Geodesic
Edge-maximal graphs with cutwidth at most three
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 635-657 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line P_n with n=|V(G)| vertices, in such a way that the maximum number of edges between each pair of consecutive vertices is minimized. A graph G with cutwidth k (k≥ 1) is edge-maximal if c(G+uv) gt;k for any uv∈{uv: u,v∈ V(G) and uv∉ E(G)}. In this paper, we provide a complete insight to structural properties of edge-maximal graphs with cutwidth at most 3.
Keywords: combinatorics, graph labeling, cutwidth, edge-maximal graph 
@article{DMGT_2023_43_3_a3,
     author = {Zhang, Zhen-Kun},
     title = {Edge-maximal graphs with cutwidth at most three},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {635--657},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a3/}
}
TY  - JOUR
AU  - Zhang, Zhen-Kun
TI  - Edge-maximal graphs with cutwidth at most three
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 635
EP  - 657
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a3/
LA  - en
ID  - DMGT_2023_43_3_a3
ER  - 
%0 Journal Article
%A Zhang, Zhen-Kun
%T Edge-maximal graphs with cutwidth at most three
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 635-657
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a3/
%G en
%F DMGT_2023_43_3_a3
Zhang, Zhen-Kun. Edge-maximal graphs with cutwidth at most three. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 635-657. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a3/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).

[2] F.R.K. Chung, Labelings of graphs, in: Selected Topics in Graph Theory, L.W. Beineke and R.J. Wilson (Eds.) 3 (1988) 151–168.

[3] F.R.K. Chung and P.D. Seymour, Graphs with small bandwidth and cutwidth, Discrete Math. 75 (1989) 113–119. https://doi.org/10.1016/0012-365X(89)90083-6

[4] M.J. Chung, F. Makedon, I.H. Sudborough and J. Turner, Polynomial time algorithms for the min cut problem on degree restricted trees, SIAM J. Comput. 14 (1985) 158–177. https://doi.org/10.1137/0214013

[5] J. Diaz, J. Petit and M. Serna, A survey of graph layout problems, ACM Computing Surveys 34 (2002) 313–356. https://doi.org/10.1145/568522.568523

[6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Company, San Francisco, 1979).

[7] E. Korach and N. Solel, Tree-width, path-width and cutwidth, Discrete Appl. Math. 43 (1993) 97–101. https://doi.org/10.1016/0166-218X(93)90171-J

[8] L. Lin and Y. Lin, Cutwidth of iterated caterpillars, RAIRO Theor. Inform. Appl. 47 (2013) 181–193. https://doi.org/10.1051/ita/2012032

[9] Y. Lin and A. Yang, On 3-cutwidth critical graphs, Discrete Math. 275 (2004) 339–346. https://doi.org/10.1016/j.disc.2003.06.012

[10] H. Liu and J. Yuan, The cutwidth problem on graphs, Appl. Math. J. Chinese Univ. Ser. A 3 (1995) 339–347.

[11] F.S. Makedon, C.H. Papadimitriou and I.H. Sudborough, Topological bandwidth, SIAM J. on Algebraic and Discrete Methods 6 (1985) 418–444. https://doi.org/10.1137/0606044

[12] D.M. Thilikos, M. Serna and H.L. Bodlaender, Cutwidth II:} Algorithms for partial w-trees of bounded degree, J. Algorithms 56 (2005) 25–49. https://doi.org/10.1016/j.jalgor.2004.12.003

[13] I. Vrto, Cutwidth of the r-dimensional mesh of d-ary trees, RAIRO Theor. Inform. Appl. 34 (2000) 515–519. https://doi.org/10.1051/ita:2000128

[14] M. Yannakakis, A polynomial algorithm for the min-cut arrangement of trees, J. ACM 32 (1985) 950–989. https://doi.org/10.1145/4221.4228

[15] Z.-K. Zhang and Y. Lin, On 4-cutwidth critical trees, Ars Combin. 105 (2012) 149–160.

[16] Z.-K. Zhang and H.-J. Lai, Characterizations of k-cutwidth critical trees, J. Comb. Optim. 34 (2017) 233–244. https://doi.org/10.1007/s10878-016-0061-5

[17] Z.-K. Zhang, Decompositions of critical trees with cutwidth k, Comput. Appl. Math. 38 (2019) 148. https://doi.org/10.1007/s40314-019-0924-3