Hoffman-type identities. (English) Zbl 1041.05048
Let \(G\) be a simple graph and let \(A\) be the adjacency matrix of \(G\). Hoffman observed that \(G\) is a connected regular graph if and only if there exists a polynomial \(P(x)\) such that \(P(A) = J\), where \(J\) is the \(n\times n\) all-one matrix. In this work the authors generalize the Hoffman identity and derive corresponding identities for the recently introduced classes of harmonic and semiharmonic graphs.
Reviewer: Mirko Lepović (Kragujevac)
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05A19 | Combinatorial identities, bijective combinatorics |
References:
| [1] | Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36 (1963) · Zbl 0112.14901 |
| [2] | Cvetković, D.; Rowlinson, P.; Simić, S., Eigenspaces of Graphs (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0878.05057 |
| [3] | Dress, A.; Gutman, I., The number of walks in graphs, Appl. Math. Lett., 11, 4, 43-49 (1998) · Zbl 0936.92022 |
| [4] | B. Borovićanin, S. Grünewald, I. Gutman and M. Petrović, Harmonic graphs with small number of cycles, Discrete Mathematics; B. Borovićanin, S. Grünewald, I. Gutman and M. Petrović, Harmonic graphs with small number of cycles, Discrete Mathematics |
| [5] | A. Dress and S. Grünewald, Semiharmonic trees and monocyclic graphs, Appl. Math. Lett.; A. Dress and S. Grünewald, Semiharmonic trees and monocyclic graphs, Appl. Math. Lett. · Zbl 1039.05050 |
| [6] | A. Dress and I. Gutman, Asymptotic results regarding the number of walks in a graph, Appl. Math. Lett.; A. Dress and I. Gutman, Asymptotic results regarding the number of walks in a graph, Appl. Math. Lett. · Zbl 1041.05047 |
| [7] | Grünewald, S., Harmonic trees, Appl. Math. Lett., 15, 8, 1001-1004 (2002) · Zbl 1009.05041 |
| [8] | S. Grünewald and D. Stevanović, Semiharmonic bicyclic graphs, (submitted).; S. Grünewald and D. Stevanović, Semiharmonic bicyclic graphs, (submitted). |
| [9] | Hoffman, A. J., The polynomial of a directed graph, (Proc. Amer. Math. Soc., 16 (1965)), 303-309 · Zbl 0129.40102 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
