Geodesic
The Wiener index of maximal outerplane graphs
Prikladnaâ diskretnaâ matematika, no. 4 (2014), pp. 112-122.

Voir la notice de l'article provenant de la source Math-Net.Ru

Wiener index $W(G)$ of a connected undirected graph $G$ equals the sum of distances between all pairs of vertices in $G$. In this paper, an effective algorithm for calculating Wiener index of maximal outerplane graphs with a big number $n$ of vertices is offered. The time complexity of the algorithm is $\mathrm O(n^2)$. The algorithm is fit for manual calculation of Wiener index of small graphs, as well as for its calculation for computer generated graphs.
Mots-clés : graph algorithm
Keywords: maximal outerplane graph, Wiener index, chordal graph, compact representation of chordal graph. 
@article{PDM_2014_4_a11,
     author = {Y. L. Nosov},
     title = {The  {Wiener} index of maximal outerplane graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {112--122},
     publisher = {mathdoc},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_4_a11/}
}
TY  - JOUR
AU  - Y. L. Nosov
TI  - The  Wiener index of maximal outerplane graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 112
EP  - 122
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_4_a11/
LA  - ru
ID  - PDM_2014_4_a11
ER  - 
%0 Journal Article
%A Y. L. Nosov
%T The  Wiener index of maximal outerplane graphs
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 112-122
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_4_a11/
%G ru
%F PDM_2014_4_a11
Y. L. Nosov. The  Wiener index of maximal outerplane graphs. Prikladnaâ diskretnaâ matematika, no. 4 (2014), pp. 112-122. http://geodesic.mathdoc.fr/item/PDM_2014_4_a11/

[1] Evstigneev V. A., Kasyanov V. N., Slovar po grafam v informatike, OOO “Sibirskoe nauchnoe izdatelstvo”, Novosibirsk, 2009, 300 pp.

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

[3] Fedyanin D. N., “Ob indekse Vinera v posledovatelnosti sotsialnykh setei”, Tr. 52-i nauch. konf. MFTI “Soremennye problemy fundamentalnykh i prikladnykh nauk”. Ch. I. Radiotekhnika i kibernetika, v. 2, MFTI, M., 2009, 94–97

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

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

[6] Gutman I., Yan W., Yang B. Y., Yeh Y. N., “Generalized Wiener indices of zigzagging pentachains”, J. Math. Chem., 42:2 (2007), 103–117 | DOI | MR | Zbl

[7] Gutman I., Yeh Y. N., Lee S. L., Chen J. C., “Wiener numbers of dendrimer”, Commum. Math. Chem., 30:1 (1984), 103–115

[8] Vukičević D., Trinajstić N., “Wiener indices of benzenoid graphs”, Bulletin of the Chemists and Technologists of Macedonia, 23:2 (2004), 113–129

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

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

[11] Dobrynin A. A., “Indeks Vinera dlya grafov proizvolnogo obkhvata i ikh rebernykh grafov”, Sibirskii zhurnal industrialnoi matematiki, 22:4(40) (2009), 44–50 | MR

[12] Šoltés L., “Transmission in graphs: a bound and vertex removing”, Math. Slovaca, 41:1 (1991), 11–16 | MR | Zbl

[13] El Marraki M., Al Hagri G., “Calculation of the Wiener index for some particular trees”, J. Theor. Appl. Inform. Technology (JATIT), 22:2 (2010), 77–83

[14] Floyd R. W., “Algorithm 97: Shortest Path”, Comm. ACM, 5:6 (1962), 345 | DOI

[15] Warshall S., “A theorem on Boolean matrices”, J. ACM, 9:1 (1962), 11–12 | DOI | MR | Zbl

[16] Johnson D. B., “Efficient algorithms for shortest paths in sparse networks”, J. ACM, 24:1 (1977), 1–13 | DOI | MR | Zbl

[17] Müller W. R., Szymanski K., Knop J. V., Trinajstić N., “An algorithm for construction of the molecular distance matrix”, J. Comput. Chem., 8:2 (1987), 170–173 | DOI

[18] Dijkstra E. W., “A note on two problems in connexion with graphs”, Numer. Math., 1:1 (1959), 269–271 | DOI | MR | Zbl

[19] Mohar B., Pisanski T., “How to compute the Wiener index of a graph”, J. Math. Chem., 3:2 (1988), 267–277 | DOI | MR

[20] Bellman R., “On a routing problem”, Quart. Appl. Math., 16:1 (1958), 87–90 | MR | Zbl

[21] Ford (Jr.) L. R., Network Flow Theory, Paper P-923, RAND Corp., Santa Monica, California, 1956

[22] Kharari F., Teoriya grafov, Mir, M., 1973, 300 pp. | MR

[23] Felzenszwalb P. F., “Representation and detection of deformable shapes”, IEEE Trans. Pattern Analys. Machine Intelligence, 27:2 (2005), 208–220 | DOI

[24] Dirac G. A., “On rigid circuit graphs”, Abh. Math. Sem. Univ. Hamburg, 25 (1967), 71–76 | DOI | MR

[25] Asratian A. S., Oksimets N., “Graphs with hamiltonian balls”, Australasian J. Combinator., 17:4 (1998), 185–198 | MR | Zbl

[26] Rose D., Tarjan R. E., Lueker G., “Algorithmic aspects of vertex elimination on graphs”, SIAM J. Comput., 5:2 (1976), 146–160 | DOI | MR

[27] Tarjan R. E., Yannakakis M., “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs”, SIAM J. Comput., 13:3 (1984), 566–579 | DOI | MR | Zbl

[28] Beyer T., Jones W., Mitchell S., “Linear algorithms for isomorphism of Maximal outerplanar graphs”, J. ACM, 26:4 (1979), 603–610 | DOI | MR | Zbl

[29] Markenzon L., Pereira P. R. C., “A compact representation for chordal graphs”, Proc. of Workshop on Graphs and Combinatorial Optimization, CTW, Gargnano, 2008, 174–176

[30] Blair J. R. S., Peyton B., “An introduction to chordal graphs and clique trees”, Graph Theory and Sparse Matrix Computation, Springer Verlag, N.Y., 1993, 1–29 | DOI | MR | Zbl

[31] Markenzon L., Vernet O., Representações Computacionais de Grafos, Notas em Matemática Aplicada, 24, SBMAC, São Carlos, SP, 2006, 76 pp.