The weighted complexity and the determinant functions of graphs

Title
The weighted complexity and the determinant functions of graphs
Author(s)
이재운권영수김동석[김동석]
Keywords
MATRIX-TREE THEOREM; SPANNING-TREES
Issue Date
201008
Publisher
ELSEVIER SCIENCE INC
Citation
LINEAR ALGEBRA AND ITS APPLICATIONS, v.433, no.2, pp.348 - 355
Abstract
The complexity of a graph can be obtained as a derivative of a variation of the zeta function [S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B 74 (1998) 408-410] or a partial derivative of its generalized characteristic polynomial evaluated at a point [D. Kim, H.K. Kim, J. Lee, Generalized characteristic polynomials of graph bundles, Linear Algebra Appl. 429 (4) (2008) 688-697]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [H. Mizuno, I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory Ser. B 89 (2003) 17-26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the complexity from a variation of the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs. (C) 2010 Elsevier Inc. All rights reserved.
URI
http://hdl.handle.net/YU.REPOSITORY/23837http://dx.doi.org/10.1016/j.laa.2010.03.001
ISSN
0024-3795
Appears in Collections:
이과대학 > 수학과 > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE