THE STRUCTURE OF GRAPHS ON \(n\) VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO \(n-2\)

Authors

  • Do Nhu An Nha Trang University, Viet Nam

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

Download data is not yet available.

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

04-10-2021

Volume and Issues

Section

Natural Sciences and Technology

How to Cite

An, D. N. (2021). THE STRUCTURE OF GRAPHS ON \(n\) VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO \(n-2\). Dalat University Journal of Science, 11(4), 55-62. https://doi.org/10.37569/DalatUniversity.11.4.830(2021)