THE STRUCTURE OF GRAPHS ON \(n\) VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO \(n-2\) - Do Nhu An (Tạp chí Khoa học Đại học Đà Lạt)
Let \(G\) be an undirected simple graph on n vertices and \(σ^2(G)=n-2\) (degree sum of any two non-adjacent vertices in \(G\) is equal to \(n-2\)) and \(α(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 \(α(G)=2\) and \(G\) is a disconnected graph; for \(n≥4\) is an even number then \(2≤α(G)≤(n+2)/2\), where if \(α(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 \(δ=(n-2)/2\), where \(0≤ k≤(n-2)/2\). In particular, when \(k=0\) then \(G\) is an \((n-2)/2\)-Regular graph.