ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Z.-K. Zhang

Zhen-Kun Zhang

Huanghuai University



Edge-maximal graphs with cutwidth at most three



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 ,


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.


combinatorics, graph labeling, cutwidth, edge-maximal graph


  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.
  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.
  5. J. Diaz, J. Petit and M. Serna, A survey of graph layout problems, ACM Computing Surveys 34 (2002) 313–356.
  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.
  8. L. Lin and Y. Lin, Cutwidth of iterated caterpillars, RAIRO Theor. Inform. Appl. 47 (2013) 181–193.
  9. Y. Lin and A. Yang, On $3$-cutwidth critical graphs, Discrete Math. 275 (2004) 339–346.
  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.
  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.
  13. I. Vrto, Cutwidth of the r-dimensional mesh of d-ary trees, RAIRO Theor. Inform. Appl. 34 (2000) 515–519.
  14. M. Yannakakis, A polynomial algorithm for the min-cut arrangement of trees, J. ACM 32 (1985) 950–989.
  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.
  17. Z.-K. Zhang, Decompositions of critical trees with cutwidth $k$, Comput. Appl. Math. 38 (2019) 148.