Common Independence in Graphs

For notation and graph theory terminology we, in general, follow [1]. Specifically, let $G=(V_G,E_G)$ be a graph with vertex set $V_G$ and edge set $E_G$. If A and B are disjoint sets of vertices of G, then we denote by $E_G(A,B)$ the set of edges in G joining a vertex in A with a vertex in B. For a vertex v of G, its neighborhood, denoted by $N_G\left(v\right)$, is the set of all vertices adjacent to v, and the cardinality of $N_G\left(v\right)$, denoted by $d_G\left(v\right)$, is called the degree of v. The closed neighborhood of v, denoted by $N_G\left[v\right]$, is the set $N_G\left(v\right)\cup \left\{v\right\}$. In general, for a subset $X\subseteq V_G$ of vertices, the neighborhood of X, denoted by $N_G\left(X\right)$, is defined to be ${\bigcup }_{v\in X}{N}_G\left(v\right)$, and the closed neighborhood of X, denoted by $N_G\left[X\right]$, is the set $N_G\left(X\right)\cup X$. A vertex of degree 0 is said to be isolated in G, while a vertex of degree one in G is called a leaf of G. The set of all leaves of G is denoted by $L_G$. We define a pendant edge of a graph to be an edge incident with a leaf. The corona of graphs H and F is a graph $H\circ F$ resulting from the disjoint union of H and $|V_H|$ copies of F in which each vertex v of H is adjacent to all vertices of the copy of F corresponding to v. The corona$H\circ K_1$, in particular, is the graph obtained from H by adding exactly one pendant edge to each vertex of H. A graph G is said to be a corona if G is the corona $H\circ K_1$ of some graph H. It is obvious that a corona is a graph in which each vertex is a leaf or it is adjacent to exactly one leaf.

We denote the path, cycle, and complete graph on n vertices by $P_n$, $C_n$, and $K_n$, respectively. The complete bipartite graph with one partite set of size n and the other of size m is denoted by $K_{n,m}$. A star is the tree $K_{1,k}$ for some $k\ge 1$. For $k,l\ge 1$, a double star$S(k,l)$ is the tree with exactly two vertices that are not leaves, one of which has k leaf neighbors and the other l leaf neighbors.

A vertex v is called a simplicial vertex of G if $N_G\left[v\right]$ is a complete graph, while it is a cut vertex if $G-v$ is disconnected. A block of a graph G is a maximal connected subgraph of G without its own cut vertices. We say that G is a block graph if every block of G is a complete graph (equivalently, every vertex of G is a simplicial or a cut vertex). A block of a block graph G is called a simplex if it contains at least one simplicial vertex of G, while it is an end block if it contains at most one cut vertex of G.

A subset D of $V_G$ is called a dominating set of G if every vertex belonging to $V_G-D$ is adjacent to at least one vertex in D. A subset I of $V_G$ is said to be independent if no two vertices belonging to I are adjacent in G. The cardinality of a largest (i.e., maximum) independent set of G, denoted by $\alpha \left(G\right)$, is called the independence number of G. Every largest independent set of a graph is called an $\alpha$-set of the graph. The independent domination number of G, denoted by $i\left(G\right)$, is the cardinality of a smallest independent dominating set of G (or equivalently, the cardinality of a minimum maximal independent set of vertices in G). The study of independent sets in graphs was begun by Berge [2,3] and Ore [4]. In 2013 Goddard and Henning published an article [5] that summarized results on independence domination in graphs. It is obvious that $i\left(G\right)\le \alpha \left(G\right)$ for any graph G. A graph G is a well-covered graph if $i\left(G\right)=\alpha \left(G\right)$. Equivalently, G is well-covered if every maximal independent set of G is a maximum independent set of G. The concept of well-covered graphs was introduced by Plummer [6] and extensively studied in many papers. We refer the reader to the excellent (but already old) survey on well-covered graphs by Plummer [7].

Now, between the integers $i\left(G\right)$ and $\alpha \left(G\right)$, we insert another integer concerning the existence and cardinality of independent sets in G. Formally, we introduce the concept of the common independence number of a graph G, denoted by ${\alpha }_c\left(G\right)$, as the greatest integer r such that every vertex of G belongs to some independent subset X of $V_G$ with $\left|X\right|\ge r$. Thus, the common independence number of a graph G refers to numbers of mutually independent vertices of G, and it emphasizes the notion of the individual independence of a vertex of G from other vertices of G. The common independence number ${\alpha }_c\left(G\right)$ of G is the limit of symmetry in G with respect to the fact that each vertex of G belongs to an independent set of cardinality ${\alpha }_c\left(G\right)$ in G, and there are vertices in G that do not belong to any larger independent set in G. For possible applications of the three parameters $i\left(G\right)$, $\alpha \left(G\right)$, and ${\alpha }_c\left(G\right)$ we refer the reader to the newest survey by Majeed and Rauf [8] on different applications of graph theory in computer science and social networks. It follows immediately from the above definitions (see also Proposition 1) that $i\left(G\right)\le {\alpha }_c\left(G\right)\le \alpha \left(G\right)$ for any graph G. In the following section, we present the first properties of the common independence number. Then, in the next two sections, we characterize the family of trees T for which $i\left(T\right)={\alpha }_c\left(T\right)$, and the family of block graphs G such that ${\alpha }_c\left(G\right)=\alpha \left(G\right)$, respectively. (We remark that the family of well-covered graphs is a proper subfamily of each of the previously mentioned families.)

