Lucky \(k\)-polynomials of null and complete split graphs

1. Introduction

It is assumed that the reader is familiar with the concept of graphs as well as that of a proper coloring of a graph. For general notation and concepts in graphs see [1,2,3]. For specific (new) notation used in this paper refer to [4,5]. By convention, if \(G\) has order \(n \geq 1\) and has no edges (\(\varepsilon(G)=0\)) then \(G\) is called a null graph denoted by, \(\mathfrak{N}_n\).

§2 deals with the introduction to Lucky \(k\)-polynomials. §2.1 presents Lucky \(k\)-polynomials for null graphs. In §3, some main results are presented in respect of complete split graphs and for generalized star graphs. Finally, in §4, a few suggestions on future research on this problem are discussed.

2. Lucky \(k\)-Polynomials

Recall from [6] that in an improper coloring an edge \(uv\) for which, \(c(u)=c(v)\) is called a bad edge. In [5] the notion of the chromatic completion number of a graph \(G\) denoted by, \(\zeta(G)\) was introduced. Also, recall from [5] that \(\zeta(G)\) is the maximum number of edges over all chromatic colorings that can be added to \(G\) without adding a bad edge.

Recall from [5] that a chromatic coloring in accordance with Lucky’s theorem or an optimal near-completion \(\chi\)-partition is called a Lucky \(\chi\)-coloring or simply a Lucky coloring denoted by, \(\varphi_{\mathcal{L}}(G)\).

For \(\chi(G) \leq n\leq \lambda\) colors the number of distinct Lucky \(k\)-colorings, \(\chi(G) \leq k\leq n\) is determined by a polynomial, called the Lucky \(k\)-polynomial, \(\mathcal{L}_G(\lambda,k)\). Lastly, recall the falling factorial, \(\lambda^{(n)}= \lambda(\lambda-1)(\lambda-2)\cdots (\lambda-n+1)\).

Corollary 1. For a graph \(G\) of order \(n\geq 1\), \(\lambda \geq n\) the Lucky \(n\)-polynomial is, \begin{equation}\mathcal{L}_{G}(\lambda,n)= \lambda^{(n)}= \binom{\lambda}{n}\cdots n!. \end{equation}

Proof. For any graph of order \(n \geq 1\), it follows that any proper \(n\)-coloring necessarily has \(\theta(c_i)=1\), \(\forall~i\). Therefore the result.

A trivial upper bound is observed.

Corollary 2. For any graph \(G\) of order \(n\), \(\mathcal{L}_{K_n}(\lambda,n) \leq \mathcal{P}_G(\lambda,n)\) where \(\mathcal{P}_G(\lambda,n)\) is the chromatic polynomial of \(G\).

Theorem 1. For a graph \(G\), \(\chi(G)\leq k’\leq k\leq \lambda\), it follows that, \begin{equation} \mathcal{L}_{G}(\lambda,k’) \leq \mathcal{L}_{G}(\lambda,k). \end{equation}

Proof. The result follows from the number theory result. For a \begin{equation} k’-tuple, (x_1,x_2,x_3,\dots,x_{k’}) \&nbsp such\&nbsp that\&nbsp \sum\limits_{i=1}^{k’}x_i =n \end{equation} and a \begin{equation} k-tuple, (y_1,y_2,y_3,\dots,y_k) \&nbsp such \&nbsp that\&nbsp \sum\limits_{i=1}^{k}y_i =n \end{equation} we have that, \begin{equation}\sum\limits_{i=1}^{k’-1}\prod\limits_{j=i+1}^{k’}x_ix_j \leq \sum\limits_{i=1}^{k-1}\prod\limits_{j=i+1}^{k}y_iy_j. \end{equation}

2.1. Lucky \(k\)-polynomials of null graphs

