TY - JOUR
AU - An, Do Nhu
TI - THE STRUCTURE OF GRAPHS ON \(n\) VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO \(n-2\)
PY - 2021/10/04
Y2 - 2024/09/14
JF - Dalat University Journal of Science
JA - DLU JOS
VL - 11
IS - 4
LA - en
DO - 10.37569/DalatUniversity.11.4.830(2021)
UR - https://doi.org/10.37569/DalatUniversity.11.4.830(2021)
SP - 55-62
AB - 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.
ER -