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

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 sigma2(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>=3 is an odd number then alpha(G)=2 and G is a disconnected graph; for n>=4 is an even number then 2=<alpha(G)<=(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<=k<=(n-2)/2. In particular, when k=0 then G is an (n-2)/2-Regular graph.

Metrics

Metrics Loading ...

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)