By convention let the vertices of a null graph of order \(n\geq 2\) be viewed as seated on the circumference of an imaginary circle and let the vertices be consecutively labeled \(v_i\), \(i=1,2,3,\dots,n\) in a clockwise fashion. Since \(\chi(\mathfrak{N}_n) = 1\) it is obvious that for a proper \(1\)-coloring there are exactly \(\lambda\) distinct proper \(1\)-colorings. Put differently, there are exactly \(\lambda\) distinct Lucky \(1\)-colorings. Hence, \(\mathcal{L}_{\mathfrak{N}_n}(\lambda, 1) = \lambda\). Similarly trivial, it follows that for a proper \(n\)-coloring there are \(\mathcal{L}_{\mathfrak{N}_n}(\lambda, n) = \lambda^{(n)}\) or \(\binom{\lambda}{n}n!\) such distinct Lucky \(n\)-colorings.

For the analysis of Lucky \(k\)-polynomials of null graphs of order \(n\geq 2\) and \(2\leq k \leq n-1\) we require a set theory perspective.

Case 1: As a special case we allow \(k=1\). For the set of vertices \(\{v_1,v_2\}\), we consider only Lucky \(1\)-colorings. As stated before there are \(\lambda\) such distinct Lucky \(1\)-colorings.

Case 2: For the set of vertices \(\{v_1,v_2,v_3\}\), we consider only Lucky \(2\)-colorings. For a Lucky \(2\)-coloring we consider the partitions: \begin{equation}\{\{v_1,v_2\},\{v_3\}\}, \{\{v_1,v_3\},\{v_2\}\}, \{\{v_2,v_3\},\{v_1\}\}. \end{equation} \begin{equation} Hence, \mathcal{L}_{\mathfrak{N}_3}(\lambda, 2) = 3\lambda^{(2)}= 3\lambda(\lambda-1). \end{equation}

Case 3: For the set of vertices \(\{v_1,v_2,v_3,v_4\}\), we consider both Lucky \(2\)-colorings and Lucky \(3\)-colorings. For a Lucky \(2\)-coloring we consider the partitions:

