×

Resistance characterizations of equiarboreal graphs. (English) Zbl 1370.05087

Summary: A weighted (unweighted) graph \(G\) is called equiarboreal if the sum of weights (the number) of spanning trees containing a given edge in \(G\) is independent of the choice of edge. In this paper, we give some resistance characterizations of equiarboreal weighted and unweighted graphs, and obtain the necessary and sufficient conditions for \(k\)-subdivision graphs, iterated double graphs, line graphs of regular graphs and duals of planar graphs to be equiarboreal. Applying these results, we obtain new infinite families of equiarboreal graphs, including iterated double graphs of 1-walk-regular graphs, line graphs of triangle-free 2-walk-regular graphs, and duals of equiarboreal planar graphs.

MSC:

05C22 Signed and weighted graphs
05C05 Trees
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bapat, R. B., Resistance matrix of a weighted graph, MATCH Commun. Math. Comput. Chem., 50, 73-82 (2004) · Zbl 1052.05028
[2] Bapat, R. B.; Gupta, S., Resistance distance in wheels and fans, Indian J. Pure Appl. Math., 41, 1-13 (2010) · Zbl 1203.05041
[3] Biggs, N., Potential theory on distance-regular graphs, Combin. Probab. Comput., 2, 243-255 (1993) · Zbl 0793.94007
[4] Bollobás, B., Modern Graph Theory (1998), Springer: Springer New York · Zbl 0902.05016
[5] Chaiken, S., A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebr. Discrete Methods, 3, 319-329 (1982) · Zbl 0495.05018
[6] Chen, H., Random walks and the effective resistance sum rules, Discrete Appl. Math., 158, 1691-1700 (2010) · Zbl 1208.05136
[7] Ciucu, M.; Yan, W. G.; Zhang, F. J., The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A, 112, 105-116 (2005) · Zbl 1072.05038
[8] Coolsaet, K.; Jurišić, A.; Koolen, J., On triangle-free distance-regular graphs with an eigenvalue multiplicity equal to the valency, European J. Combin., 29, 1186-1199 (2008) · Zbl 1182.05133
[9] Dalfó, C.; van Dam, E. R.; Fiol, M. A.; Garriga, E.; Gorissen, B. L., On almost distance-regular graphs, J. Combin. Theory Ser. A, 118, 1094-1113 (2011) · Zbl 1225.05249
[10] Diestel, R., Graph Theoy (2006), Springer: Springer New York
[11] Fleischner, H.; Imrich, W., Transitive planar graphs, Math. Slovaca, 29, 97-106 (1979) · Zbl 0424.05023
[12] Fraisse, P.; Hell, P., Equicovering matroids by distinct bases, European J. Combin., 16, 159-162 (1995) · Zbl 0822.05015
[13] Godsil, C. D., Equiarboreal graphs, Combinatorica, 1, 163-167 (1981) · Zbl 0489.05047
[14] Huang, Q.; Chen, H.; Deng, Q., Resistance distances and the kirchhoff index in double graphs, J. Appl. Math. Comput., 50, 1-14 (2016) · Zbl 1330.05052
[15] Jakobson, D.; Rivin, I., Extremal metrics on graphs. I, Forum Math., 14, 147-163 (2002) · Zbl 0995.05072
[16] Kirkland, S.; Neumann, M.; Shader, B., Distances in weighted trees and group inverse of Laplacian matrices, SIAM J. Matrix Anal. Appl., 18, 827-841 (1997) · Zbl 0889.15004
[17] Klein, D. J.; Ivanciuc, O., Graph cyclicity, excess conductance, and resistance deficit, J. Math. Chem., 30, 271-287 (2001) · Zbl 1008.05082
[18] Klein, D. J.; Randić, M., Resistance distance, J. Math. Chem., 12, 81-95 (1993)
[19] Koolen, J. H.; Markowsky, G.; Park, J., On electric resistances for distance-regular graphs, European J. Combin., 34, 770-786 (2013) · Zbl 1259.05193
[20] Liu, X.; Zhou, J.; Bu, C., Resistance distance and Kirchhoff index of R-vertex join and R-edge join of two graphs, Discrete Appl. Math., 187, 130-139 (2015) · Zbl 1315.05129
[21] Munarini, E.; Cippo, C. P.; Scagliola, A.; Salvi, N. Z., Double graphs, Discrete Math., 308, 242-254 (2008) · Zbl 1131.05042
[22] Nikseresht, A.; Sepasdar, Z., On the Kirchhoff and the Wiener indices of graphs and block decomposition, Electron. J. Combin., 21, P1.25 (2014) · Zbl 1300.05086
[23] Sun, L.; Wang, W.; Zhou, J.; Bu, C., Some results on resistance distances and resistance matrices, Linear Multilinear Algebra, 63, 523-533 (2015) · Zbl 1306.05046
[24] Thomassen, C., Resistances and currents in infinite electrical networks, J. Combin. Theory Ser. B, 49, 87-102 (1990) · Zbl 0706.94029
[25] Yang, Y. J., On a new cyclicity measure of graphs-The global cyclicity index, Discrete Appl. Math., 172, 88-97 (2014) · Zbl 1288.05139
[26] Zhou, J.; Wang, Z.; Bu, C., On the resistance matrix of a graph, Electron. J. Combin., 23, P1.41 (2016) · Zbl 1333.05191
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.