A directed star is a star digraph in which the centre is either a sink or a source. With every directed star, we associate a weight \(w\left(\alpha\right)\). Let \(D\) be a digraph; and \(C\), a spanning subgraph of \(D\); in which every component is a directed star. Then \(C\) is called a directed star cover of \(D\), and the weight of \(C\) is \(w(C)=\prod_{\alpha}w\left(\alpha\right)\), where the product is taken over all the components \(\alpha\) of \(C\). The directed star polynomial of \(D\) is \[E\left(D;\mathbf{w}\right)=\sum w(C),\] where the sum is taken over all the directed star covers of \(D\). The paper establishes properties of star polynomials and establishes relationships between star polynomials, source polynomials (where all components are source stars), and sink polynomials (where all components are sink stars). Furthermore, it presents methods to compute these polynomials for general digraphs. We derive formulae for the star polynomials of rooted products of digraphs. Moreover, we establish applications of these polynomials to several domination parameters and obtain results regarding these polynomials and independent sets in undirected graphs.
A (undirected) star is a tree consisting of a node – called its centre, joined to all the other nodes- called its tips. A star (digraph) is a digraph whose underlying graph is a star. A directed star is a star digraph in which the centre is either a sink or a source. If the centre is a sink, then the star is a sink star. If the centre is a source, the star is a source star. A star with \(n\) nodes, is called an \(\boldsymbol{n}\)-star. When \(n=2\), the star can be regarded as either a source star or a sink star.
Let \(F\) be the family of directed stars. With every member \(\alpha\) of \(F\), we associate a weight \(w\left(\alpha\right)\). Let \(D\) be a digraph; and \(C\), a spanning subgraph of \(D\); in which every component belongs to \(F\). Then \(C\) is called a star cover of \(D\), and the weight of \(C\) is \(w(C)=\prod_{\alpha}w\left(\alpha\right)\), where the product is taken over all the components \(\alpha\) of \(C\). The directed star polynomial of \(D\) is \[E\left(D;\mathbf{w}\right)=\sum w(C),\] where the sum is taken over all the directed star covers of \(D\). This polynomial is an example of an F-polynomial. The F-polynomial (also known as the Farrell polynomial [13]) was introduced in [4], and has been extensively researched [5].
Note that star covers have also been called star factors [1, 10, 11].
The indegree of a node \(v\) will be denoted by \(\mathbf{id(v)}\). The outdegree of a node \(v\) will be denoted by \(\mathbf{od(v)}\). We denote the directed edge from node \(u\) to \(v\), as \(\overrightarrow{uv}\) .
When F is the family of directed stars, the resulting F-polynomial, is the (directed) star polynomial of \(D\), and is denoted by \(E(D,\mathbf{w})\). Note that a component node is a star with one node; and a component edge is a star with two nodes. A star with more than two nodes is called a proper star.
When \(F\) is the family of sink stars, a cover is a sink (star) cover. In this case, \(F\left(D;\mathbf{w}\right)\), is the sink polynomial; and is denoted by \(\overset{\vee}{E}\left(D;\mathbf{w}\right)\). When \(F\) is the family of source stars, a cover is a source (star) cover. In this case, \(F\left(D;\mathbf{w}\right)\), is the source polynomial of \(D\); and is denoted by \(\widehat{E}\left(D;\mathbf{w}\right)\).
In the case of undirected graphs, the analogous polynomials, i.e. when F is the family of undirected stars, have been extensively investigated ([3, 6], and [7]). Its applications include graph reconstruction [2], assignment problems and discrete random allocation problems [8].
Star covers of tournaments have been studied in [1]. A variation of the domination number called the bounded domination number of tournaments has been studied in [12] using star covers.
A \(k\)-bounded star packing of a graph \(G\), is a subgraph of G consisting of vertex-disjoint components where each component is a star having at least one but no more than \(k\) edges. These subgraphs were studied in [11].
We establish results about basic characteristics of star polynomials, in Section 2. We then establish generating functions and recurrences for the various tar polynomials of symmetric paths, a class of digraphs obtained from undirected paths by replacing each edge with two oppositely oriented edges.
Similar results are obtained in Section 5, for the class of Transitive tournaments, as well as for a related class of tournaments.
In Section 6, we establish results for star polynomials of a generalization of rooted products of digraphs. Rooted products are a special digraph product introduced by Godsil and Mckay in [9]. Results about a special version of this digraph product are derived in Section 7, which includes the special case of oriented stars.
Finally, in Section 8, we establish that the out-domination and in-dominations number sof a digraph \(D\) can be derived from the star polynomial and the source polynomial of \(D\). We also establish that certain coefficients of the source polynomial give the number of \(k\)-bounded star packings, for \(1\leq k \leq n\). We now present applications of star covers and their associated polynomials to the study of \(k\)-Exact 1-Total Dominating Sets. Additionally, we present a result linking the cardinalities of neighbourhoods of independent sets to the sizes of the sets themselves. These findings enhance the understanding of the interplay between domination parameters, independent sets, and various star polynomial structures.
The polynomials obtained by specifying the weight assignment are considered various specializations of the Directed Star Polynomial. In this subsection, we introduce the specializations that will be discussed in later sections, as well as basic results.
The following result is immediate from the definitions.
Theorem 2.1. Let \(D\) be a digraph. If the weight assigned to every source star (sink star) is zero, then \(E(D,\mathbf{w})\) is a sink polynomial (source polynomial) of \(D\).
Let us assign to each member of \(F\) with \(n\) nodes, the weight \(w_{n}\); then the corresponding vector of weights \(\left(w_{1},w_{2},w_{3},\cdots\right)\) is denoted by \(\underline{w}\); and the corresponding \(F\)-polynomial \(F(D;\underline{w})\) is called the general node-weighted \(F\)-polynomial of \(D\). The undirected analogue of the general node-weighted polynomial was introduced in [3]. The general node-weighted polynomials for source stars and sinks stars, are denoted by \(\widehat{E}(D;\underline{w})\) and \(\overset{\vee}{E}(D;\underline{w})\), respectively.
Another weight assignment is as follows. A source star with \(n\) nodes is assigned a weight \(x_{n}\); and a sink star with \(n\)(\(>2\)) nodes; a weight \(y_{n}\). Since sink stars of orders 1 and 2 are also source stars, they will be assigned weights \(x_{1}\) and \(x_{2}\), respectively. Let \(\underline{x}=\left(x_{1},\,x_{2},\,\ldots,x_{n}\right)\) and \(\underline{y}=\left(y_{3},y_{4},\ldots,y_{n}\right)\). Then \(\mathbf{w}\) is now \((\underline{x},\underline{y})\). The resulting directed star polynomial is denoted by \(E(D;(\underline{x},\underline{y}))\).
The following result can be used to obtain the general node-weighted polynomials \(\overset{\vee}{E}(D;\underline{w})\) and \(\widehat{E}(D;\underline{w})\), from the polynomial \(E(D;(\underline{x},\underline{y}))\). It follows immediately from the above definitions.
Theorem 2.2.
(i) \(\widehat{E}(D;\underline{w})=E(D;(w_{1},w_{2},\ldots,w_{n}),(0,0,\ldots,0))\),
(ii) \(\overset{\vee}{E}(D;\underline{w})=E(D;(w_{1},w_{2},0,\ldots,0),\,(w_{3},w_{4},0,\ldots,0))\).
Proof. By putting \(y_{i}=0\), for all \(i\), we remove any contributions from covers with any proper sink star component. Thus, the contributing covers are now only covers with components that can be classified as source stars (including component nodes and edges). Thus putting \(x_{i}=w_{i}\), for all \(i\), and summing the weights of the contributing covers yields by definition the polynomial \(\widehat{E}(D;\underline{w})\).
By putting \(x_{i}=0\), for all \(i\ge3\), we remove any contributions from covers with any proper source star component. Thus, the contributing covers are now only covers with components that can be classified as sink stars (including component nodes and edges). Thus putting \(x_{i}=w_{i}\), for all \(i\leq2\), \(y_{i}=w_{i}\) for all \(i\geq3\), and summing the weights of the contributing covers yields by definition the polynomial \(\overset{\vee}{E}(D;\underline{w})\). ◻
Theorem 2.3. Let \(D\) be a digraph with \(p\) nodes and \(q\) (non-loop) edges. Then \(E(D;(\underline{x},\underline{y}))\) has the following properties.
(i) The coefficient of \(x_{1}^{p}\) is 1.
(ii) The coefficient of \(x_{1}^{p-2}x_{2}\) is \(q\).
(iii) The coefficient of \(x_{1}^{p-k}x_{k}\) is the number of subgraphs of \(D\), which are source stars with \(k\) nodes.
(iv) For \(k\geq3\), the coefficient of \(x_{1}^{p-k}y_{k}\) is the number of subgraphs of \(D\), which are sink stars with \(k\) nodes.
(v) The coefficient of \(x_{p}\) is the number of spanning source stars.
(vi) For \(p(\geq3)\), the coefficient of \(y_{p}\) is the number of spanning sink stars.
Proof. (i) There is a unique cover with all components being component nodes, so the coefficient of \(x_{1}^{p}\) is 1.
(ii) For every edge, there is a cover with that edge as an edge component and all other components being components. Since the number of edges is \(q\) and given that the coefficient of \(x_{1}^{p-2}x_{2}\) is the number of such covers, the result of part (ii) follows.
(iii) By using a similar argument to part (ii) and by using source stars with \(k\) nodes instead of edges, we obtain the result given in part (iii).
(iv) Similarly, if we use sink stars with \(k\) nodes instead of edges, we obtain the result given in part (iv).
(v, vi) The weight \(x_{p}\) (resp. \(y_{p}\)) is assigned to a source star with \(p\) nodes, thus such a star is comprised of all the nodes of \(D\) and so is a spanning subgraph of \(D\).
(vi) The centres of the stars of a source cover dominate all the other nodes of \(D\). ◻
The following result is also immediate from the definitions. It gives some basic properties of sink polynomials and source polynomials.
Theorem 2.4. Let \(D\) be a digraph with \(p\) nodes and \(q\) (non-loop) edges. Then \(\widehat{E}(D;\underline{w})\) and \(\overset{\vee}{E}(D;\underline{w})\) have the following properties:
(i) The coefficient of \(w_{1}^{p}\) is 1.
(ii) The coefficient of \(w_{1}^{p-2}w_{2}\) is \(q\).
(iii) The coefficient of \(w_{p}\), is the number of spanning stars.
(iv) If the least power of \(w_{1}\) in the source polynomial (sink polynomial) polynomial of \(D\), is \(r\), then the greatest out-degree (in-degree) of any node in \(D\), is \(p-r\).
The following result is also immediate from the definitions. It gives some basic properties of sink polynomials and source polynomials.
Let \(r\) be the largest positive integer, such that \(x_{r}\) belongs to a monomial in \(E(D;(\underline{x},\underline{y}))\). Then, \(D\) has a cover consisting of an \(r\)-star, together with \(p-r\) component nodes. By deleting \(j\) (\(\leq r-2\)) edges, we obtain a cover consisting of a source star with \(r-j\) nodes, together with \(p-(r-j)\) component nodes. Then, amongst the covers with such a component, there exists a cover in which the other components are nodes. Hence, we have the following result.
Theorem 2.5. Let \(r\) be the greatest positive integer for which the weight \(x_{r}\) appears in at least one monomial of the polynomial \(E(D;(\underline{x},\underline{y}))\). Then, all terms of the form \(x_{1}^{p-k}x_{k}\) (\(2\leq k\leq r\)) occur in \(E(D;(\underline{x},\underline{y}))\), with non-zero coefficients.
Using a similar argument, we easily deduce the following result.
Theorem 2.6. Let \(r\)(\(\geq3\)) be the greatest positive integer for which the weight \(y_{r}\) appears in at least one monomial of the \(E(D;(\underline{x},\underline{y}))\). Then all terms of the form \(x_{1}^{p-k}y_{k}\) (\(3\leq k\leq r\)) occur in \(E(D;(\underline{x},\underline{y}))\), with non-zero coefficients.
Theorem 2.2, together with Theorems 2.5 and 2.6; yields the following result.
Theorem 2.7. Let \(D\) be a digraph. Then \(\widehat{E}(D;\underline{w})\) and \(\overset{\vee}{E}(D;\underline{w})\) have the following property.
If \(r\) is the largest positive integer, such that \(w_{r}\) belongs to a monomial; then all terms of the form \(w_{1}^{p-k}w_{k}\) (\(2\leq k\leq r\)) occur with non-zero coefficients.
In this section, we establish two types of recurrence relations for \(E(D;\underline{w})\). The first type is based on deleting and incorporating nodes, while the second involves deleting and incorporating edges. Let \(H\) be a subgraph of a digraph \(D\), then \(D^{\prime}(H)\) denotes the digraph obtained from \(D\), by removing the nodes of \(H\).
The following result is the Fundamental Node Theorem ([4]), in the case of star covers.
Theorem 3.1. Let \(D\) be a digraph containing a node \(z\). Then:
\[\begin{aligned} E(D;\mathbf{w}) & = w(z) E\bigl(D^{\prime}(z);\mathbf{w}\bigr) + \sum\limits_{\beta} w(\beta) \, E\bigl(D^{\prime}(\beta);\mathbf{w}\bigr) \\ & \quad + \sum\limits_{\gamma} w(\gamma) \, E\bigl(D^{\prime}(\gamma);\mathbf{w}\bigr) + \sum\limits_{\delta} w(\delta) \, E\bigl(D^{\prime}(\delta);\mathbf{w}\bigr)\,, \end{aligned}\] where the first summation is taken over all stars \(\beta\) with two nodes including \(z\). The second summation is taken over all proper source stars \(\gamma\) containing \(z\). The third summation is taken over all proper sink stars \(\delta\) containing \(z\).
Proof. When \(F\) is a family of stars, a member of the family with one node, is a node. A member with two nodes, is an edge. A member with more two nodes, is either (i) a proper source star or (ii) a proper sink star. Hence, the result follows from the Fundamental Node Theorem. ◻
When \(\mathbf{w}\) is \(\left(\underline{x},\underline{y}\right)\), we have the following result.
Theorem 3.2 . Let \(D\) be a digraph containing a node \(z\). Then \[\begin{aligned} E\bigl(D;(\underline{x},\underline{y})\bigr) =& x_{1} E\bigl(D^{\prime}(z);(\underline{x},\underline{y})\bigr) + \sum\limits_{\overrightarrow{uv}} x_{2} E\bigl(D^{\prime}(u,v);(\underline{x},\underline{y})\bigr) \\ &+ \sum\limits_{\gamma} x_{|\gamma|} E\bigl(D^{\prime}(\gamma);(\underline{x},\underline{y})\bigr) + \sum\limits_{\delta} y_{|\delta|} E\bigl(D^{\prime}(\delta);(\underline{x},\underline{y})\bigr), \end{aligned}\] where the first summation is taken over all edges \(\overrightarrow{uv}\), where \(u=z\) or \(v=z\). The second summation is taken over all proper source stars \(\gamma\) containing \(z\); and the third summation is taken over all proper sink stars \(\delta\) containing \(z\).
Proof. In this case, a node has weight \(w_{1}\); and the weight of an edge is \(w_{2}\). If a proper source star \(\gamma\) has \(|\gamma|\) nodes, then its weight is \(x_{|\gamma|}\). A proper sink star \(\delta\) with \(|\delta|\) nodes has weight \(y_{|\delta|}\). The result then follows from Theorem 3.1. ◻
Note that in this paper, we denote the directed edge from node \(u\) to \(v\), as \(\overrightarrow{uv}\) .
Definition 3.3. Let \(D\) be a digraph. An edge that is required to belong to every star cover of \(D\), is called incorporated. The resulting graph with one or more incorporated edges, is called a restricted digraph, and is noted by \(D^{*}\).
Let \(D\) be a digraph containing an edge \(e\). Partition the star covers of \(D\) into two classes:
(i) those which contain \(e\); and
(ii) those which do not contain \(e\).
Let \(\overrightarrow{rs}\) be an edge of a digraph \(D\). Then \[E\left(D;\mathbf{w}\right)=E\left(D^{\prime};\mathbf{w}\right)+E\left(D^{*};\mathbf{w}\right),\] where \(D^{\prime}\) is the graph obtained by deleting \(\overrightarrow{rs}\); and \(D^{*}\) is the (restricted) graph obtained from \(D\), by incorporating \(\overrightarrow{rs}\).
An incorporated edge is a subgraph of either (i) a source star or (ii) a proper sink star. In Case (i), the edge is “source-incorporated”. In Case (ii), we say that the edge is “proper sink-incorporated”.
Throughout our discussion, all sink-incorporated edges will be “proper sink-incorporated”, unless otherwise specified.
We denote by \(D^{*}\left(\overrightarrow{rs}\right)\), the restricted digraph obtained from \(D\), by source-incorporating \(\overrightarrow{rs}\). The restricted digraph obtained, by sink-incorporating \(\overrightarrow{rs}\), will be denoted by \(D^{**}\left[\overrightarrow{rs}\right]\). Hence, we have the following result.
Theorem 3.4. (Fundamental Edge Theorem for Star Polynomials) Let \(D\) be a digraph, containing an edge \(\overrightarrow{rs}\). Then \[\begin{aligned} E(D;\mathbf{w}) =&E\left(D^{\prime}\left(\overrightarrow{rs}\right);\mathbf{w}\right)+E\left(D^{*}\left(\overrightarrow{rs}\right);\mathbf{w}\right) +E\left(D^{**}\left[\overrightarrow{rs}\right];\mathbf{w}\right)\,. \end{aligned}\]
Let \(\overrightarrow{rs}\) be an edge of a digraph \(D\). In the graph \(D^{*}\left(\overrightarrow{rs}\right)\), (where the edge \(\overrightarrow{rs}\) is source-incorporated \(r\) is the centre of a source star, and \(s\) is a tip. Therefore, edges incident with \(s\), cannot belong to a source star containing \(\overrightarrow{rs}\). Also, edges incident to \(r\) (i.e. \(r\) as head), cannot belong to such a source star.
In the graph \(D^{**}\left[\overrightarrow{rs}\right]\), (where the edge \(\overrightarrow{rs}\) is sink-incorporated) \(s\) is the centre of a sink star, and \(r\) is a tip. Therefore, edges incident with \(s\), cannot belong to any sink star containing \(\overrightarrow{rs}\). Also, edges from \(s\) (i.e. \(s\) as tail), cannot belong to such a sink star. Hence, we have the following result.
Lemma 3.5. Let \(D\) be a digraph, containing an edge \(\overrightarrow{rs}\).
(i) If \(D^{*}\left(\overrightarrow{rs}\right)\) contains an incorporated edge \(\overrightarrow{tr}\), \(\overrightarrow{us}\) \((u\neq r)\), or \(\overrightarrow{sv}\), then
\[E\left(D^{*}\left(\overrightarrow{rs}\right);\mathbf{w}\right)=0.\]
(ii) If \(D^{**}\left[\overrightarrow{rs}\right]\) contains an incorporated edge \(\overrightarrow{st}\), \(\overrightarrow{rv}\) \((v\neq s)\), or \(\overrightarrow{ur}\) , then \[E\left(D^{**}\left[\overrightarrow{rs}\right];\mathbf{w}\right)=0.\]
Suppose that an edge \(\overrightarrow{rs}\) is source-incorporated. Then, by Lemma 3.5, we can remove all unincorporated edges incident with (tip) \(s\), incident to (centre) \(r\) (i.e. \(r\) as head); since the incorporation of any such edges, yields a restricted digraph with star polynomial zero.
Suppose that we sink-incorporate an edge \(\overrightarrow{rs}\). Then, by Lemma 3.5, we can omit all unincorporated edges incident with (tip) \(r\), incident from (centre) \(s\); since the incorporation of any such edges, yields a restricted digraph with star polynomial zero. Hence, we have the following result.
Lemma 3.6. Let \(D\) be a digraph and \(\overrightarrow{rs}\) an edge of \(D\). Let \(D_{r}^{*}\left(\overrightarrow{rs}\right)\) be the restricted digraph obtained from \(D^{*}\left(\overrightarrow{rs}\right)\) by removing all edges of the form \(\overrightarrow{ts}\) \((t\neq r)\), \(\overrightarrow{tr}\) or \(\overrightarrow{st}\). Then \[E\left(D_{r}^{*}\left(\overrightarrow{rs}\right);\mathbf{w}\right)=E\left(D^{*}\left(\overrightarrow{rs}\right);\mathbf{w}\right)\,.\]
Also, let \(D_{s}^{**}\left(\overrightarrow{rs}\right)\) be the restricted digraph obtained from \(D^{**}\left(\overrightarrow{rs}\right)\) by removing all edges of the form \(\overrightarrow{rt}\) \((t\neq s)\) , \(\overrightarrow{tr}\) or \(\overrightarrow{sv}\). Then \[E\left(D_{s}^{**}\left[\overrightarrow{rs}\right];\mathbf{w}\right)=E\left(D^{**}\left[\overrightarrow{rs}\right];\mathbf{w}\right)\,.\]
A symmetric digraph with underlying graph \(G\) is obtained from \(G\) by replacing each edge with a pair of oppositely oriented edges. The following result gives explicit recurrences for the star polynomials of symmetric paths; i.e., the symmetric digraph whose underlying graph is a path graph.
| \(n\) | \(\widehat{E}(\overleftrightarrow{P_{n}};\underline{w})\,\,\,\left(=\overset{\vee}{E}(\overleftrightarrow{P_{n}};\underline{w})\right)\) |
|---|---|
| 1 | \(w_{1}\) |
| 2 | \(w_{1}^{2}+2w_{2}\) |
| 3 | \(w_{1}^{3}+4w_{1}w_{2}+w_{3}\) |
| 4 | \(w_{1}^{4}+6w_{1}^{2}w_{2}+2w_{1}w_{3}+4w_{2}^{2}\) |
| 5 | \(w_{1}^{5}+6w_{1}^{3}w_{2}+3w_{1}^{2}w_{3}+5w_{1}w_{2}^{2}+w_{2}w_{3}\) |
| 6 | \(w_{1}^{6}+10w_{1}^{4}w_{2}+4w_{1}^{3}w_{3}+10w_{1}^{2}w_{2}^{2}+7w_{1}w_{2}w_{3}+w_{2}^{3}+w_{3}^{2}\) |
Theorem 4.1.
(i) \({E}(\overleftrightarrow{P}_{n};\underline{x},\underline{y})=x_{1}{E}(\overleftrightarrow{P}_{n-1};\underline{x},\underline{y})+2x_{2}{E}(\overleftrightarrow{P}_{n-2};\underline{x},\underline{y})+(x_{3}+y_{3}){E}(\overleftrightarrow{P}_{n-3};\underline{x},\underline{y}),\)
(ii) \(\overset{\vee}{E}(\overleftrightarrow{P}_{n};\underline{w})=w_{1}\overset{\vee}{E}(\overleftrightarrow{P}_{n-1};\underline{w})+2w_{2}\overset{\vee}{E}(\overleftrightarrow{P}_{n-2};\underline{w})+w_{3}\overset{\vee}{E}(\overleftrightarrow{P}_{n-3};\underline{w}),\)
Also, \(\widehat{E}(\overleftrightarrow{P}_{0};\underline{w})=\overset{\vee}{E}(\overleftrightarrow{P}_{0};\underline{w})=1,\quad \widehat{E}(\overleftrightarrow{P}_{1};\underline{w})=\widehat{E}(\overleftrightarrow{P}_{1};\underline{w})=w_{1},\) and \(\widehat{E}(\overleftrightarrow{P}_{2};\underline{w})=\widehat{E}(\overleftrightarrow{P}_{2};\underline{w})=w_{1}^{2}+2w_{2}.\)
Proof. Let \(v\) be an end-node of \(\overleftrightarrow{P}_{n}\). By the Fundamental Node Theorem, we have \[\begin{aligned} E(\overleftrightarrow{P}_{n};(\underline{x},\underline{y}))=&x_{1}E(\overleftrightarrow{P}_{n}^{\prime}\left(v\right);(\underline{x},\underline{y})) + \sum\limits_{\beta} w\left(\beta\right)E(\overleftrightarrow{P}_{n}^{\prime}\left(\beta\right);(\underline{x},\underline{y})) \\ &+\sum\limits_{\gamma} w_{|\gamma|} E(\overleftrightarrow{P}_{n}^{\prime}\left(\gamma\right);(\underline{x},\underline{y})), \end{aligned}\] where the first summation is taken over all edges \(\beta\) incident on \(v\). The second summation is taken over all proper source stars \(\gamma\) containing \(v\).
The digraphs \(\overleftrightarrow{P}_{n}^{\prime}\left(v\right)\), \(\overleftrightarrow{P}_{n}^{\prime}\left(\beta\right)\) and \(\overleftrightarrow{P}_{n}^{\prime}\left(\gamma\right)\) are the symmetric chains \(\overleftrightarrow{P}_{n-1}\), \(\overleftrightarrow{P}_{n-2}\) and \(\overleftrightarrow{P}_{n-|\gamma|}\), respectively. Since \(v\) is an end-node of \(\overleftrightarrow{P}_{n}\), it has a single neighbour. Let that neighbour be \(u\) , then \(u\) is the centre of the only proper source star and the only proper sink star in \(\overleftrightarrow{P}_{n}\) containing \(v\). Both stars will consist of three nodes. Therefore, the result in Part (i) follows.
The result in Part (ii) is established.
Hence, the result follows. ◻
We have used Theorem 4.1, to obtain the polynomials \(\widehat{E}\left(\overleftrightarrow{P_{n}};\underline{w}\right)\) and \(\overset{\vee}{E}\left(\overleftrightarrow{P_{n}};\underline{w}\right)\), for \(n=1,2,3,4,5,6\). These are given below in Table 1.
Theorem 4.2. Let \(E(n)=E(\overleftrightarrow{P}_{n};\underline{w})\) and \(E(t)=\sum\limits_{k=0}^{n} E(k)t^{k}\). Then \[E(t)=\frac{1}{1-x_{1}t-2x_{2}t^{2}-( x_{3} +y_{3})t^{3}}.\]
Proof. For \(k\geq3\) , we have
\[{E}(\overleftrightarrow{P}_{n};\underline{x},\underline{y})=x_{1}{E}(\overleftrightarrow{P}_{n-1};\underline{x},\underline{y})+2x_{2}{E}(\overleftrightarrow{P}_{n-2};\underline{x},\underline{y})+(x_{3}+y_{3}){E}(\overleftrightarrow{P}_{n-3};\underline{x},\underline{y}),\]
Let \(E(n)=E(\overleftrightarrow{P}_{n};\underline{w})\) and \(E(t)=\sum\limits_{k=0}^{n}E(k)t^{k}\). Thus, by summing from \(k=3\) and multiplying by \(t^{k}\), we have
\[\sum\limits_{k=3}^{n}E(k)t^{k}=x_{1}\sum\limits_{k=3}^{n}E(k-1)t^{k}+2x_{2}\sum\limits_{k=3}^{n}E(k-2)t^{k}+(x_{3}+y_{3})\sum\limits_{k=3}^{n}E(k-3)t^{k},\] and \[\begin{aligned} \sum\limits_{k=0}^{n}E(k)t^{k}&-E(0)-E(1)t-E(2)t^{2}= x_{1}t\left(\sum\limits_{k=0}^{n}E(k)t^{k}-E(0)-E(1)t\right)\\ & +2x_{2}t^{2}\left(\sum\limits_{k=0}^{n}E(k)t^{k}-E(0)\right) +(x_{3}+y_{3})t^{3}\sum\limits_{k=0}^{n}E(k)t^{k}. \end{aligned}\]
Thus,
\[\begin{aligned} E(t)-1-x_{1}t-\left(x_{1}^{2}+2x_{2}\right)t^{2}= & x_{1}t\left(E(t)-1-x_{1}t\right) +2x_{2}t^{2}\left(E(t)-1\right)+(x_{3}+y_3)t^{3}E(t). \end{aligned}\]
Thus,
\[\begin{aligned} E(t)-x_{1}tE(t)-2x_{2}t^{2}E(t)-(x_{3}+y_3)t^{3}E(t)= 1, \end{aligned}\]
Hence, \[E(t)=\frac{1}{1-x_{1}t-2x_{2}t^{2}-( x_{3} +y_{3})t^{3}}.\] ◻
Using the generating function from Theorem 4.2 and making the substitution as suggested in the result given in Theorem 2.2, we obtain a generating function for the sink and source polynomials of symmetric paths.
Theorem 4.3.
(i) \(\overset{\vee}{E}(\overleftrightarrow{P}_{n};\underline{w})=w_{1}\overset{\vee}{E}(\overleftrightarrow{P}_{n-1};\underline{w})+2w_{2}\overset{\vee}{E}(\overleftrightarrow{P}_{n-2};\underline{w})+w_{3}\overset{\vee}{E}(\overleftrightarrow{P}_{n-3};\underline{w}),\)
(ii) Let \(\widehat{E}_{P}(n)=\widehat{E}(\overleftrightarrow{P}_{n};\underline{w})\)
and \(\hat{E}_{P}(t)=\sum\limits_{k=0}^{n}\hat{E}_P(k)t^{k}\).
Then \[\widehat{E}(t)=\frac{1}{1-w_{1}t-2w_{2}t^{2}-w_{3}t^{3}}.\]
The following result gives the number of covers in terms of evaluations of the star polynomials.
Theorem 4.4. Let \(P(n)\) be the number of sink-star (resp. source-star) covers and \(P(t)\) be the sequence’s ordinary generating function, then \(P(t) =\dfrac{1}{1-t-2t^{2}-t^{3} }\).
Proof. By definition, the sum of the coefficients of the sink (resp. source) polynomial is the number of the corresponding type of covers. This can be obtained by substituting \(w_{i}=1\), for all \(i\), into the sink polynomial (resp. source polynomial). Thus, using this substitution and by Theorem 4.2, the result follows. ◻
The terms \(P(n)\) for \(n=1,2,…\); form the sequence A002478 in [14] and are the even-indexed terms of Narayana’s cows sequence (A000930 in [14]).
We now investigate transitive tournaments. In our discussion, we assume that the nodes of the tournaments have been labelled \(v_{1},\) \(v_{2},\ldots\), \(v_{n}\) , such that node \(v_{i}\) dominates \(v_{j}\), if and only if \(i<j\) .
Using any \(r\,\left(\leq n\right)\) nodes of \(^{\tau}K_{n}\), we can construct a source (sink) star, by using the node with lowest (highest) index as its centre. There can be no other source (sink) star containing these \(r\) nodes, since any such star, must contain a node of higher index, dominating a node of lower index (a contradiction). Hence, we have the following result.
Theorem 5.1. Every selection of \(r\) (\(\leq n\)) nodes of the transitive tournament \(^{\tau}K_{n}\), defines a unique source star and a unique sink star.
The following result, gives recurrences for \(\overset{\wedge}{E}({}^{\theta}K_{n};\underline{w})\) and \(\overset{\vee}{E}({}^{\theta}K_{n};\underline{w})\).
Theorem 5.2.
(i) \(\overset{\wedge}{E}({}^{\theta}K_{n};\underline{w})=w_{1}\overset{\wedge}{E}({}^{\tau}K_{n-1};\underline{w})+(n-1)w_{2}\overset{\wedge}{E}({}^{\tau}K_{n-2};\underline{w}),\)
(ii) \(\overset{\vee}{E}({}^{\theta}K_{n};\underline{w})=w_{1}\overset{\vee}{E}({}^{\tau}K_{n-1};\underline{w})+(n-1)w_{2}\overset{\vee}{E}({}^{\tau}K_{n-2};\underline{w})\).
Proof. (i) Apply Theorem 3.2 to the digraph \(^{\theta}K_{n}\), with \(z=v_{n}\); together with Theorem 2.2. This yields \[\begin{aligned} E(D;\underline{w}) & =w_{1}E(D^{\prime}\left(z\right);\underline{w})+\sum\limits_{\overrightarrow{uv}}w_{2}\,E(D^{\prime}\left(\overrightarrow{uv}\right);\underline{w})\\ & \quad+\sum\limits_{\gamma}w_{|\gamma|}\,E(D^{\prime}\left(\gamma\right);\underline{w})+\sum\limits_{\delta}w_{|\delta|}\,E(D^{\prime}\left(\delta\right);\underline{w})\,. \end{aligned}\]
Since no proper source star contains \(v_{n}\), then \[\begin{aligned} \overset{\wedge}{E}({}^{\theta}K_{n};\underline{w}) & =w_{1}\overset{\wedge}{E}({}^{\theta}K_{n}^{\prime}(v_{n});\underline{w})+\sum\limits_{\overrightarrow{uv}}w_{2}\overset{\wedge}{E}({}^{\theta}K_{n}(\overrightarrow{uv});\underline{w}). \end{aligned}\]
By removing the end-nodes of an edge from \(^{\theta}K_{n}\), we get \(^{\tau}K_{n-2}\). By removing a node from \(^{\theta}K_{n}\), we get \(^{\tau}K_{n-1}\). There are \((n-1)\) edges incident with \(v_{n}\). Therefore, we have \[\begin{aligned} \overset{\wedge}{E}({}^{\theta}K_{n};\underline{w}) & =w_{1}\overset{\wedge}{E}({}^{\tau}K_{n-1};\underline{w})+(n-1)w_{2}\overset{\wedge}{E}({}^{\tau}K_{n-2};\underline{w}). \end{aligned}\]
(ii) The result for \(\overset{\vee}{E}\left(^{\theta}K_{n};\underline{w}\right)\) (Part (ii)) can be similarly established, by using \(z=v_{1}\). ◻
The following result gives an explicit formula for \(\overset{\wedge}{E}\left(^{\tau}K_{n};\underline{w}\right)\) and \(\overset{\vee}{E}\left(^{\tau}K_{n};\underline{w}\right)\).
Theorem 5.3.
\[\begin{aligned} \hat{E}\left(^{\tau}K_{n};\underline{w}\right) = \check{E}\left(^{\tau}K_{n};\underline{w}\right) = n! \, \left[ \sum\limits_{\mathbf{j}} \left( \prod_{r+1}^{n} \frac{1}{j_{r}!} \left(\frac{w_{r}}{r!}\right)^{j_{r}} \right) \right]\,, \end{aligned}\] where the summation is taken over all vectors \(\mathbf{j}=\left(j_{1},\,j_{2},\,j_{3},\ldots\,,j_{n}\right)\) of non-negative integers, such that \[\sum\limits_{r = r+1}^{n} r j_r = n.\]
Proof. Let \(S(^{\tau}K_{n};j_{1},\,j_{2},\,\ldots\,,j_{n})\) be the set of sink (source) star covers of \(^{\tau}K_{n}\), with \(j_{1}\) node components, \(j_{2}\) component edges; and in general \(j_{i}\) sink star components with \(i\) nodes, where \(1\leq i\leq n\). Clearly, \[j_{1}+2j_{2}+\ldots+nj_{n}=n.\]
The number of distinct labelled partitions of \(V(^{\tau}K_{n})\) can be obtained by first allocating \(n\) labels to the nodes (which can be done in \(n!\) ways), and then modifying the result because of duplications (by dividing by \(\prod_{r}(r!)^{j_{r}}j_{r}!\)) arising from permutations of both the parts of the partitions, and permutations to the nodes within each part. Therefore, the number of such partitions is \[n! \sum\limits_{r = r+1}^{n} \prod \frac{1}{(r!)^{j_r} j_r!} \,,\] where \(\sum\limits_{r}rj_{r}=n\).
By Theorem 5.1, for every selection of \(r\) (\(\leq n\)) nodes of the transitive tournament \(^{\tau}K_{n}\), defines a unique source star and a unique sink star. Therefore, the contribution to \(\left(^{\tau}K_{n};\underline{w}\right)\) of the covers belonging to \(S(^{\tau}K_{n};j_{1},\,j_{2},\,\ldots\,,j_{n})\) is \[C_{\mathbf{j}}=n!\prod_{r}\frac{w_{r}^{j_{r}}}{(r!)^{j_{r}}j_{r}!}\,.\]
Summing over all the partitions that satisfy the restrictions given above, yields \[\hat{E}\left(^{\tau}K_{n}; \underline{w}\right) = n! \, \left[ \sum\limits_{\mathbf{j}} \left( \prod_{r = r+1}^{n} \frac{1}{j_r!} \left(\frac{w_r}{r!}\right)^{j_r} \right) \right] \,,\] where the summation is taken over all vectors \(\mathbf{j}=\left(j_{1},\,j_{2},\,j_{3},\ldots\,,j_{n}\right)\) of non-negative integers, such that \[\sum\limits_{r = 1}^{n} r j_r = n.\]
Clearly, \(\overset{\wedge}{E}\left(^{\tau}K_{n};\underline{w}\right)=\overset{\vee}{E}\left(^{\tau}K_{n};\underline{w}\right)\). Hence, the result follows. ◻
The rooted products of graphs was introduced by Godsil and Mckay in 1978 [9]. The rooted product of a graph \(G\) and a rooted graph \(H\) is defined as the graph obtained by identifying each node \(v_i\) of \(G\), with the root node of a copy of \(H\).
We now introduce a generalization of the rooted product . This product is formed from an oriented star and various rooted digraphse. That is, there may be more than a pair of digraphs involved in the product.
Definition 6.1. Let \(^{\sigma}S_{n}\) be an oriented \(n-\)star, with tips \(v_{1}\), \(v_{2}\), \(\ldots,\) \(v_{n}\) and centre \(v_{0}\); and let \(D_{1}D_{2}\ldots D_{n}\) be rooted digraphs with roots \(z_{1}\), \(z_{2}\) \(\ldots z_{n}\). We denote by \[^{\sigma} S_{n} \cdot \, D_{1} D_{2} \ldots D_{n},\] the graph obtained by attaching to \(v_{i}\), the digraph \(D_{i}\) using node \(z_{i}\) (for \(i\) \(=1,\)\(2,\ldots,n)\). The resulting \(i^{\text{th}}\) node of attachment will be labelled \(z_{i}\). (The centre is considered to be identified with the only node of the digraph \(K_1\).)
We now derive a general result for the star polynomials of digraphs obtained by identifying rooted digraphs with tips of stars.
Theorem 6.2. Let \(H\) be the digraph \(^{\sigma}S_{n}\cdot D_{1}D_{2}\ldots D_{n}\), in which the out-degree of the centre of \(^{\sigma}S_{n}\) is non-zero. Let \(\overrightarrow{rz_{1}}\in H.\) Then
\[\begin{aligned} E\left(H;\mathbf{w}\right) =& E(D_{1};\mathbf{w})\,E\big(({}^{\sigma}S_{n} – v_{1}) \cdot D_{2}D_{3} \ldots D_{n};\mathbf{w}\big) \\ &\quad + E\left(D_{1} – z_{1};\mathbf{w}\right) \left(\prod_{k \in A^{-}} E(D_{k};\mathbf{w})\right) \sum\limits_{N \subseteq A^{+}} w\left(\hat{S}_{|N|}\right) \\ &\quad \times \left(\prod_{j \in A^{+} – N} E(D_{j};\mathbf{w})\right) \left(\prod_{\substack{i \in N \\ i \neq 1}} E(D_{i} – z_{i};\mathbf{w})\right) \\ &\quad + E\big( (\{\overrightarrow{r z_{1}}\} \cdot D_{1})^{**} [\overrightarrow{r z_{1}}]; \mathbf{w} \big) \prod_{k=2}^{n} E(D_{k};\mathbf{w}) \,, \end{aligned}\] where \(\hat{S}_{|N|}\) is a source star with centre \(r\), and containing \(\overrightarrow{rz_{1}}\) .
Proof. Apply the Fundamental Edge Theorem for Star Polynomials (Theorem 3.6) to \(H\) using the edge \(\overrightarrow{rz_{1}}\). This yields:
\[E\left(H;\underline{w}\right)=E(H^{\prime}(\overrightarrow{rz_{1}});\underline{w})+E(H^{*}(\overrightarrow{rz_{1}});\underline{w})+E(H^{**}(\overrightarrow{rz_{1}});\underline{w}).\]
Removing the edge \(\overrightarrow{rz_{1}}\) from \(H\), yields a graph with components \(D_{1}\) and \(\left(^{\sigma}S_{n}-v_{1}\right)\cdot D_{2}D_{3}\ldots D_{n}\). Therefore, \[H^{\prime}(\overrightarrow{rz_{1}})=D_{1}\cup\left[\left(^{\sigma}S_{n}-v_{1}\right)\cdot D_{2}D_{3}\ldots D_{n}\right].\]
By Lemma 3.6, \[E(H^{*}(\overrightarrow{rz_{1}});\mathbf{w})=E(H_{r}^{*};\mathbf{w})\,,\] where \[H_{r}^{*}=H^{*}(\overrightarrow{rz_{1}})-\left\{ \overrightarrow{tz_{1}}\,:\,t\neq r\right\} -\{\overrightarrow{vr}\,:\,v\in H\}-\{\overrightarrow{z_{1}v}\,:\,v\in H\}.\]
Now, \[\begin{aligned} H^{*}(\overrightarrow{rz_{1}})-\{\overrightarrow{vr}\,:\,v\in H\}=& H^{*}(\overrightarrow{rz_{1}})-\{\overrightarrow{z_{i}r}\in H:i=2,\ldots,n\}\\ =&\left(^{\sigma}S_{n}\cdot D_{1}D_{2}\ldots D_{n}\right)^{*}(\overrightarrow{rz_{1}})-\{\overrightarrow{z_{i}r}\in H:i=2,\ldots,n\}. \end{aligned}\]
Removing the edges of the form \(\overrightarrow{z_{i}r}\) \(\left(i\neq1\right)\), disconnects the corresponding digraphs \(D_{i}\) from the node \(r\).
Let \(\boldsymbol{A^{-}} = \left\{ i : \overrightarrow{z_{i} r} \in H \right\}\) and \(\boldsymbol{A^{+}}=\left\{ i\,:\,\overrightarrow{rz_{i}}\in H\right\}\).
Clearly, \(|A^{-}|=\mathrm{id}(r)\) and \(|A^{-}|=\mathrm{od}(r)\). Therefore \[H^{*}(\overrightarrow{r z_{1}}) – \{ \overrightarrow{v r} : v \in H \} = \left(\bigcup_{k \in A^{-}} D_{k}\right) \cup \left(\hat{S}_{|A^{+}|} \cdot D_{j_{1}} D_{j_{2}} \ldots D_{j_{\mathrm{id}(r)}}\right)^{*}(\overrightarrow{r z_{1}}),\] where \(j_{1},\) \(j_{2},\) \(\ldots\), \(j_{\mathrm{id}(r)}\) are the elements of \(A^{-}\); and where \(\hat{S}_{|A^{+}|}\) is a source star, with \(r\) as centre.
Removing all edges of the form \(\overrightarrow{z_{1}v}\) and \(\overrightarrow{tz_{1}}\) \((t\neq r)\), yields a graph in which \(\left(D_{1}-z_{1}\right)\) is a component.
Therefore, \[H_{r}^{*}=H^{*}(\overrightarrow{rz_{1}})-\left\{ \overrightarrow{tz_{1}}\,:\,t\neq r\right\} -\{\overrightarrow{vr}\,:\,v\in H\}-\{\overrightarrow{z_{1}v}\,:\,v\in H\},\] \[H^{*}(\overrightarrow{r z_{1}}) – \{ \overrightarrow{v r} : v \in H \} = \left( \bigcup_{k \in A^{-}} D_{k} \right) \cup \left( \hat{S}_{|A^{+}|} \cdot D_{j_{1}} D_{j_{2}} \ldots D_{j_{\mathrm{id}(r)}} \right)^{*}(\overrightarrow{r z_{1}}),\]
Let \(X\) be a source star component of a cover in which \(\overrightarrow{rz_{1}}\) is a source-incorporated edge. If \(z_{k}\notin X\), for some \(k\), then \(z_{k}\) belongs to a cover of \(D_{k}\). Hence,
\[\begin{aligned} E\left(H_{r}^{*}; \mathbf{w}\right) =& E\left(D_{1} – z_{1}; \mathbf{w}\right) \prod_{k \in A^{-}} E(D_{k}; \mathbf{w})\\ & \times \left[ \sum\limits_{\substack{N \subseteq A^{+} \\ z_{1} \in N}} \Biggl( E\left(\hat{S}_{|N|}^{*}(\overrightarrow{r z_{1}}); \mathbf{w}\right) \prod_{j \in A^{+} \!-\! N} E\left(D_{j}; \mathbf{w}\right) \times \prod_{\substack{i \in N \\ i \neq 1}} E\left(D_{i} – z_{i}; \mathbf{w}\right) \Biggr) \right] \,, \end{aligned}\] where the source star \(\hat{S}_{|N|}\), has \(r\) as centre.
When we sink-incorporate \(\overrightarrow{rz_{1}}\) (to obtain \(H_{s}^{**}\)), then (by Lemma 3.6) we omit all other edges incident with \(r\), or leaving \(s\). This yields a graph with components \(\left\{ \overrightarrow{rz_{1}}\right\} \boldsymbol{\cdot}D_{1}\) and \(D_{i}\) (\(i=2,3,\ldots,n)\). Therefore, \[H_{s}^{**} = \bigl( \{ \overrightarrow{r z_{1}} \} \cdot D_{1} \bigr) \cup \bigcup_{2 \leq k \leq n} D_{k} ,\]
When we sink-incorporate \(\overrightarrow{rz_{1}}\), (i.e. require \(\overrightarrow{rz_{1}}\) to be in a proper sink star), to obtain \(H_{s}^{**}\), there are corresponding covers, only if there is an edge in \(D_{1},\) with \(z_{1}\) as head. Therefore, \[E\left(H_{s}^{**}; \mathbf{w}\right) = E\bigl( \{ \overrightarrow{r z_{1}} \} \cdot D_{1}; \mathbf{w} \bigr) \prod_{k=2}^{n} E(D_{k}; \mathbf{w}) \,.\]
Hence, the result follows. ◻
We now derive a general result for the star polynomials of the partial rooted products of an oriented star and a rooted digraph, where the tips are identified with the roots of copies of a particular digraph.
Let \(u\) be a node in a digraph \(D\). Let \(H\) be the digraph formed by identifying a copy of \(D\) (using root node \(u\)) to each tip of the oriented star \(^{\sigma}S_{n}\). When \(D_{i}=D\) (\(i=1,2,\ldots,n\)), we have:
(i) \[E(D_{1};\mathbf{w})\,E(\left(^{\sigma}S_{n}-v_{1}\right)\cdot D_{2}D_{3}\ldots D_{n};\mathbf{w})=E(D;\mathbf{w})\,E(\left(^{\sigma}S_{n}-v_{1}\right)\cdot DD\ldots D;\mathbf{w})\,.\]
(ii) \[\prod_{k \in A^{+}} E(D_{k}; \mathbf{w}) = \prod_{k \in A^{-}} E(D; \mathbf{w}) = \bigl(E(D; \mathbf{w})\bigr)^{\mathrm{id}(r)} \quad \text{[since } |A^{-}| = \mathrm{id}(r) \text{]} \,.\]
(iii) \[\begin{aligned} &\sum\limits_{N \subseteq A^{+}} w\bigl(\check{S}_{|N|}\bigr) \left( \prod_{j \in A^{+} – N} E(D_{j}; \mathbf{w}) \right) \left( \prod_{i \in N} E(D_{i} – z_{i}; \mathbf{w}) \right) \\ &\qquad= \sum\limits_{N \subseteq A^{+}} x_{|N|} \left( \prod_{j \in A^{+} – N} E(D; \mathbf{w}) \right) \left( \prod_{i \in N} E(D – z_{i}; \mathbf{w}) \right), \end{aligned}\] [since \(D_{i}=D,\,\,\forall i\)] \[= \sum\limits_{k=1}^{\mathrm{od}(r)} x_{k} \left( E(D; \mathbf{w}) \right)^{\mathrm{od}(r) – k} \left( E(D – u; \mathbf{w}) \right)^{k},\] [since \(1\leq|N|\leq|A^{+}|=\mathrm{od}(r)\)].
Now, \[E\bigl( (\{ \overrightarrow{r z_{1}} \} \cdot D_{1})^{**} [ \overrightarrow{r z_{1}} ]; \mathbf{w} \bigr) \prod_{k=2}^{n} E(D_{k}; \mathbf{w})=E((\left\{ \overrightarrow{rz_{1}}\right\} \cdot D)^{**}\left[\overrightarrow{rz_{1}}\right]);\mathbf{w})\,\left(E(D;\mathbf{w})\right)^{n-1}.\]
The following corollary gives the result, when the centre of \(^{\sigma}S_{n}\) has non-zero out-degree, and a copy of the graph \(D\) is identified with each tip of \(^{\sigma}S_{n}\).
Corollary 7.1. Let \(H=\left(^{\sigma}S_{n}-v_{1}\right)\cdot DD\ldots D\), in which the out-degree of the centre of \(^{\sigma}S_{n}\) is non-zero. Let \(\overrightarrow{rz_{1}}\in H.\) Then \[\begin{aligned} E\left(H; \mathbf{w}\right) &= E(D; \mathbf{w}) \, E\bigl( (^{\sigma} S_{n} – v_{1}) \cdot D D \ldots D ; \mathbf{w} \bigr) \\ &\quad + E\left(D – z_{1}; \mathbf{w}\right) \bigl(E(D; \mathbf{w})\bigr)^{\mathrm{id}(r)} \sum\limits_{k=2}^{\mathrm{od}(r)} x_{k} \, \bigl(E(D; \mathbf{w})\bigr)^{\mathrm{od}(r) – k} \bigl(E(D – u; \mathbf{w})\bigr)^{k} \\ &\quad + E\bigl( (\{ \overrightarrow{r z_{1}} \} \cdot D)^{**} [ \overrightarrow{r z_{1}} ]; \mathbf{w} \bigr) \, \bigl(E(D; \mathbf{w})\bigr)^{n-1}. \end{aligned}\]
If \(D\) is a component node, \(H=^{\sigma}S_{n}\). In this case, we have:
(i) \(E(D;\mathbf{w})=E(K_{1};\mathbf{w})=x_{1}\) ;
(ii) \(E(\left(^{\sigma}S_{n}-v_{1}\right)\cdot DD\ldots D;\mathbf{w})=E({}^{\sigma}S_{n}-v_{1};\mathbf{w})\); and
(iii) \(E\left(D-z_{1};\mathbf{w}\right)=1\), since \(D-z_{1}\) is the null graph.
(iv) \(\left\{ \overrightarrow{rz_{1}}\right\} \cdot D=\left\{ \overrightarrow{rz_{1}}\right\}\).
Therefore \[E((\left\{ \overrightarrow{rz_{1}}\right\} \cdot D)^{**}\left[\overrightarrow{rz_{1}}\right]);\mathbf{w})=E((\overrightarrow{P_{2}})^{**}\left[\overrightarrow{rz_{1}}\right]);\mathbf{w})=0\,.\]
By Corollary 7.1, we have:
\[\begin{aligned} E(^{\sigma}S_{n};\mathbf{w}) = x_{1} \cdot E\bigl(^{\sigma}S_{n} – v_{1}; \mathbf{w}\bigr) + 1 \cdot x_{1}^{\text{id}(r)} \cdot \Biggl( \sum\limits_{k=1}^{\mathrm{od}(r)} x_{k} \, x_{1}^{\mathrm{od}(r) – k} \cdot 1^{k} \Biggr). \end{aligned}\]
Also, \(\mathrm{od}(r)+\mathrm{id}(r)=n\). Hence, we have the following result.
Corollary 7.2. Let \(^{\sigma}S_{n}\) be an oriented star with centre \(r\) and tips \(v_{1}\), \(v_{2}\), \(\ldots,\,v_{n}\); such that the out-degree of \(r\) is non-zero. Then \[\begin{aligned} E(^{\sigma} S_{n}; \mathbf{w}) = x_{1} \cdot E(^{\sigma} S_{n} – v_{1}; \mathbf{w}) + \sum\limits_{k=2}^{\mathrm{od}(r)} x_{1}^{n-k} x_{k+1}. \end{aligned}\]
A similar argument can be used, to obtain a result analogous to
Theorem 6.2, when \(\overrightarrow{z_{1}r}\) (instead of \(\overrightarrow{rz_{1}}\)) belongs to \(H\).
However, we will give an independent argument.
Reversing the edges of a source star (sink star), yields a sink star (source star). Thus, the requirement that an edge \(\overrightarrow{uv}\) in \(D\), belongs to a source star, is equivalent to requiring that the reversed edge \(\overrightarrow{vu}\), belongs to a sink star in \(\overleftarrow{D}\). Also, the requirement that an edge \(\overrightarrow{uv}\) in \(D\), belongs to a proper sink star, is equivalent to requiring that the reversed edge \(\overrightarrow{vu}\), belongs to a proper source star in \(\overleftarrow{D}\). This restricted graph will be denoted by \(\overleftarrow{D}^{*}[\overrightarrow{vu}]\). We use square brackets, instead of parentheses, to indicate that the edge must belong to a proper source star. Hence, we have the following result.
Lemma 7.3. Let \(T:\mathbb{R}\left[\mathbf{w}\right]\rightarrow\mathbb{R}\left[\mathbf{w}\right]\) be the automorphism defined by \(T\left(w(\hat{S}_{n})\right)=w(\check{S}_{n})\), and \(T\left(w(\check{S}_{n})\right)=w(\hat{S}_{n})\). Then,
(i) \(\overleftarrow{\left(\overleftarrow{D}\right)}=D\) ;
(ii) \(T\left(E(D;\mathbf{w})\right)=E(\overleftarrow{D};\mathbf{w})\) ;
(iii) \(T\left(E(D^{*}(\overrightarrow{uv});\mathbf{w})\right)=E(\overleftarrow{D}^{**}(\overrightarrow{vu});\mathbf{w})\) ; and
(iv) \(T\left(E(D^{**}[\overrightarrow{uv}];\mathbf{w})\right)=E(\overleftarrow{D}^{*}[\overrightarrow{vu}];\mathbf{w})\).
Using Theorem 2.2 and Lemma 7.3, we deduce the following result.
Theorem 7.4. Let \(D\) be a digraph. Then
(i) \(\overset{\wedge}{E}(D;\underline{w})=\overset{\vee}{E}(\overleftarrow{D};\underline{w})\); and
(ii) \(\overset{\wedge}{E}(D;w)=\overset{\vee}{E}(\overleftarrow{D};w)\).
Note that \(\overrightarrow{z_{1}r}\in D\) implies that \(\overrightarrow{rz_{1}}\in\overleftarrow{D}\) – the converse of \(D\). Therefore, applying Theorem 6.2 to the converse of \(H\), yields:
\[\begin{aligned} E\left(\overleftarrow{H}; \mathbf{w}\right) &= E(\overleftarrow{D_{1}}; \mathbf{w})\, E\bigl( (\overleftarrow{^{\sigma} S_{n}} – v_{1}) \cdot \overleftarrow{D_{2}} \overleftarrow{D_{3}} \ldots \overleftarrow{D_{n}}; \mathbf{w} \bigr) \\ &\quad + E\left(\overleftarrow{D_{1}} – z_{1}; \mathbf{w}\right) \left( \prod_{k \in A^{-}} E(\overleftarrow{D_{k}}; \mathbf{w}) \right) \\ &\quad \times \left( \sum\limits_{N \subseteq A^{+}} E\left(\hat{S}_{|N|}\right) \left[ \prod_{j \in A^{+} – N} E(\overleftarrow{D_{j}}; \mathbf{w}) \right] \left[ \prod_{i \in N} E(\overleftarrow{D_{i}} – z_{i}; \mathbf{w}) \right] \right) \\ &\quad + E\bigl( (\{ \overrightarrow{r z_{1}} \} \cdot D_{1}); \mathbf{w} \bigr) \prod_{k=2}^{n} E(D_{k}; \mathbf{w}) \,. \end{aligned}\]
By applying the automorphism \(T\), we have:
\[\begin{aligned} T\bigl(E(\overleftarrow{H}; \mathbf{w})\bigr) &= T\bigl( E(\overleftarrow{D_{1}}; \mathbf{w}) \, E\bigl( (\overleftarrow{^{\sigma} S_{n}} – v_{1}) \cdot \overleftarrow{D_{2}} \ldots \overleftarrow{D_{n}}; \mathbf{w} \bigr) \bigr) \\ &\quad + T\left[ E\bigl(\overleftarrow{D_{1}} – z_{1}; \mathbf{w}\bigr) \left( \prod_{k \in A^{-}} E(\overleftarrow{D_{k}}; \mathbf{w}) \right) \right.\\ &\left.\quad \times \left( \sum\limits_{N \subseteq A^{+}} E\bigl(\hat{S}_{|N|}^{*}(\overrightarrow{r z_{1}})\bigr) \left( \prod_{j \in A^{+} – N} E(\overleftarrow{D_{j}}; \mathbf{w}) \right) \left( \prod_{\substack{i \in N \\ i \neq 1}} E(\overleftarrow{D_{i}} – z_{i}; \mathbf{w}) \right) \right) \right] \\ &\quad + T\Bigl( E\bigl( (\{ \overrightarrow{r z_{1}} \} \cdot D_{1})^{**} [ \overrightarrow{r z_{1}} ]; \mathbf{w} \bigr) \, E\bigl( \prod_{k=2}^{n} \overleftarrow{D_{k}}; \mathbf{w} \bigr) \Bigr) \,. \end{aligned}\]
Using Lemma 7.3, we get: \[\begin{aligned} E\left(H; \mathbf{w}\right) &= E(D_{1}; \mathbf{w}) \, E\bigl( (^{\sigma} S_{n} – v_{1}) \cdot D_{2} D_{3} \ldots D_{n}; \mathbf{w} \bigr) \\ &\quad + E\left(D_{1} – z_{1}; \mathbf{w}\right) \left( \prod_{k \in A^{+}} E(D_{k}; \mathbf{w}) \right) \sum\limits_{N \subseteq A^{-}} E\left(\check{S}_{|N|}^{**}(\overrightarrow{r z_{1}})\right) \\ &\quad \times \left( \prod_{j \in A^{-} – N} E(D_{j}; \mathbf{w}) \right) \left( \prod_{\substack{i \in N \\ i \neq 1}} E(D_{i} – z_{i}; \mathbf{w}) \right) \\ &\quad + E\bigl( (\{ \overrightarrow{z_{1} r} \} \cdot D_{1})^{**} [ \overrightarrow{r z_{1}} ]; \mathbf{w} \bigr) \, E\bigl( \prod_{k=2}^{n} D_{k}; \mathbf{w} \bigr) \,. \end{aligned}\]
Hence, we have the following result.
Theorem 7.5. Let \(H\) be the graph \(^{\sigma}S_{n}\cdot D_{1}D_{2}\ldots D_{n}\), in which the in-degree of the centre of \(^{\sigma}S_{n}\) is non-zero. Let \(\overrightarrow{z_{1}r}\in H.\) Then
\[\begin{aligned} E\left(H;\mathbf{w}\right)=&E(D_{1};\mathbf{w})\,E(\left(^{\sigma}S_{n}-v_{1}\right)\cdot D_{2}D_{3}\ldots D_{n};\mathbf{w}) + E\left(D_{1} – z_{1}; \mathbf{w}\right) \left( \prod_{k \in A^{+}} E(D_{k}; \mathbf{w}) \right) \\ &\quad \times \sum\limits_{N \subseteq A^{-}} w\left(\check{S}_{|N|}\right) \left( \prod_{j \in A^{-} – N} E(D_{j}; \mathbf{w}) \right) \left( \prod_{\substack{i \in N \\ i \neq 1}} E(D_{i} – z_{i}; \mathbf{w}) \right) \\ &+ E\bigl( (\{ \overrightarrow{z_{1} r} \} \cdot D_{1})^{*}(\overrightarrow{z_{1} r}); \mathbf{w} \bigr) \, E\left( \prod_{k=2}^{n} D_{k}; \mathbf{w} \right) \,, \end{aligned}\] where \(\check{S}_{|N|}\) is a sink star with centre \(r\), and containing edge \(\overrightarrow{z_{1}r}\) .
An analogous condition holds for sink stars.
Using an argument analogous to that given for Corollary 7.1, together with Theorem 7.5, we obtain the following results, when the centre of \(^{\sigma}S_{n}\) has non-zero in-degree. We can now obtain the following result for \(E(^{\sigma}S_{n};(\underline{x},\underline{y}))\).
Theorem 7.6. Let \(^{\sigma}S_{n}\), be an oriented star with centre \(r\) and tips \(v_{1}\), \(v_{2}\), \(\ldots,\,v_{n}\); such that the in-degree of \(r\) is non-zero. Then \[\begin{aligned} E(^{\sigma}S_{n}; (\underline{x}, \underline{y})) &= x_{1} \cdot E(^{\sigma}S_{n} – v_{1}; (\underline{x}, \underline{y})) + x_{1}^{n-1} x_{2} + \sum\limits_{k=2}^{\mathrm{id}(r)} x_{1}^{n-k} y_{k+1}. \end{aligned}\]
Proof. \(^{\sigma}S_{n}={}^{\sigma}S_{n}\cdot DD\ldots
D\), when \(D\) is a component
node,. In this case, we have:
\(E(D;(\underline{x},\underline{y}))=E(K_{1};(\underline{x},\underline{y}))=x_{1}\)
; \(E(\left(^{\sigma}S_{n}-v_{1}\right)\cdot
DD\ldots
D;(\underline{x},\underline{y}))=E({}^{\sigma}S_{n}-v_{1};(\underline{x},\underline{y}))\);
and \(E\left(D-z_{1};(\underline{x},\underline{y})\right)=1\),
since \(D-z_{1}\) is the null graph.
\(\left\{ \overrightarrow{z_{1}r}\right\}
\cdot D=\left\{ \overrightarrow{z_{1}r}\right\}\); and
therefore
\[E((\left\{ \overrightarrow{z_{1}r}\right\} \cdot D)^{**}\left[\overrightarrow{z_{1}r}\right]);(\underline{x},\underline{y}))=E((\overrightarrow{P_{2}})^{**}\left[\overrightarrow{z_{1}r}\right]);(\underline{x},\underline{y}))=0.\]
By Theorem 6.2, we have:
\[\begin{aligned} E(^{\sigma}S_{n};(\underline{x},\underline{y})) & =x_{1}\cdot E(^{\sigma}S_{n}-v_{1};(\underline{x},\underline{y})) +1\cdot x_{1}^{\text{od}(r)}\cdot\Bigl(x_{2}\cdot\bigl(x_{1}\bigr)^{\mathrm{id}(r)-1}\\ & \quad+\mathrm{id}(r){\sum}y_{k+1}\,x_{1}^{\mathrm{id}(r)-k}\cdot1^{k}\Bigr). \end{aligned}\] Also, \(\mathrm{od}(r)+\mathrm{id}(r)=n\). Hence, the result follows. ◻
Every proper star subgraph of a sink (source) star is a sink (source) star. From Theorem 2.2: Conversion of star polynomials to sink and source polynomials]; together with Corollary 7.2 and Theorem 7.6; we have the following result.
Theorem 7.7.
(i) \[\overset{\vee}{E}(\overset{\vee}{S}_{n};
\underline{w}) = w_{1} \cdot \overset{\vee}{E}(\overset{\vee}{S}_{n-1};
\underline{w}) + \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1}.\]
(ii) \[\overset{\wedge}{E}(\overset{\vee}{S}_{n};
\underline{w}) = w_{1} \cdot
\overset{\wedge}{E}(\overset{\vee}{S}_{n-1}; \underline{w}) +
w_{1}^{n-1} w_{2}.\] (iii) \[\overset{\wedge}{E}(\overset{\wedge}{S}_{n};
\underline{w}) = w_{1} \cdot \overset{\vee}{E}(\overset{\vee}{S}_{n-1};
\underline{w}) + \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1}.\]
(iv) \[\overset{\vee}{E}(\overset{\wedge}{S}_{n};
\underline{w}) = w_{1} \cdot
\overset{\vee}{E}(\overset{\wedge}{S}_{n-1}; \underline{w}) +
w_{1}^{n-1} w_{2},\] where \(\overset{\wedge}{E}(\overset{\wedge}{S}_{0};\underline{w})=\overset{\vee}{E}(\overset{\vee}{S}_{0};\underline{w})=\overset{\vee}{E}(\overset{\wedge}{S}_{0};\underline{w})=\overset{\wedge}{E}(\overset{\vee}{S}_{0};\underline{w})\)\(=w_{1}\).
Proof. (i) For a sink star with \(n\) tips, the in-degree of the centre is \(n\). Therefore, Corollary 7.6, yields: \[\begin{aligned} E(\overset{\vee}{S}_{n}; \underline{w}) = x_{1} \cdot E(\overset{\vee}{S}_{n} – v_{1}; \underline{w}) + x_{1}^{n-1} x_{2} + \sum\limits_{k=1}^{n} x_{1}^{n-k} y_{k+1}. \end{aligned}\]
Using Theorem 2.2, we get: \[\begin{aligned} \overset{\vee}{E}(\overset{\vee}{S}_{n}; \underline{w}) &= w_{1} \cdot \overset{\vee}{E}(\overset{\vee}{S}_{n-1}; \underline{w}) + w_{1}^{n-1} w_{2} + \sum\limits_{k=2}^{n} w_{1}^{n-k} w_{k+1} \\ &= w_{1} \cdot \overset{\vee}{E}(\overset{\vee}{S}_{n-1}; \underline{w}) + \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1}. \end{aligned}\]
The recurrences given in (ii), (iii) and (iv), can be similarly deduced. ◻
We note from (i) and (iii), that \(\overset{\wedge}{E}(\overset{\wedge}{S}_{n};\underline{w})=\overset{\vee}{E}(\overset{\vee}{S}_{n};\underline{w})\). The following Table 2 gives these polynomials, for \(n=1,2\ldots,6\).
| \(n\) | \(\overset{\wedge}{E}(\overset{\wedge}{S}_{n};\underline{w})\,\,\left(=\overset{\vee}{E}(\overset{\vee}{S}_{n};\underline{w})\right)\) |
|---|---|
| 1 | \(w_{1}^{2}+w_{2}\) |
| 2 | \(w_{1}^{3}+2w_{1}w_{2}+w_{3}\) |
| 3 | \(w_{1}^{4}+3w_{1}^{2}w_{2}+2w_{1}w_{3}+w_{4}\) |
| 4 | \(w_{1}^{5}+4w_{1}^{3}w_{2}+3w_{1}^{2}w_{3}+2w_{1}w_{4}+w_{5}\) |
| 5 | \(w_{1}^{6}+5w_{1}^{4}w_{2}+4w_{1}^{3}w_{3}+3w_{1}^{2}w_{4}+2w_{1}w_{5}+w_{6}\) |
| 6 | \(w_{1}^{7}+6w_{1}^{5}w_{2}+5w_{1}^{4}w_{3}+4w_{1}^{3}w_{4}+3w_{1}^{2}w_{5}+2w_{1}w_{6}+w_{7}\) |
Theorem 7.8. Denote \(\overset{\vee}{E}(\overset{\vee}{S}_{n};\underline{w})\) and \(\overset{\wedge}{E}(\overset{\wedge}{S}_{n};\underline{w})\) by \(E(n)\). Then \[E(n) = w_{1}^{n+1} + \sum\limits_{k=1}^{n} k w_{1}^{n-k} w_{k+1}, \quad \text{for } n \geq 0.\]
Proof. From Theorem 7.7 (iii), we have
\[\label{eq1} E(n) = w_{1} E(n-1) + \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1}, \quad \text{with } E(0) = w_{1} . \tag{1}\]
Multiplying by \(t^{n}\), and summing from \(n=1\), yield:
\[\sum\limits_{n=1} E(n) t^{n} = w_{1} \sum\limits_{n=1} E(n-1) t^{n} + \sum\limits_{n=1} \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1} t^{n}.\]
Let \(E(t) = \sum\limits_{n=0} E(n) t^{n}\). Then, we have:
\[E(t) – E(0) = w_{1} t E(t) + \sum\limits_{n=1} \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1} t^{n},\]
\[\Rightarrow E(t)(1 – w_{1} t) – w_{1} = \sum\limits_{n=1} \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1} t^{n} \quad [E(0) = w_{1}],\]
\[\begin{aligned} \Rightarrow E(t) &= \frac{w_{1} + \sum\limits_{n=1} \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1} t^{n}}{1 – w_{1} t} \\ &= \Bigl( w_{1} + \sum\limits_{n=1} \sum\limits_{k=1}^{n} w_{1}^{n-k} w_{k+1} t^{n} \Bigr) \Bigl( 1 + w_{1} t + w_{1}^{2} t^{2} + \ldots \Bigr). \end{aligned}\]
Extracting the coefficient of \(t^{n}\) yields: \[\begin{aligned} E(n) &= w_1^{n+1} + \sum\limits_{n=1} \sum\limits_{k=1}^{n} w_1^{n-k} w_{k+1} \\ &= w_1^{n+1} + w_1^{n-1}w_2 + \left(w_1^{n-1}w_2 + w_1^{n-2}w_3\right) + \left(w_1^{n-1}w_2 + w_1^{n-2}w_3 + w_1^{n-3}w_4\right) \\ &\quad + \ldots + \sum\limits_{k=1}^{n} w_1^{n-k} w_{k+1} \\ &= w_1^{n+1} + w_1^{n-1}w_2 + 2w_1^{n-2}w_3 + 3w_1^{n-3}w_4 + \ldots + nw_1^0 w_{n+1} \\ &= w_1^{n+1} + \sum\limits_{k=1}^{n} k w_1^{n-k} w_{k+1}. \end{aligned}\]
Since \(\overset{\vee}{E}(\overset{\vee}{S}_{n};\underline{w})\) and \(\overset{\wedge}{E}(\overset{\wedge}{S}_{n};\underline{w})\), satisfy the recurrence (in Eq. 1), the result follows. ◻
In this section, we establish new connections between the out-domination number, the in-domination number, and the presence of specific terms in the source and sink polynomials, thereby linking domination parameters with polynomial characteristics. Additionally, we present applications of star covers and associated polynomials to a class of domination concepts introduced in [11] , as well as to a result about the cardinalities of neighborhoods of independent sets. Additionally,
For a digraph \(D\), if \(uv \in D\) then the node \(u\) is said to dominate the node \(v\). An out-domination set of a digraph D is a set S of vertices of D such that every node of \(D-S\) is an out-neighbour of some node of \(S\). The minimum cardinality of an out-domination set for \(D\) is the out-domination number \(\gamma ^{+}\) of \(D\). The in-domination number \(\gamma ^{-} (D)\) is analogously defined in terms of the in-neighbours pf nodes in \(S\).
Some basic properties of (directed) star polynomials are given below. Note that for a multivariate polynomial, the degree of each term is the sum of the exponents of its variables.
Theorem 8.1. The minimum degree of the terms in \(\widehat{E}(D;\underline{w})\) is the out-domination number of \(D\).
Proof. The centre of each source star dominates the tips of the stars. So the set of centre nodes and component nodes, comprise a dominating set of the digraph \(D\). Also every dominating set \(X\) of \(D\) has edges directed from members of \(X\), to the remaining nodes of \(D\), call this set \(E_X\). Therefore, for each such out-dominating set \(X\), one can obtain a star cover, by selecting edges from \(E_X\) so that no two nodes are dominated by the same member of \(X\), and no member of \(X\) dominates another. Thus the number of members of \(X\) is the number of components of the star cover. Thus, the term of minimal total degree corresponds to a out-dominating set of minimum cardinality. Hence, that minimum total degree is the out-domination number of \(D\). ◻
We now present applications of star covers and their associated polynomials to the study of kk-Exact 1-Total Dominating Sets, a concept introduced in [11] . Furthermore, we explore an inequality relating the cardinalities of neighborhoods of independent sets to the size of the independent sets themselves. These results deepen the understanding of connections between domination parameters, independent sets and various star polynomials.
A \(k\)-bounded star-factor of \(G\) is a spanning subgraph of \(G\) consisting of node-disjoint components where each component is a star having at least one but no more than \(k\) edges.
Thus, a graph has a 1-bounded star-factor precisely when it has a perfect matching.
We call a set \(D\) of vertices of a graph \(G\) a \(k\),exact 1 – total dominating set if it is possible to find a spanning subgraph of \(G\) all of whose edges can be directed to form a directed graph \(G^{+}\) in such a manner that every vertex in \(D\) has outdegree at least one and at most \(k\), and every vertex in \(G^{+}\) has indegree exactly 1. In forming the directed graph \(G^{+}\) we are allowing each undirected edge \(xy\) in the spanning subgraph to be replaced with either one or both of the directed edges \(\overrightarrow{xy}\) or \(\overrightarrow{yx}\). To simplify the notation we shall refer to \(D\) as a \((k,1]\)-total dominating set, or simply a \((k,1]\)-set. In [11], the authors introduced the concept of a \(k\)-exact 1-total dominating set and established the following two theorems.
Theorem 8.2. Let \(k\geq2\). A graph \(G\) has a \(k\),exact 1 – total dominating set if and only if \(G\) has a \(k\)-bounded star-factor.
In the following theorem, \(N(S)\) denotes the set of neighbors of the nodes in the set \(S\). That is, \[N(S) = \{ v \mid v \text{ is adjacent to some node } u \in S \}.\]
Theorem 8.3. Let \(k\geq2\). The graph \(G\) has a \(k\)-bounded star-factor if and only if for every independent set \(I\) of nodes, it follows that \(k|N(I)|\geq|I|\).
The underlying graph of \(D\), denoted by \(U(D)\), is the undirected graph obtained from \(D\) by removing the directions on edges; and then replacing multiple edges by single edges.
Let \(C\) be a directed (sink / source) star cover where each component has less than \(k\)-edges but with no components nodes; then, \(C\) is called a \(k\)-bounded directed star-factor. By the above definitions, the underlying graph of a \(k\)-bounded directed star-factor is a \(k\)-bounded star-factor. is a \(k\)-bounded star-factor. Therefore, by the previous pair of theorems, we obtain the following result, which demonstrates connections between the existence of certain (directed) star covers of digraphs and the domination and independence properties of the underlying graph of \(D\).
Theorem 8.4. Let \(k \geq 2\). If a digraph \(D\) has a \(k\)-bounded directed star-factor, then its underlying graph \(U(D)\) satisfies the following two properties:
(i) \(U(D)\) has a \(k\)-exact 1-total dominating set.
(ii) For every independent set \(I\) of nodes in \(U(D)\), the inequality \[k |N(I)| \geq |I|,\] holds, where \(N(I)\) denotes the set of neighbours of nodes in \(I\).
Proof. By definitions, the underlying graph of a \(k\)-bounded directed star-factor is a \(k\)-bounded star-factor of \(U(D)\). Thus, by theorems 8.2 and 8.3, the result follows. ◻
We explicitly state the corresponding results for the directed star polynomial, the sink polynomial and the source polynomial of digraphs.
Theorem 8.5. Let \(D\) be a digraph of order \(n\), and let \(k\) be an integer with \(2 \leq k < n\). Suppose at least one of the following holds:
(i) The polynomial \(E(D; (\underline{x}, \underline{y}))\) contains a term in which all variables are elements of the set \(\{x_2, \dots, x_{k+1}, y_3, \dots, y_{k+1}\}\).
(ii) Either \(\widehat{E}(D; \underline{w})\) or \(\overset{\vee}{E}(D; \underline{w})\) contains a term in which all variables are elements of the set \(\{w_2, \dots, w_{k+1}\}\).
Then the underlying graph \(U(D)\) satisfies:
\(\bullet\) \(U(D)\) has a \(k\)-exact 1-total dominating set.
\(\bullet\) For every independent set \(I\) of nodes in \(U(D)\), \(k \cdot |N(I)| \geq |I|,\) where \(N(I)\) denotes the neighbourhood of \(I\).
We now introduce some notations. Suppose that \(P=1^{h_{1}}2^{h_{2}}\cdot\cdot\cdot n^{h_{n}}\) and \(Q=1^{j_{1}}2^{j_{2}}\cdot\cdot\cdot n^{j_{n}}\) are two partitions of \(n\), that is \(P\vdash n\) and \(Q\vdash n\). then write \(\underline{x}^{P}\) and \(\underline{y}^{Q}\) for \(x_{1}^{h_{1}}x_{2}^{h_{2}}\cdot\cdot\cdot x_{n}^{h_{n}}\) and \(y_{1}^{h_{1}}y_{2}^{h_{2}}\cdot\cdot\cdot y_{n}^{h_{n}}\), respectively. Let \(P\oplus Q\) be the integer partition \(1^{h_{1}+j_{1}}2^{h_{2}+j_{2}}\cdot\cdot\cdot n^{h_{n}+j_{n}},\) of the form \(c \, w_2^{h_2} w_3^{h_3} \cdots w_k^{h_k},\) with \(c \in \mathbb{Z}^+\).