\begin{equation} \{\{v_1,v_2\},\{v_3,v_4\}\}, \{\{v_1,v_3\},\{v_2,v_4\}\}, \{\{v_1,v_4\},\{\{v_2,v_3\}\}. \end{equation} \begin{equation} Hence, \mathcal{L}_{\mathfrak{N}_4}(\lambda, 2) = 3\lambda^{(2)}= 3\lambda(\lambda-1). \end{equation} For a Lucky \(3\)-coloring we consider the partitions: \begin{equation}\{\{v_1,v_2\},\{v_3\},\{v_4\}\} , \{\{v_1,v_3\},\{v_2\},\{v_4\}\} , \{\{v_1,v_4\},\{v_2\},\{v_3\}\} ,\\ \{\{v_2,v_3\},\{v_1\},\{v_4\}\} , \{\{v_2,v_4\},\{v_1\},\{v_3\}\} , \{\{v_3,v_4\},\{v_1\},\{v_2\}\}. \end{equation} \begin{equation} Hence, \mathcal{L}_{\mathfrak{N}_4}(\lambda, 3) = 6\lambda^{(3)}= 6\lambda(\lambda-1)(\lambda-2). \end{equation}

Case 4: For the set of vertices \(\{v_1,v_2,v_3,v_4,v_5\}\), we consider Lucky \(2\)-colorings, Lucky \(3\)-colorings and Lucky \(4\)-colorings.

From Lucky’s theorem [5] it follows that for a Lucky \(2\)-coloring the partitions must have the form \(\{\{3\)-elements\(\},\{2\)-elements\(\}\}\). From the partitions in Case 3 it follows that \(6\) such partitions will follow. In addition \(4\) further \(2\)-element subsets of the form \(\{v_i,v_5\}\), \(i=1,2,3,4\) together with a unique corresponding \(3\)-element subset are 4 more partitions. Hence, \(10\) such partitions exist. \begin{equation} Therefore, \mathcal{L}_{\mathfrak{N}_5}(\lambda, 2) = 10\lambda^{(2)}= 10\lambda(\lambda-1). \end{equation} From Lucky’s theorem [5] it follows that for a Lucky \(3\)-coloring the partitions must have the form \(\{\{2\)-element\(\},\{2\)-element\(\},\{1\)-element\(\}\}\). From the partitions in Case 3 it follows that \(12\) such partitions will follow. In addition \(3\) further partitions of the form \(\{\{2\)-element\(\},\{2\)-element\(\},\{v_5\}\}\) are possible. The aforesaid follows from the partitions for a Lucky \(2\)-coloring in Case 3. \begin{equation} Hence, \mathcal{L}_{\mathfrak{N}_5}(\lambda, 3) = 15\lambda^{(3)}= 15\lambda(\lambda-1)(\lambda-2). \end{equation} From Lucky’s theorem [5] it follows that for a Lucky \(4\)-coloring the partitions must have the form \(\{\{2\)-element\(\},\{1\)-element\(\},\{1\)-element\(\},\{1\)-element\(\}\}\). There are \(\binom{5}{2}=10\) such \(2\)-element subsets. Each will correspond with its unique triple of \(1\)-element subsets. \begin{equation} Hence, \mathcal{L}_{\mathfrak{N}_5}(\lambda, 4) = 10\lambda^{(4)}= 10\lambda(\lambda-1)(\lambda-2)(\lambda-3). \end{equation}

Observation 1. The Lucky \(k\)-polynomial for a null graph \(\mathfrak{N}_n\) has the trivial form i.e. \(\mathcal{L}_{\mathfrak{N}_n}(\lambda, k) = m_{\mathfrak{N}_n}(n,k)\cdots \lambda^{(k)}\) with \(m_{\mathfrak{N}_n}(n,k)\) some positive integer for \(k\in\{1,2,3,\dots,n\}\) and \(n=1,2,3,\dots\). Furthermore, it is conjectured that if \(G\) permits a \(k\)-coloring then the Lucky \(k\)-polynomial has the form \(\mathcal{L}_G(\lambda, k) = m_G(n,k)\cdot \lambda^{(k)}\) with \(m_G(n,k)\) some positive integer. Note that \(m_G(n,k)\leq S(n,k)\) where \(S(n,k)\) is the corresponding Stirling number of the second kind (or Stirling partition number). These subsets of specialized numbers, \(m_G(n,k)\), are called the family of Lucky numbers.

2.2. Lucky \(2\)-polynomials of null graphs

It is evident that Cases 1 to 4 present an inefficient way of determining the value of \(m_{\mathfrak{N}_n}(n,k)\). The approach in this subsection is to present a recursive result for Lucky \(2\)-colorings. We summarize the Lucky \(2\)-coloring results above as a corollary.

Corollary 3.

• (a) For \(n=1\), \(\mathcal{L}_{\mathfrak{N}_1}(\lambda,2) = 0\).
• (b) For \(n=2\), \(\mathcal{L}_{\mathfrak{N}_2}(\lambda,2) = \lambda(\lambda-1)\).
• (c) For \(n=3\), \(\mathcal{L}_{\mathfrak{N}_3}(\lambda,2) = 3\lambda(\lambda-1)\).
• (d) For \(n=4\), \(\mathcal{L}_{\mathfrak{N}_4}(\lambda,2) = 3\lambda(\lambda-1)\).
• (e) For \(n=5\), \(\mathcal{L}_{\mathfrak{N}_5}(\lambda,2) = 10\lambda(\lambda-1)\).

Theorem 2. For a null graph \(\mathfrak{N}_n\), \(n= 6,7,8,\cdots\) we have

• (a) If \(n\) is odd then, \begin{equation}\mathcal{L}_{\mathfrak{N}_n}(\lambda,2) = 2\mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda,2) + \binom{n-1}{\frac{n-3}{2}}\lambda(\lambda-1). \end{equation}
• (b) If \(n\) is even then, \begin{equation}\mathcal{L}_{\mathfrak{N}_n}(\lambda,2) = \mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda,2). \end{equation}

Proof.

