A Study On Independence Number of Deg-Centric Graphs

Résumé

The deg-centric graph of a simple, connected graph $G$, denoted by $G_d$, is a graph constructed from $G$ such that $V(G_d) = V(G)$ and $E(G_d) = \{v_iv_j: d_G(v_i,v_j) \leq deg_G(v_i)\}$. A set $S$ is independent in a graph $G$ if any pair of vertices $u,v\in S$ are nonadjacent in $G$. Maximum independent sets in $G$ will also be called $\alpha-$sets in $G.$ The independence number $\alpha(G)$ of a graph $G$ is the cardinality of an $\alpha-$set in $G.$ Thus, an independent set $S$ in $G$ is an $\alpha-$ set whenever $|S|=\alpha(G)$. This paper presents the independence number of the deg-centric graphs. Also, investigate the properties and structural characteristics of this type of graph.