1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Edge-Maximal Graphs with Cutwidth at Most Three

Published Online: 18 Mar 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 18 Mar 2020
Accepted: 28 Dec 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn 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) > k for any uv ∈ {uv : u, vV (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

MSC 2010

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).10.1007/978-1-84628-970-5Search in Google Scholar

[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.Search in Google Scholar

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

[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. doi:10.1137/021401310.1137/0214013Search in Google Scholar

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

[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).Search in Google Scholar

[7] E. Korach and N. Solel, Tree-width, path-width and cutwidth, Discrete Appl. Math. 43 (1993) 97–101. doi:10.1016/0166-218X(93)90171-J10.1016/0166-218X(93)90171-JSearch in Google Scholar

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

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

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

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

[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. doi:10.1016/j.jalgor.2004.12.00310.1016/j.jalgor.2004.12.003Search in Google Scholar

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

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

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

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo