Extremal by Wiener index maximal outerplane graphs with two simplicial vertices

Yu. L. Nosov

Čelâbinskij fiziko-matematičeskij žurnal, Tome 4 (2019) no. 3, pp. 285-322.

Résumé

We consider the maximal outerplane graphs (mops) with two simplicial vertices, with the extreme values of the Wiener index. The lower $W^L_n = n^2-3n+3$ and upper $W^U_n=(4n^3+6n^2-4n-3+3(-1)^n)/48$ bounds of the Wiener index of arbitrary mops of the order $n$ are determined. For the lattice mops (L-mops), i. e. the graphs that are laid out on the lattice of equilateral triangles without voids and overlaps, we prove that the upper bound of Wiener index matches that of the arbitrary mops. The lower bound $W^{[L]}_n$ of Wiener index of L-mops is defined as follows: $W^{[L]}_n = (n^3 +6n^2-15n+26)/18$ if $(n- 4) \bmod 3 = 0$ and $W^{[L]}_n = (n^3 +6n^2-9n+2-2(-1)^q)/18$ if $(n- 4) \bmod 3 = q$ where $q=1,2$. For the lower and upper bounds of Wiener index of arbitrary and lattice mops we determine the extremal graphs, where these bounds are reached. We provide a constructive classification of L-mops. For all classes of L-mops we determine the extremal graphs and their respective Wiener indices. For each class of L-mops we show the existence of isomorphism and geometric similarity between dual graphs of L-mop class and molecular graphs of isomers and conformers of conjugated polyene hydrocarbons (CPH). The obtained results can be used for classification of shapes in images represented by mops and for classification of CPH isomers.

Détail

Keywords: maximal outerplane graph, extremal graph, Wiener index.

Bibliographie

[1] Harary F., Graph Theory, Addison-Wesley, Reading, 1969, 274 pp. | MR | Zbl

[2] B. Bollobás, Extremal Graph Theory, Academic Press, London–New York–San Francisco, 1978, 488 pp. | MR | Zbl

[3] Stankevich I.V., “Graphs in structural chemistry”, Application of graph theory in chemistry, Siberian Scientific Publishing House, Novosibirsk, 1988, 7–69 (In Russ.)

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

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

[6] M. Knor, R. S̆krekovski, A. Tepeh, “Mathematical aspects of Wiener index”, Ars Mathematica Contemporanea, 11:3 (2016), 327–352 | DOI | MR | Zbl

[7] R. C. Entringer, D. E. Jackson, D. A. Snyder, “Distance in graphs”, Czechoslovak Mathematical Journal, 26:101 (1976), 283–296 | MR | Zbl

[8] M. Fischermann, A. Hoffmann, D. Rautenbach, L. Szekely, L. Volkmann, “Wiener index versus maximum degree in trees”, Discrete Applied Mathematics, 122:1–3 (2002), 127–137 | DOI | MR | Zbl

[9] D. Stevanović, “Maximizing Wiener index of graphs with fixed maximum degree”, MATCH Communications in Mathematical and in Computer Chemistry, 60:1 (2008), 71–83 | MR | Zbl

[10] H. Wang, “The extremal values of the Wiener index of a tree with given degree sequence”, Discrete Applied Mathematics, 156:14 (2008), 2647–2654 | DOI | MR | Zbl

[11] X. D. Zhang, Q. Y. Xiang, L. Q. Xu, R. Y. Pan, “The Wiener index of trees with given degree sequences”, MATCH Communications in Mathematical and in Computer Chemistry, 60:2 (2008), 623–644 | MR | Zbl

[12] On the Wiener index of trees with fixed diameter, “H. Liu, X. F. Pan”, MATCH Communications in Mathematical and in Computer Chemistry, 60:2 (2008), 85–94 | MR

[13] K. Ch. Das., M. J. Nadjafi-Arani, “On maximum Wiener index of trees and graphs with given radius”, Journal of Combinatorial Optimization, 34:2 (2017), 574–587 | DOI | MR | Zbl

[14] P. Dankelmann, “Average distance and independence number”, Discrete Applied Mathematics, 51:1–2 (1994), 75–83 | DOI | MR | Zbl

[15] Minimum Wiener indices of trees and unicyclic graphs of given matching number, “Z. Du”, MATCH Communications in Mathematical and in Computer Chemistry, 63:1 (2010), 101–112 | MR

[16] H. Lin, “On the Wiener index of trees with given number of branching vertices”, MATCH Communications in Mathematical and in Computer Chemistry, 72:1 (2014), 301–310 | MR | Zbl

[17] H. Lin, “On segment sequences and the Wiener index of trees”, MATCH Communications in Mathematical and in Computer Chemistry, 75:1 (2016), 91–104 | MR

[18] A. M. Farley, A. Proskurowski, “Computation of the center and diameter of outerplanar graphs”, Discrete Applied Mathematics, 2:3 (1980), 185–191 | DOI | MR | Zbl

[19] A. Proskurowski, “Centers of maximal outerplanar graphs”, Journal of Graph Theory, 4:2 (1980), 75–79 | DOI | MR | Zbl

[20] A. S. Asratian, N. Oksimets, “Graphs with Hamiltonian balls”, The Australasian Journal of Combinatorics, 17:4 (1998), 185–198 | MR | Zbl

[21] Nosov Yu.L., “The Wiener index of maximal outerplane graphs”, Applied discrete mathematics, 26:4 (2014), 112–122 (In Russ.)

[22] Nosov Yu.L., “Maximal outerplane graphs with two simplicial vertices”, Applied discrete mathematics, 29:3 (2015), 95–109 (In Russ.)

[23] S. J. Cyvin, E. K. Lloyd, B. N. Cyvin, J. Brunvoll, “Chemical relevance of a pure combinatorial problem: Isomers of conjugated polyenes”, Structural Chemistry, 7:3 (1996), 183–186 | DOI

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

[25] Nosov Yu.L., “Maximal outerplane graphs of extremal diameter values”, Chelyabinsk Physical and Mathematical Journal, 3:4 (2018), 421–437 (In Russ.) | MR

[26] Wolfram Mathematica, (Accessed: 02.02.2019) https://www.wolfram.com/mathematica

[27] The On-Line Encyclopedia of Integer Sequences, (Accessed: 01.02.2019) http://www.oeis.org/A004526

[28] G. P. Moss, “Basic terminology of stereochemistry (IUPAC Recommendations 1996)”, Pure and Applied Chemistry, 68:12 (1996), 2193–2222 | DOI

[29] PubChem, (Accessed: 02.02.2019) https://pubchem.ncbi.nlm.nih.gov

[30] ChemSpider, (Accessed: 02.02.2019) http://www.chemspider.com