• (a) If \(n\) is odd then \(n-1\) is even. So the number of Lucky \(2\)-colorings of \(\mathfrak{N}_{n-1}\) results from the number of partitions of the form \begin{equation}\Big\{\Big\{\frac{(n-1)}{2} -element \Big\},\Big\{\frac{(n-1)}{2} -element \Big\}\Big\}\&nbsp in \&nbsp respect \&nbsp of \Big\{v_i:i=1,2,3,\dots,v_{n-1}\Big\}. \end{equation} Hence, there are exactly \(2m_{\mathfrak{N}_{n-1}}((n-1),2)\) partitions which will be obtained from the consecutive union of \(\Big\{v_n\Big\}\) with each of the \(\frac{(n-1)}{2}\)-element subsets in each partition to obtain partitions of the form \begin{equation}\Big\{\Big\{\frac{(n+1)}{2} -element \Big\},\Big\{\frac{(n-1)}{2} -element \Big\}\Big\}\&nbsp in \&nbsp respect \&nbsp of\Big\{v_i:i=1,2,3,\dots,v_n\Big\}. \end{equation} Therefore, the term \(2\mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda, 2)\) in the result. Finally the number of distinct \(\frac{(n-1)}{2}\)-element subsets which has the vertex element \(v_n\) together with each unique corresponding \(\frac{(n+1)}{2}\)-element subset must be added as \begin{equation}\Big\{\Big\{\frac{(n+1)}{2} -element \Big\},\Big\{\frac{(n-1)}{2} -element \Big\}\Big\} \end{equation} partitions. Hence, the element \(v_n\) can be added to each of the \(\binom{n-1}{\frac{n-3}{2}}\)-element subsets from the vertex set \(\Big\{v_i: i=1,2,3,\dots,v_{n-1}\Big\}\). Therefore, through immediate induction the result follows.
• (b) If \(n\) is even then \(n’=n-1\) is odd. The partitions of the vertex set \(\Big\{v_1,v_2,v_3,\dots,v_{n-1}\Big\}\) are of the form \begin{equation}\Big\{\Big\{\frac{n}{2} -element \Big\},\Big\{\lfloor \frac{(n-1)}{2}\rfloor -element \Big\}\Big\}. \end{equation} Therefore, by the union of \(\Big\{v_n\Big\}\) and each of the \(\Big\{\lfloor \frac{(n-1)}{2}\rfloor\)-element\(\Big\}\) subsets in the \(m_{\mathfrak{N}_{n-1}}((n-1),2)\) partitions, the required \(m_{\mathfrak{N}_{n-1}}((n-1),2)= m_{\mathfrak{N}_n}(n,2)\) partitions of the form \begin{equation}\Big\{\Big\{\frac{n}{2} -element \Big\},\Big\{\frac{n}{2} -element \Big\}\Big\}\&nbsp in \&nbsp respect \&nbsp of\Big\{v_i: i=1,2,3,\dots,n\Big\} \end{equation} are obtained. Therefore, through immediate induction the result follows.

2.3. Lucky \(3\)-polynomials of null graphs

In this subsection we present a recursive result for Lucky \(3\)-colorings. We summarize the Lucky \(3\)-coloring results above as a corollary.

Corollary

• (a) For \(n=1\), \(\mathcal{L}_{\mathfrak{N}_1}(\lambda,3) = 0\).
• (b) For \(n=2\), \(\mathcal{L}_{\mathfrak{N}_2}(\lambda,3) = 0\).
• (c) For \(n=3\), \(\mathcal{L}_{\mathfrak{N}_3}(\lambda,3) = \lambda(\lambda-1)(\lambda-2)\).
• (d) For \(n=4\), \(\mathcal{L}_{\mathfrak{N}_4}(\lambda,3) = 6\lambda(\lambda-1)(\lambda-2)\).
• (e) For \(n=5\), \(\mathcal{L}_{\mathfrak{N}_5}(\lambda,3) = 15\lambda(\lambda-1)(\lambda-2)\).

Partition the set of positive integers into subsets, \( X_1=\{i: i=6+3t, t=0,1,2,\dots\}\), \(X_2 = \{i: i=7+3t, t=0,1,2,\dots\}\) and \( X_3=\{i: i=8+3t, t=0,1,2,\dots\}\).

