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

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

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...

Full description

Saved in:

Bibliographic Details
Main Author:	Do Nhu An
Format:	Article
Language:	English
Published:	Dalat University 2021-10-01
Series:	Tạp chí Khoa học Đại học Đà Lạt
Subjects:	connected graph disconnected graph maximum independent set regular graph.
Online Access:	https://tckh.dlu.edu.vn/index.php/tckhdhdl/article/view/830
Tags:	Add Tag No Tags, Be the first to tag this record!

_version_	1832569041136386048
author	Do Nhu An
author_facet	Do Nhu An
author_sort	Do Nhu An
collection	DOAJ
description	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.
format	Article
id	doaj-art-3bd6bf5ed6a84fd282f3f37db6149c97
institution	Kabale University
issn	0866-787X
language	English
publishDate	2021-10-01
publisher	Dalat University
record_format	Article
series	Tạp chí Khoa học Đại học Đà Lạt
spelling	doaj-art-3bd6bf5ed6a84fd282f3f37db6149c972025-02-02T23:31:55ZengDalat UniversityTạp chí Khoa học Đại học Đà Lạt0866-787X2021-10-01556210.37569/DalatUniversity.11.4.830(2021)600THE STRUCTURE OF GRAPHS ON $n$ VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO $n-2$Do Nhu An0Nha Trang UniversityLet $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.https://tckh.dlu.edu.vn/index.php/tckhdhdl/article/view/830connected graphdisconnected graphmaximum independent setregular graph.
spellingShingle	Do Nhu An THE STRUCTURE OF GRAPHS ON $n$ VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO $n-2$ Tạp chí Khoa học Đại học Đà Lạt connected graph disconnected graph maximum independent set regular graph.
title	THE STRUCTURE OF GRAPHS ON $n$ VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO $n-2$
title_full	THE STRUCTURE OF GRAPHS ON $n$ VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO $n-2$
title_fullStr	THE STRUCTURE OF GRAPHS ON $n$ VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO $n-2$
title_full_unstemmed	THE STRUCTURE OF GRAPHS ON $n$ VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO $n-2$
title_short	THE STRUCTURE OF GRAPHS ON $n$ VERTICES WITH THE DEGREE SUM OF ANY TWO NONADJACENT VERTICES EQUAL TO $n-2$
title_sort	structure of graphs on n vertices with the degree sum of any two nonadjacent vertices equal to n 2
topic	connected graph disconnected graph maximum independent set regular graph.
url	https://tckh.dlu.edu.vn/index.php/tckhdhdl/article/view/830
work_keys_str_mv	AT donhuan thestructureofgraphsonnverticeswiththedegreesumofanytwononadjacentverticesequalton2 AT donhuan structureofgraphsonnverticeswiththedegreesumofanytwononadjacentverticesequalton2

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

Similar Items