For our studies of the common independence number of a graph, we begin from straightforward propositions and simple examples.

To better recognize connections between the independent domination number $i\left(G\right)$, the common independence number ${\alpha }_c\left(G\right)$, and the independence number $\alpha \left(G\right)$, we begin with simple examples. It is obvious that $i\left(K_n\right)={\alpha }_c\left(K_n\right)=\alpha \left(K_n\right)=1$ for every positive integer n. Similarly, if m and n are positive integers and $m\le n$, then $i\left(K_{m,n}\right)={\alpha }_c\left(K_{m,n}\right)=m\le \alpha \left(K_{m,n}\right)=n$. It is no problem to observe that $i\left(P_n\right)=\lceil n/3\rceil$, ${\alpha }_c\left(P_n\right)=\lfloor n/2\rfloor$, and $\alpha \left(P_n\right)=\lceil n/2\rceil$. Consequently, $i\left(P_n\right)<{\alpha }_c\left(P_n\right)<\alpha \left(P_n\right)$ if $n=2k+1$ and $k\ge 4$. On the other hand we have $i\left(C_n\right)=\lfloor n/3\rfloor \le {\alpha }_c\left(C_n\right)=\lceil (n-1)/2\rceil =\lfloor n/2\rfloor =\alpha \left(C_n\right)$ if $n\ge 3$. Let $G_k$ be a graph obtained from the corona $K_{1,k}\circ {\overline{K}}_2$ by inserting a new vertex into each non-pendant edge of $K_{1,k}\circ {\overline{K}}_2$, see Figure 1. Now it is easy to see that $i\left(G_k\right)=k+1$, ${\alpha }_c\left(G_k\right)=2k+1$, $\alpha \left(G_k\right)=3k+2$, and $i\left(G_k\right)<{\alpha }_c\left(G_k\right)<\alpha \left(G_k\right)$ if $k\ge 1$. Similarly, if $S^{*}\left(k,l\right)$ denotes a graph obtained from the double star $S(k,l)$ by inserting a new vertex into its only non-pendant edge, then it is obvious that $i\left(S^{*}\left(k,l\right)\right)=2$, ${\alpha }_c\left(S^{*}\left(k,l\right)\right)=min\{k,l\}+1$, and $\alpha \left(S^{*}\left(k,l\right)\right)=k+l+1$. From these examples it follows that the differences between numbers $i\left(G\right)$, ${\alpha }_c\left(G\right)$, and $\alpha \left(G\right)$ can be arbitrarily large.

The aim of the next theorem is to show for which positive integers m, n, and p satisfying the inequalities $m\le n\le p$ there exists a graph G such that $i\left(G\right)=m$, ${\alpha }_c\left(G\right)=n$, and $\alpha \left(G\right)=p$. This theorem again shows that the difference between the independence number and the common independence number as well as the difference between the common independence number and the independent domination number of a graph can be arbitrarily large.

In this section we consider graphs G for which $\alpha \left(G\right)={\alpha }_c\left(G\right)$; in particular we provide a constructive characterization of block graphs G for which $\alpha \left(G\right)={\alpha }_c\left(G\right)$. It follows from the next proposition that such graphs form the class of the $\alpha$-excellent graphs, that is, the class of graphs G in which every vertex belongs to some largest independent set of G. Thus, we are interested in characterizations of the $\alpha$-excellent graphs. The $\alpha$-excellent trees were already studied in [9,10]. We extend their characterizations to the $\alpha$-excellent block graphs, and we present some additional properties of the $\alpha$-excellent trees.

In order to state and prove our characterization of the $\alpha$-excellent block graphs, we present additional definitions and some preliminary results that we will need while proving the next two theorems. Let $K_n$ be a complete graph of order $n\ge 1$ with vertex set $\{v_1,\dots ,v_n\}$. If $k_1,\dots ,k_n$ are positive integers, then by $K_n^{k_1,\dots ,k_n}$ we denote a graph obtained from the disjoint union of the complete graphs $K_n,K_{k_1},\dots ,K_{k_n}$ by joining each vertex $v_i$ of $K_n$ with each vertex of $K_{k_i}$ for $i=1,\dots ,n$. The graph $K_n^{k_1,\dots ,k_n}$ is said to be a general corona of $K_n$ and the subgraph of $K_n^{k_1,\dots ,k_n}$ induced by the vertices $v_1,\dots ,v_n$ is called the body of $K_n^{k_1,\dots ,k_n}$. It is obvious that $K_n^{k_1,\dots ,k_n}$ has the property stated in the next observation.