Theorem 3. For a null graph \(\mathfrak{N}_n\), \(n= 6,7,8,\cdots\), we have

• (a) If \(n \in X_1\) then, \(\mathcal{L}_{\mathfrak{N}_n}(\lambda,3) = \mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda, 3)\).
• (b) If \(n \in X_2\) then, \(\mathcal{L}_{\mathfrak{N}_n}(\lambda,3) = 3\mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda,3) + \binom{n-1}{\frac{n-4}{3}}\lambda(\lambda-1)(\lambda-2)\).
• (c) If \(n \in X_3\) then, \(\mathcal{L}_{\mathfrak{N}_n}(\lambda,3) = 2\mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda,3) + \binom{n-1}{\frac{n-5}{3}}\lambda(\lambda-1)(\lambda-2)\).

Proof.

• (a) If \(n \in X_1\), then the partitions of the vertex set \(\Big\{v_1,v_2,v_3,\dots,v_n\Big\}\) are of the form \begin{equation}\Big\{\Big\{\frac{n}{3} -element \Big\},\Big\{\frac{n}{3} -element \Big\},\Big\{\frac{n}{3} -element \Big\}\Big\}. \end{equation} Therefore, the partitions of \(\Big\{v_1,v_2,v_3,\dots,v_{n-1}\Big\}\) are of the form \begin{equation}\Big\{\Big\{\frac{n}{3} -element \Big\},\Big\{\frac{n}{3} -element \Big\},\Big\{(\frac{n}{3}-1) -element \Big\}\Big\}. \end{equation} From the union of \(\Big\{v_n\Big\}\) and each of the \(\Big\{(\frac{n}{3}-1)\)-element\(\Big\}\Big\}\) subsets in the \(m_{\mathfrak{N}_{n-1}}((n-1),3)\) partitions, the required \(m_{\mathfrak{N}_{n-1}}((n-1),3)= m_{\mathfrak{N}_n}(n,3)\) partitions of the form \begin{equation}\Big\{\Big\{\frac{n}{3} -element \Big\},\Big\{\frac{n}{3} -element \Big\},\Big\{\frac{n}{3} -element \Big\}\Big\}\&nbsp in \&nbsp respect \&nbsp of\Big\{v_i: i=1,2,3,\dots,n\Big\} \end{equation} are obtained. Therefore, through immediate induction the result follows.
• (b) If \(n \in X_2\), then the partitions of the vertex set \(\Big\{v_1,v_2,v_3,\dots,v_n\Big\}\) are of the form \begin{equation}\Big\{\Big\{(\frac{n-1}{3}+1) -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\}\Big\}. \end{equation} Therefore, the partitions of \(\Big\{v_1,v_2,v_3,\dots,v_{n-1}\Big\}\) are of the form \begin{equation}\Big\{\Big\{\frac{n-1}{3} -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\}\Big\}. \end{equation} From the union of \(\Big\{v_n\Big\}\) and each of the \(\Big\{\frac{(n-1)}{3}\)-element\(\Big\}\) subsets in each partition, exactly \(3m_{\mathfrak{N}_{n-1}}((n-1),3)\) partitions of the form \begin{equation}\Big\{\Big\{(\frac{n-1}{3}+1) -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\}\Big\} \end{equation} are obtained. Hence, the term \(3\mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda, 3)\). Finally the number of distinct \(\Big\{\frac{(n-1)}{3}\)-element\(\Big\}\) subsets which has the vertex element \(v_n\) together with each unique corresponding \((\frac{(n+1)}{3}+1)\)-element subset must be added as \begin{equation}\Big\{\Big\{(\frac{(n+1)}{3}+1) -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\},\Big\{\frac{(n-1)}{3} -element \Big\}\Big\} \end{equation} partitions. Hence, the element \(v_n\) can be added to each of the \(\binom{n-1}{\lfloor \frac{n}{3}\rfloor-1}\)-element subsets from the vertex set \(\Big\{v_i: i=1,2,3,\dots,v_{n-1}\Big\}\) to obtain the term \(\binom{n-1}{\frac{n-4}{3}}\lambda(\lambda-1)(\lambda-2)\). Therefore, through immediate induction the result follows.
• (c) This result follows through similar reasoning as part (b).

