The Wiener Index for Graphs of Arbitrary Girth and Their Edge Graphs

A. A. Dobrynin

Sibirskij žurnal industrialʹnoj matematiki, Tome 12 (2009) no. 4, pp. 44-50.

Résumé

We consider the invariant $W(G)$ (Wiener index) of a simple connected nondirected graph $G$, which is equal to the sum of distances between all pairs of vertices in the natural metric. We show that for every $g\ge5$ there exist planar graphs $G$ with a shortest cycle of length $g$ for which $W(L(G))=W(G)$, where $L(G)$ is the edge graph for $G$.

Détail

Mots-clés : invariant graph
Keywords: distance in graphs, Wiener index.

Bibliographie

[1] Wiener H., “Structural determination of paraffin boiling points”, J. Amer. Chem. Soc., 69 (1947), 17–20 | DOI

[2] Gutman I., Polansky O. E., Mathematical Concepts in Organic Chemistry, Springer-Verl., Berlin, 1986 | MR | Zbl

[3] Trinajstić N., Chemical Graph Theory, CRC Press, Boca Raton, 1992 | MR

[4] Gutman I., Yeh Y. N., Lee S. L., Luo Y. L., “Some recent results in the theory of the Wiener number”, Indian J. Chem. A, 32 (1993), 651–661

[5] Entringer R. C., “Distance in graphs: trees”, J. Combin. Math. Combin. Comput., 24 (1997), 65–84 | MR | Zbl

[6] Dobrynin A. A., Gutman I., “Indeks Vinera dlya derevev i grafov geksagonalnykh sistem”, Diskret. analiz i issled. operatsii. Ser. 2, 5:2 (1998), 34–60 | MR | Zbl

[7] Dobrynin A. A., Entringer R., Gutman I., “Wiener index for trees: theory and applications”, Acta Appl. Math., 66 (2001), 211–249 | DOI | MR | Zbl

[8] Dobrynin A. A., Gutman I., Klavžar S., Žigert P., “Wiener index of hexagonal systems”, Acta Appl. Math., 72 (2002), 247–294 | DOI | MR | Zbl

[9] Nikolić S., Trinajstić N., Mihalić Z., “The Wiener index: developments and applications”, Croat. Chem. Acta, 68 (1995), 105–129

[10] Bertz S. H., “Branching in graphs and molecules”, Discrete Appl. Math., 19 (1988), 65–83 | DOI | MR | Zbl

[11] Bertz S. H., Wright W. F., “The graph theory approach to synthetic analysis: definition and application of molecular complexity and synthetic complexity”, Graph Theory Notes, 35 (1998), 32–48 | MR

[12] Gutman I., Estrada E., “Topological indices based on the line graph of the molecular graph”, J. Chem. Inform. Comput. Sci., 36 (1996), 541–543

[13] Gutman I., Popović L., Mishra B. K., Kaunar M., Estrada E., Guevara N., “Application of line graphs in physical chemistry. Predicting surface tension of alkanes”, J. Serb. Chem. Soc., 62 (1997), 1025–1029

[14] Buckley F., “Mean distance of line graphs”, Congr. Numer., 32 (1981), 153–162 | MR | Zbl

[15] Gutman I., “Distance of line graphs”, Graph Theory Notes, 31 (1996), 49–52 | MR

[16] Dobrynin A. A., Gutman I., Iovashevich V., “Bitsiklicheskie grafy i ikh rebernye grafy s sovpadayuschim indeksom Vinera”, Diskret. analiz i issled. operatsii. Ser. 2, 4:2 (1997), 3–9 | MR | Zbl

[17] Gutman I., Jovašević V., Dobrynin A. A., “Smallest graphs for which the distance of the graph is equal to the distance of its line graph”, Graph Theory Notes, 33, 1997, 19 | MR

[18] Gutman I., Pavlović L., “More on distance of line graphs”, Graph Theory Notes, 33 (1997), 14–18 | MR

[19] Dobrynin A. A., Melnikov L. S., “Indeks Vinera grafov i ikh rebernykh grafov”, Diskret. analiz i issled. operatsii. Ser. 2, 11:2 (2004), 25–44 | MR | Zbl

[20] Dobrynin A. A., Mel'nikov L. S., “Wiener index, line graphs and the cyclomatic number”, MATCH Commun. Math. Comput. Chem., 53:1 (2005), 209–214 | MR | Zbl

[21] Dobrynin A. A., Mel'nikov L. S., “Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers”, Appl. Math. Lett., 18 (2005), 307–312 | DOI | MR | Zbl

[22] Dobrynin A. A., Mel'nikov L. S., “Some results on the Wiener index of iterated line graphs”, Electron. Notes Discrete Math., 22 (2005), 469–475 | DOI | Zbl

[23] Polansky O. E., Bonchev D., “The Wiener number of graphs. I. General theory and changes due to some graph operations”, MATCH Commun. Math. Comput. Chem., 21 (1986), 133–186 | MR | Zbl