THE STRUCTURE OF GRAPHS ON \(n\) VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO \(n-2\)
DOI:
https://doi.org/10.37569/DalatUniversity.11.4.830(2021)Keywords:
Connected graph, Disconnected graph, Maximum independent set, Regular graph.Abstract
Let \(G\) be an undirected simple graph on n vertices and \(\sigma^2(G)=n-2\) (degree sum of any two non-adjacent vertices in \(G\) is equal to \(n-2\)) and \(\alpha(G)\) be the cardinality of an maximum independent set of \(G\). In \(G\), a vertex of degree \((n-1)\) is called total vertex. We show that, for \(n\geq3\) is an odd number then \(\alpha(G)=2\) and \(G\) is a disconnected graph; for \(n\geq4\) is an even number then \(2\leq\alpha(G)\leq(n+2)/2\), where if \(\alpha(G)=2\) then \(G\) is a disconnected graph, otherwise \(G\) is a connected graph, \(G\) contains \(k\) total vertices and \(n-k\) vertices of degree \(\delta=(n-2)/2\), where \(0\leq k\leq(n-2)/2\). In particular, when \(k=0\) then \(G\) is an \((n-2)/2\)-Regular graph.
Downloads
References
An, D. N. (2008). Some problems about Hamiltonian cycle in special graphs. The 2nd International Conference on Theories and Applications of Computer Science (ICTACS’09) - Journal of Science and Technology, Vietnam Academy of Science and Technology, 6(5A-Special issue), 57-66.
An, D. N. (2019). Recognizing the Hamiltonian graph on n vertices with σ_2 (G)=n-1 is an easy problem. International Journal of Advanced Research in Computer Science, 10(2), 42-45.
Graham, R. L., Grötschel, M., & Lovász, L. (1995). Handbook of combinatorics (1st Ed.). North Holland.
Downloads
Published
Volume and Issues
Section
Copyright & License
Copyright (c) 2021 Do Nhu An.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.