Article in volume
Authors:
Title:
Edge-maximal graphs with cutwidth at most three
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 635-657
Received: 2020-03-15 , Revised: 2020-12-28 , Accepted: 2020-12-28 , Available online: 2021-02-15 , https://doi.org/10.7151/dmgt.2395
Abstract:
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\ge 1)$ is edge-maximal if
$c(G+uv)>k$ for any $uv\in \{uv: u,v\in V(G)$ and $uv\notin 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
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).
- 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.
- 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 - 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 - 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 - 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).
- 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 - L. Lin and Y. Lin, Cutwidth of iterated caterpillars, RAIRO Theor. Inform. Appl. 47 (2013) 181–193.
https://doi.org/10.1051/ita/2012032 - 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 - H. Liu and J. Yuan, The cutwidth problem on graphs, Appl. Math. J. Chinese Univ. Ser. A 3 (1995) 339–347.
- 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 - 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 - 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 - 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 - Z.-K. Zhang and Y. Lin, On $4$-cutwidth critical trees, Ars Combin. 105 (2012) 149–160.
- 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 - 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
Close