We are ready to give a main result.

Theorem 4. For \(4 \leq k \leq \lambda\), let \(n\geq k\), \(X_1= \{i:i=k(t+1), t=0,1,2,\dots\}\) and \(X_2= \Bbb{N}\backslash X_1\). It follows that,

• (a) If \(\lambda \geq k > n\), then \(\mathcal{L}_{\mathfrak{N}_n}(\lambda,k) = 0\).
• (b) If \(4 \leq k \leq n \leq \lambda\) and \(n \in X_1\), then \(\mathcal{L}_{\mathfrak{N}_n}(\lambda,k) = \mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda,k)\).
• (c) If \(4 \leq k \leq n \leq \lambda\) and \(n \in X_2\) let \(\frac{n}{k}= \lfloor \frac{n}{k}\rfloor + r\), \(0 < r \leq (k-1)\), then \(\mathcal{L}_{\mathfrak{N}_n}(\lambda,k) = (k-r)\mathcal{L}_{\mathfrak{N}_{n-1}}(\lambda,k) + \binom{n-1}{\frac{n-(r+k)}{k}}\lambda^{(k)}\).

Proof. Point (a) is trivial. Points (b) and (c) can be proved by similar reasoning as in the proofs of Theorems 2 and 3.

3. Lucky \(k\)-polynomials of complete split graphs

For certain graphs the Lucky \(k\)-polynomials follow trivially. Note that for a graph \(G\) the lower bound \(k \geq \chi(G)\) applies. We present a corollary without proof. Recall that a star \(S_{1,n}\) has a central vertex say \(u_1\) which is adjacent to each vertex in the independent set of vertices \(\{v_i:1\leq i\leq n\}\).

Corollary 5. For the star \(S_{1,n}\), \(n\geq 1\) and \(2\leq k \leq \lambda\), it follows that, \begin{equation}\mathcal{L}_{S_{1,n}}(\lambda,k) = \lambda \mathcal{L}_{\mathfrak{N}_n}(\lambda,k-1). \end{equation}

Recall that, a split graph is a graph in which the vertex set can be partitioned into a clique and an independent set. Note that a null graph and a star graph, \(S_{1,n}\) are relatively simple split graphs.

A complete split graph is a split graph such that each vertex in the independent set is adjacent to all the vertices of the clique (the clique is a smallest clique which permits a maximum independent set). Note that a complete graph \(K_n\) is also a complete split graph i.e. any subset of \(n-1\) vertices induces a smallest clique and the corresponding \(1\)-element subset is a maximum independent set.

Lemma 1. For a complete split graph \(G \neq K_n\), \(n\geq 3\), both the maximum independent set and the corresponding clique are unique.

Proof. Consider a clique \(Q\) and the corresponding maximum independent set \(X\) of \(G\). If it is possible to obtain another independent set say, \(X’= X\cup v_i\), \(v_i \in V(Q)\) then \(V(G)\) was not partitioned in accordance to the definition of a split graph because no \(v_j\in X\) is adjacent to \(v_i\). Similarly, \(V(Q) \cup v_k\), \(v_k\in X\) is not possible. Therefore, both the independent set and the clique are unique.

Theorem 5. Let \(X\) be the independent set in a complete split graph \(G \neq K_n\) and let the clique \(K_t\) correspond to \(\langle X \rangle\) in \(G\). Let \(t+1 \leq k \leq \lambda\). Then, \begin{equation}\mathcal{L}_G(\lambda,k) = \lambda^{(t)}\mathcal{L}_{\mathfrak{N}_{n-t}}(\lambda-t,k-t). \end{equation}

