Geodesic
The Degree-Diameter Problem for Outerplanar Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 823-834.

Voir la notice de l'article provenant de la source Library of Science

For positive integers Δ and D we define n_Δ, D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that n_Δ , D = Δ^D/2 + O ( Δ^ D/2 -1 ) if D is even, and n_Δ, D = 3 Δ^D−1/2 + O (Δ^D−1/2−1 ) if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equalsn_Δ , D .
Keywords: outerplanar, diameter, degree, degree-diameter problem, distance, separator theorem 
@article{DMGT_2017_37_3_a22,
     author = {Dankelmann, Peter and Jonck, Elizabeth and Vetr{\'\i}k, Tom\'a\v{s}},
     title = {The {Degree-Diameter} {Problem} for {Outerplanar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {823--834},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a22/}
}
TY  - JOUR
AU  - Dankelmann, Peter
AU  - Jonck, Elizabeth
AU  - Vetrík, Tomáš
TI  - The Degree-Diameter Problem for Outerplanar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 823
EP  - 834
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a22/
LA  - en
ID  - DMGT_2017_37_3_a22
ER  - 
%0 Journal Article
%A Dankelmann, Peter
%A Jonck, Elizabeth
%A Vetrík, Tomáš
%T The Degree-Diameter Problem for Outerplanar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 823-834
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a22/
%G en
%F DMGT_2017_37_3_a22
Dankelmann, Peter; Jonck, Elizabeth; Vetrík, Tomáš. The Degree-Diameter Problem for Outerplanar Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 823-834. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a22/

[1] M. Abas, Cayley graphs of diameter two and any degree with order half of the Moore bound, Discrete Appl. Math. 173 (2014) 1–7. doi:10.1016/j.dam.2014.04.005

[2] C. Balbuena, M. Miller, J. Širáň and M. Ždímalová, Large vertex-transitive graphs of diameter 2 from incidence graphs of biaffine planes, Discrete Math. 313 (2013) 2014–2019. doi:10.1016/j.disc.2013.03.007

[3] C. Dalfó, C. Huemer and J. Salas, The degree/diameter problem in maximal planar bipartite graphs, Electron. J. Combin. 23 (1) (2016) #P60.

[4] P. Dankelmann, D. Erwin, W.D. Goddard, S. Mukwembi and H.C. Swart, A characterisation of eccentric sequences of maximal outerplanar graphs, Australas. J. Combin. 58 (2014) 376–391.

[5] P. Dankelmann and T. Vetrík, The degree-diameter problem for claw-free graphs and hypergraphs, J. Graph Theory 75 (2014) 105–123. doi:10.1002/jgt.21716

[6] A.M. Farley and A. Proskurowski, Computation of the center and diameter of outerplanar graphs, Discrete Appl. Math. 2 (1980) 185–191. doi:10.1016/0166-218X(80)90039-6

[7] M. Fellows, P. Hell and K. Seyffarth, Large planar graphs with given diameter and maximum degree, Discrete Appl. Math 61 (1995) 133–153. doi:10.1016/0166-218X(94)00011-2

[8] R. Feria-Purón and G. Pineda-Villavicencio, On bipartite graphs of defect at most 4, Discrete Appl. Math 160 (2012) 140–154. doi:10.1016/j.dam.2011.09.002

[9] P. Hell and K. Seyffarth, Largest planar graphs of diameter two and fixed maximum degree, Discrete Math. 111 (1993) 313–322. doi:10.1016/0012-365X(93)90166-Q

[10] R.J. Lipton and R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177–189. doi:10.1137/0136016

[11] E. Nevo, G. Pineda-Villavicencio and D.R. Wood, On the maximum order of graphs embedded in surfaces, J. Combin. Theory Ser. B 119 (2016) 28–41. doi:10.1016/j.jctb.2015.12.004

[12] A. Proskurowski, Centers of maximal outerplanar graphs, J. Graph Theory 4 (1980) 75–79. doi:10.1002/jgt.3190040108

[13] K. Seyffarth, Maximal planar graphs of diameter two, J. Graph Theory 13 (1989) 619–648. doi:10.1002/jgt.3190130512

[14] S.A. Tishchenko, Maximum size of a planar graph with given degree and even diameter, European J. Combin. 33 (2012) 380–396. doi:10.1016/j.ejc.2011.09.005

[15] T. Vetrík, Abelian Cayley graphs of given degree and diameter 2 and 3, Graphs Combin. 30 (2014) 1587–1591. doi:10.1007/s00373-013-1361-5

[16] T. Vetrík, R. Simanjuntak and E. Baskoro, Large bipartite Cayley graphs of given degree and diameter, Discrete Math. 311 (2011) 324–326. doi:10.1016/j.disc.2010.10.015

[17] Y. Yang, J. Lin and Y. Dai, Largest planar graphs and largest maximal planar graphs of diameter two, J. Comput. Appl. Math. 144 (2002) 349–358. doi:10.1016/S0377-0427(01)00572-6