Let $\mathcal{F}$ be the family of graphs that: (1) contains every complete graph of order at least 2; and (2) is closed under attaching general coronas, that is, if a graph $G^{\prime }$ belongs to $\mathcal{F}$ and $H=K_n^{k_1,\dots ,k_n}$ is a general corona, then to $\mathcal{F}$ belongs every graph obtained from the disjoint union $G^{\prime }\cup H$ by adding n edges that join one vertex of $G^{\prime }$ with the vertices forming the body of H. By $\mathcal{E}$ we denote the family (defined in [9]) of all trees belonging to $\mathcal{F}$. Thus, $K_2$ belongs to $\mathcal{E}$, and, if a graph $G^{\prime }$ belongs to $\mathcal{E}$ and K is a complete graph of order 2, then to $\mathcal{E}$ belongs every graph obtained from the disjoint union $G^{\prime }\cup K$ by adding exactly one edge that joins a vertex of $G^{\prime }$ with a vertex of K.

It is clear from the above definition that every graph belonging to the family $\mathcal{F}$ is a block graph. Figure 2 shows a block graph G belonging to $\mathcal{F}$ and a tree T that belongs to the subfamily $\mathcal{E}$ of $\mathcal{F}$.

We are now in position to prove the main result of this section, a constructive characterization of the $\alpha$-excellent block graphs.

Claim 1 implies that the diameter d of G is greater than 2. Let $P=(u_0,u_1,\dots ,u_d)$ be a longest path without chords in G. Let $B_i$ be that block of G which contains $u_i$ and $u_{i+1}$, $i=0,\dots ,d-1$. The choice of P and Claim 1 imply that the blocks $B_0,\dots ,B_{d-1}$ are distinct, $u_1,\dots ,u_{d-1}$ are cut vertices, while $u_0$ and $u_d$ are simplicial vertices belonging to the end blocks $B_0$ and $B_{d-1}$, respectively. Without loss of generality we assume that $V_{B_1}=\{u_1,u_2\}\cup \{w_1,\dots ,w_l\}$. (We remark that possibly $V_{B_1}=\{u_1,u_2\}$.) Since $B_0$ is a simplex and the blocks $B_0$ and $B_1$ share a vertex, $B_1$ is not a simplex (by Claim 1), and therefore each of the vertices $w_1,\dots ,w_l$ is a cut vertex. Let $B_1^{\prime },\dots ,B_l^{\prime }$ be blocks distinct from $B_1$ containing the vertices $w_1,\dots ,w_l$, respectively. The choice of P implies that $B_1^{\prime },\dots ,B_l^{\prime }$ are end blocks in G and they are unique (by Claim 1). Let H denote the subgraph of G induced by the vertices belonging to the blocks $B_0,B_1^{\prime },\dots ,B_l^{\prime }$. It is obvious that H is a general corona $K_m^{k_1,\dots ,k_m}$, where $m=l+1$, $k_1=|V_{B_0}|-1,k_2=|V_{B_1^{\prime }}|-1,\dots ,k_m=\left|V_{B_l^{\prime }}\right|-1$. Let $G^{\prime }$ denote the subgraph $G-V_H$ of G. Since G can be obtained from $G^{\prime }$ by (re)attaching the general corona H to the vertex $u_2$ in $G^{\prime }$, it follows from the second part of Proposition 5 that ${\alpha }_c\left(G^{\prime }\right)=\alpha \left(G^{\prime }\right)$. Thus, since $G^{\prime }$ has $n^{\prime }$ blocks, where $1\le n^{\prime }<n$, $G^{\prime }$ belongs to $\mathcal{F}$ by the inductive hypothesis. Consequently, G belongs to $\mathcal{F}$ (since G can be obtained from $G^{\prime }$ by attaching a general corona to a vertex in $G^{\prime }$).

In the following theorem (which partially follows from Theorem 2) we prove the equivalent properties that characterize the trees T with $\alpha \left(T\right)={\alpha }_c\left(T\right)$, that is, the $\alpha$-excellent trees.

In this section we are interested in recognizing the structure of trees in which the independence number i and the common independence number ${\alpha }_c$ are equal. In order to do this, we recall that a graph G is a well-covered graph if every maximal independent set of vertices of G is a largest independent set of G. Equivalently, G is well-covered if and only if $i\left(G\right)=\alpha \left(G\right)$. We begin with some basic observations on well-covered graphs. The first one follows directly from the definition of a well-covered graph. The second one—the characterization of well-covered trees—was proved by Ravindra [11].

In the next lemma we present a general property of the graphs G for which $i\left(G\right)={\alpha }_c\left(G\right)$.

We are now in position to present our characterization of trees for which the independence number i and the common independence number ${\alpha }_c$ are equal.