Proof. It follows that any Lucky coloring of \(K_t\) necessitates a \(t\)-coloring. From the completeness between \(K_t\) and \(\langle X\rangle\) (a \((n-t)\)-null graph) it follows that only a \((k-t)\)-coloring from amongst \(\lambda-t\) colors can be assigned to the vertices of \(X\). From Corollary 5 and Lemma 1, the result follows through immediate induction for any complete split graph.

A generalized star is defined as, a graph \(G\) which can be partitioned into an independent set \(X\) and a subgraph \(G’\) (not necessarily connected) such that each vertex \(u_i \in V(G’)\) is adjacent to all vertices in \(X\). Note that a complete split graph is also a generalized star.

Lemma 2. For a generalized star \(G \neq K_n\), \(n\geq 3\) the maximum independent set \(Y\) is, either \(Y=X\) or \(Y\subseteq V(G’)\) and the corresponding subgraph \(G’\) is unique.

Proof. By similar reasoning to that in the proof of Lemma 1.

Theorem 6. Let \(X\) be the independent set in a generalized star \(G \neq K_n\) and let the subgraph \(G’\) of order \(t\) correspond to \(\langle X \rangle\) in \(G\). Let \(t+1 \leq k \leq \lambda\). Then, \begin{equation}\mathcal{L}_G(\lambda,k) = max\{\mathcal{L}_{G’}(\lambda,\ell)\cdots \mathcal{L}_{\mathfrak{N}_{n-t}}(\lambda-\ell,k-\ell) \&nbsp for \&nbsp some \&nbsp \chi(G’)\leq \ell \leq k-1\}. \end{equation}

Proof. Assume \(|V(G’)| = t\). It follows that any Lucky coloring of \(G’\) can at most be a \(t\)-coloring. From the completeness between \(G’\) and \(\langle X\rangle\) (a \((n-t)\)-null graph) it follows that for a Lucky \(k\)-coloring any color set \(\mathcal{C}\), \(\mathcal{C}’ \subseteq \mathcal{C}\) requires a \(2\)-partition into say \begin{equation}\{\{\ell -element \},\{(k-\ell) -element \}\}. \end{equation} From [5] it follows that the existence of an optimal near-completion \(\ell\)-partition of \(V(G’)\) will yield a corresponding Lucky coloring of \(G’\) yielding \(\zeta(G’)\). Because \(\zeta(G’) + \zeta(\mathfrak{N}_{n-t})\) must be maximized and maximization is always possible, the result follows through immediate induction.

Note that, Theorem 6 can immediately be generalized to the join operation between graphs \(G\), \(H\). We state it without proof because the reasoning of proof is similar to that found in the proof of Theorem 6.

Theorem 7. For the graphs \(G\) and \(H\) it follows that, \begin{equation}\mathcal{L}_{G+H}(\lambda,k) = max\{\mathcal{L}_{G}(\lambda,\ell)\cdots \mathcal{L}_{H}(\lambda-\ell,k-\ell)\&nbsp for \&nbsp some \&nbsp\chi(G)\leq \ell \leq k-1\}. \end{equation}

4. Conclusion

From Theorem 7, it follows naturally to seek a result for the corona operation between two graphs. Other interesting problems are,

Problem 1. Find a closed formula, if such exists, for the family of Lucky numbers, \(m_G(n,k)\) for \(\chi(G) \leq k \leq \lambda\) and \(n\in \Bbb{N}\).

Problem 2. Find an efficient algorithm to find \begin{equation}\mathcal{L}_{G+H}(\lambda,k) = max\{\mathcal{L}_{G}(\lambda,\ell)\cdots \mathcal{L}_{H}(\lambda-\ell,k-\ell)\&nbsp for \&nbsp some \&nbsp\chi(G)\leq \ell \leq k-1\}. \end{equation}

Problem 3. Use Theorem 6 to formulate and proof a generalized result for complete \(q\)-partite graphs.

Problem 4. Find an efficient algorithm to find the Lucky \(k\)-polynomials of complete \(q\)-partite graphs.

Acknowledgments

The author would like to thank the anonymous referees for their constructive comments, which helped to improve on the elegance of this paper.

Conflicts of Interest:

The author declares no conflict of interest.