Traffic network analysis via multidimensional split variational inequality problem with multiple output sets

1.   Introduction

All the graphs in the paper are finite, simple, connected, and without loops.

Graphs and their derived structures play a pivotal role in various domains, ranging from computer science and network analysis to chemistry and social sciences. Among these, domination and chromaticity are fundamental concepts with broad applications, including morphological analysis, communication networks, social network theory, and facility placement. In 1958, it appeared as the coefficient of external stability ^[2], and later on it was named the domination number. The study of domination began in the late 1950s, with its formalization as a "domination number" emerging in the 1960s through foundational work by Ore ^[23] and others. Since then, significant results have been established, such as the domination properties of planar graphs by MacGillivray and Seyffarth ^[22], and later refined by Henning and Goddard ^[10]. Liu et al. ^[20] studied network coherence analysis of $n$-polygon networks. Moreover, Liu et al. ^[19] conducted a graphical analysis of hierarchical networks. For more on chromaticity of graphs, we refer the reader to ^[9,24]. For more applications of graph-theoretic parameters in communication systems and network design, we refer the reader to ^[7,11,28,33].

Line graphs, an essential graph family, have received considerable attention due to their applications in diverse fields such as optimization ^[26], coding theory, and Hamiltonian graph studies ^[14]. These graphs transform the edge set of an original graph into vertices, preserving the adjacency relationships, thereby creating a powerful framework for analyzing structural and combinatorial properties. Harary and Nash-Williams ^[15] provided foundational insights into Eulerian and Hamiltonian line graphs, while Clark ^[6] and Brualdi and Shanny ^[4] contributed further to understanding their Hamiltonian properties. Recent studies, such as those by Zhong et al. ^[32], highlighted the significance of line graphs in the context of Hamiltonian connectivity and related metrics. Liu et al. ^[21] studied Zagreb indices of Eulerian graphs. For the extensive study of the traceable and Hamiltonian graphs, we refer the reader to, for instance, ^[18].

This paper focuses on two specific graph families–the pan graph and the lollipop graph–and explores their line graphs with respect to domination number, chromatic number, and Hamiltonian properties. Pan and lollipop graphs, characterized by their hybrid structures, have been extensively used in modeling problems where connectivity and domination play critical roles. Notably, their line graphs exhibit unique combinatorial features that merit detailed exploration. Siddiqui and James ^[27] provided initial insights into the chromatic and domination numbers of pan and lollipop graphs, which serve as a basis for extending these results to their line graphs.

Our contributions are threefold. First, we derive analytical formulas for the domination and chromatic numbers of the line graphs of pan and lollipop graphs, using established inequalities and structural properties ^[5,25]. Second, we examine the relationships between the chromatic and domination numbers of these graphs and their line graphs, offering insights into how these parameters influence each other. Finally, we analyze Hamiltonian and traceable properties, demonstrating that the line graph of a pan graph is Hamiltonian, while that of a lollipop graph is traceable, extending prior work on Hamiltonian structures ^[29]. These findings not only deepen the understanding of these graph families but also provide potential applications in network design, algorithm optimization, and combinatorial modeling.

In this paper, we obtain the analytical formulas for the domination and chromatic numbers of these graphs by using a well-known inequality $\gamma(G-e)-1 \leq \gamma(G)\leq \gamma(G-e)$, with the help of some known results. Then, we discuss the relation between the chromatic and domination number of pan graphs with the line graphs of pan graphs. Finally, we elaborate the Hamiltoniancity for these line graphs by showing that the line graph of a pan graph is Hamiltonian, while the line graph of a lollipop graph is traceable.

2.   Preliminaries

Let us start by recalling some useful definitions and results (we refer the reader to ^[30] for other notions not recalled). Let $G = (V, E)$ be a graph. A set $D$ of vertices of a simple graph $G$ is a dominating set if every vertex $u\in V(G) \setminus D$ is adjacent to a vertex $v \in D$. The dominating number (domination number) $\gamma(G)$ of a graph $G$ is the size of the smallest dominating set of $G$. A dominating set $D$ with $\vert D\vert = \gamma(G)$ is called a minimum dominating set, see Haynes and Henning ^[12]. A $\gamma$-set in $G$ is a dominating set of cardinality $\gamma$ in $G$.

The line graph $L'(G)$ ^[13] of a graph $G$ is the graph whose vertex set is $E(G)$ and two vertices $u, v \in V(L'(G))$ are adjacent if they are adjacent edges in $G$. A coloring or proper coloring for a graph $G$ is the process of assigning colors to the vertex set $V$ of $G$ in such a way that any two adjacent vertices of $G$ do not have the same color. The chromatic number $\chi (G)$ for a graph $G$ is the smallest or minimum number of colors necessary for a graph coloring. Recall that $P_n$ (resp. $C_n$) denotes a path (resp. cycle) of order $n$.

Since we are mainly interested in the domination number, we recall some known results on it.

Lemma 2.1. ^[12] If a graph $G$ of order $n$ has a vertex of degree $n-1$, then $\gamma(G) = 1$.

We refer to the following result for the domination number of the path and cycle graphs.

Proposition 2.1. ^[5,8] For $n\ge 3$, $\gamma(P_n) = \gamma(C_n) = \lceil \frac{n}{3}\rceil$ (that is, $\gamma = \frac{n}{3}$ if $n\equiv0(\mathrm{mod}\; 3)$ and $\gamma = \lceil \frac{n}{3}\rceil$ if $n\ge 6$).

Next, we give the following lower bound on the domination number of a graph in terms of its diameter.

Proposition 2.2. ^[17] For a connected graph $G$ with diameter $diam(G)$, we have

The next classical result bounds the domination number of a graph in terms of its order, size, and the maximum degree.

Theorem 2.1. ^[5] If $\Delta(G)$ is the maximum vertex-degree of a graph $G$ of order $p$ and size $q$, then

The next result delivers relations between the domination number of a graph in terms of its smallest degree $\delta(G)$.

Theorem 2.2. ^[5] (1) If $G$ is a graph of order $n$ and minimum degree $\delta$, then $\gamma(G)\le \frac{n}{\delta+1}\sum\limits_{j = 1}^{\delta+1} \frac{1}{j}$.

(2) If $G$ is a graph of order $n$ with $\delta(G) = 1$, then $\gamma(G)\le n/2$.

(3) If $G$ is a connected graph of order $n$ with $\delta(G) = 2$ and $n\ge 8$, then $\gamma(G)\le 2n/5$.

For more informations, see ^[3].

In ^[16], the following result is proved. Note that, by $G\cup G'$, we denote the disjoint union of two graphs, and the phrase below dominating set does not mean a minimal dominating set.

Proposition 2.3. If $uv$ is an edge of a connected graph $G$ and $G-uv = G_1\cup G_2$, then $\gamma(G)\le \gamma(G_1)+\gamma(G_2)$.

Proof. Let $uv$ be an edge of a connected graph such that $G-uv = G_1\cup G_2$. Let $S_i$, $i = 1, 2,$ be a dominating set of $G_i$. Let $S = S_1\cup S_2$, and then $N[S] = N[S_1\cup S_2] = N[S_1]\cup N[S_2] = V(G)$, and so $S$ is a dominating set for $G$, hence, $\gamma(G)\le \vert S\vert = \vert S_1\vert+\vert S_2\vert = \gamma(G_1)+\gamma(G_2)$. □

In ^[31], the following result is proved for an edge-deleted graph.

Theorem 2.3. ^[31] If $e\in E(G)$, then $\gamma(G-e)-1 \leq \gamma(G)\leq \gamma(G-e).$

A cycle which covers all the vertices of a graph $G$ is known as a Hamiltonian cycle. Similarly, a path covering all the vertices of a graph $G$ is a Hamiltonian path. A graph $G$ is Hamiltonian, if there exists a Hamiltonian cycle in $G$. A graph $G$ is traceable if there exists a Hamiltonian path in it. Obviously, if a graph is Hamiltonian then it is traceable. The converse is not true, in general.

Finally, let us discuss the domination number of the line graph of a complete graph on $k$ vertices. Recall that the line graph $G_k$ of a complete graph, also known as the triangular graph $T(k)$ (or $T_k$), is the graph whose vertices are the pairs of the $2$-subsets of $[k] = \{1, 2, \ldots, k\}$ and let us denote these $k\choose 2$ vertices with $v_1, v_2, \ldots, v_{k\choose 2}$. Two vertices $v_i, v_j$ of $G_k$ are adjacent if and only if $v_i\cap v_j\neq \emptyset$. These graphs have received widespread attention. More recently, the codes generated by the rows of the adjacency matrix of these graphs have also received attention. It is known that

If $k$ is even, a $\gamma$-set is given by $\{1, 2\}, \{3, 4\}, \ldots, \{k-1, k\}$ and $\gamma(G_k) = \bigg\lceil \frac{k-1}{2}\bigg\rceil$. If $k$ is odd, a $\gamma$-set of $G_k$ is $\{1, 2\}, \{3, 4\}, \ldots, \{k-2, k-1\}$ and $\gamma(G_k) = \frac{k-1}{2}$.

Let $G$ be a graph of order $n$, $m\ge 0$ be an integer, and $P_{m+1} = y_0y_1\ldots y_m$ be a path of length $m$. Pick a vertex $v_0$ in $G$, and the graph $G_{v_0}(m)$ (or simply $G(m)$) is the graph obtained from $G$ by identifying the vertex $v_0$ with the end vertex $y_0$ of $P_{m+1}$, that is, its vertex set consists of all the vertices of $G$ with those of $P_{m+1}$ with $v_0 = y_0$, so its order is $n+m$. Its edge set consists of all the edges of $G$ with those of $P_{m+1}$.

Thus, if $G = P_2$, then $G(m) = P_{m+2}$. When $G = C_{\nu}$, we have the graph $C_\nu(\mu)$, and in ^[1] the following result is proved.

Proposition 2.4. For every $\nu\ge 3$ and $\mu\ge 0$, $\gamma(C_\nu(\mu)) = \lceil\frac{\nu}{3}\rceil +\lceil\frac{\mu-1}{3}\rceil$.

Definition 2.1. If $m = 1$, the graph $C_\nu(1)$ is the pan graph $\Pi_n$. If $G = K_n$ is the complete graph on $n$ vertices, then $G(m) = K_n(m)$ is the lollipop graph $\mathcal L'_{n, m}$.

Thus, a lollipop graph $\mathcal{L'}_{\nu, \mu}$ is a graph obtained by joining the complete graph $(K_{\nu})$ to the $\mu$-order path graph $(P_{\mu})$ with a bridge. A pan graph $\prod_{\mu}$ is a graph obtained by joining a $\mu$-cycle $C_{\mu}$ to $K_1$ (singleton graph) with a bridge.

By Proposition 2.4, it follows that the domination number of the pan graph $\Pi_n$ is $\lceil\frac{n}{3}\rceil$.

Siddiqui and James, in ^[27], showed the following results for the pan and lollipop graphs.

Lemma 2.2. ^[27] Let $G = \prod_{\mu}$, and the domination number of $G$ is

Lemma 2.3. ^[27] Let $G = \prod_{\mu}$, and the chromatic number of $G$ is

Lemma 2.4. ^[27] Let $G = \mathcal{L}_{\nu, \mu}$. The domination number of $G$ is $\gamma(G) = \lceil\frac{\mu+2}{3}\rceil.$

Lemma 2.5. ^[27] Let $G = \mathcal{L}_{\nu, \mu}$. The chromatic number of $G$ is $\chi(G) = \nu.$

Here, we mention some more known results which play an important rule in our proofs. In 1979, Walikar and Acharya ^[31] showed that if $e \in E(G)$, then the following inequality holds for the domination number of $G$.

Theorem 2.4. ^[31] If $e = E(G)$, then $\gamma(G-e)-1 \leq \gamma(G)\leq \gamma(G-e).$

In 2006, Chartrand computed important results in his book ^[5] for the domination number of some well-known graphs. For the $\mu$-th order path graph, we have the following:

Lemma 2.6. ^[5] $\gamma(P_\mu) = \lceil \frac{\mu}{3}\rceil$, for $\mu \geq 1.$

In ^[8], Chartrand and Zhang computed the domination number for $C_\mu$, a cyclic graph of order $\mu$, as given in the following lemma.

Lemma 2.7. ^[8] $\gamma(C_\mu) = \lceil \frac{\mu}{3}\rceil$, for $\mu \geq 3.$

Here, we extend the result of Chartrand and Zhang ^[8] for $C_{\mu+1}$, because of their implication in our next results.

Lemma 2.8. Let $C_{\mu+1}$ be the ($\mu+1$)-th order cyclic graph. Then, the domination number of $C_{\mu+1}$ is

The proof of Lemma 2.8 is similar to the proof of Chartrand and Zhang ^[8].

Next, we present the main results of this work.

3.   The domination number of the line graphs

In this paper, we study the domination number in the line graphs of lollypop and pan graphs. The next subsection investigates minimizing dominating sets in the line graphs of lollypop graphs.

3.1.   Minimal dominating sets in the line graph of $C_\nu(\mu)$

Note that a cycle of length $n$ is isomorphic to its line graph, and so $L'(C_n)\simeq C_n$. Let $G = \Pi_n = C_\nu(1)$. Let $v_1, \ldots, v_\nu, u$ be its vertices, and then $L'(G)$ is a graph of order $\nu+1$ and it may be seen as a cycle $C_\nu$ with an extra vertex, say, $w$ plus two edges connecting $w$ with two adjacent vertices of $C_\nu$. Next, we prove that this graph is a subgraph of the line graph of $C_\nu(\mu)$.

Let us denote the vertices of $C_\nu(\mu)$ with $v_1, \ldots, v_\nu, u_{\nu+1}, \ldots, u_{\nu+\mu}$. Denote the vertices of its line graph with $p_{ij}$, where $i$ and $j$ are the pairs of indices of the endpoints of the edges of $C_\nu(\mu)$:

so it consists of the cycle

the cycle

and the path

Consider the edge $e = p_{n1}p_{n, n+1}$ of $G = L'(C_\nu(\mu))$ and let $G' = L'(C_\nu(\mu))- e$. Then,

Since $G'$ is isomorphic to $C_\nu(\mu)$, by Proposition 2.4 and Eq (3.1), we obtain

Now, consider the edge $e' = p_{n-1, n}p_{n1}$ of $G$ and let $G'' = G- e'$. Then,

Thus, $G''$ is isomorphic to $C_{\nu+1}(\mu-1)$. Note that one has to remark that for $m = 1$, we have $G'' = C_{\nu+1}$. By Proposition 2.4 and Eq (3.3), considering $m\ge 2$ implies that

Thus, if $\mu = 1$, we obtain the domination number for the line graph of the pan graph $L'(C_\nu(1))$ from Eq (3.4). Next, we conjecture that the domination of $L'(C_\nu(\mu))$ for general $\mu$ is as follows:

Conjecture 3.1. The domination number of $G = L'(C_\nu(\mu))$ is computed by the following formula:

3.2.   Minimal dominating sets in the line graph of $\Pi_n$

In this subsection, we discuss the main results of our study. Before jumping to the main results, we start with some known results which perform a crucial rule in our proofs. Alikhani et al. ^[1] computed the domination number for $C_\nu(\mu)$, where $C_\nu(\mu)$ is shown in Figure 1. Moreover, Figures 2 and 3 deliver the pan graph $\Pi_{3}$ and lollipop graphs $\mathcal{L'}_{3, 1}$ and $\mathcal{L'}_{4, 1}$, respectively.

As a special case, we obtain the domination number of $C_3(\mu)$, see Figure 4.

Corollary 3.1. For $\nu = 3$ and $\mu \geq 0$, as shown in Figure 4, $\gamma(C_3(\mu)) = 1+\lceil \frac{\mu-1}{3}\rceil$.

Proof. The proof of this corollary is immediately understood from Proposition 2.4 by considering $\nu = 3$. □

Corollary 3.2. For $\nu = 4$ and $\mu \geq 0$, as shown in Figure 5, the domination number of $\gamma(C_4(\mu))$ is

for all $k \geq 1.$

Proof. The proof of this corollary is immediately from understood Proposition 2.4 by considering $\nu = 4$. □

Theorem 3.1. For $\mu \geq 3$, let $G_\mu = L'(\Pi_\mu)$. Then,

If $\mu = 3k$, then the domination number of $G_\mu$ is

Proof. Consider the $\mu$-th-order line graph of the pan graph $L'(\Pi_\mu)$, with vertices labeled as in Figure 6.

In any case, by Theorem 2.4, we have that $\gamma(G_{\mu})\le \lceil\frac{\mu}{3}\rceil$. Moreover, a minimal dominating set of the cycle $C_\mu$ with a vertex in $v_1$ or $v_{\mu}$ is a dominating set in the pan graph and so we have the result.

We prove this result by using the inequality $\gamma(G-e)-1 \leq \gamma(G)\leq \gamma(G-e)$ given in Theorem 2.4. Let us apply Theorem 2.4 to $e = v_\mu u_1$ in $G_\mu$, and we obtain the following inequality:

Assume $\mu = 3k$ and let $\gamma(G_\mu) = \lceil \mu/3\rceil -1$. Thus, $\gamma(G_\mu) = k-1$.

Now, consider $e = v_1v_\mu$ in Figure 6, and by Theorem 2.4 we get

and so

It follows that

which is a contradiction, and so for $\mu = 3k$ we have $\gamma(G_\mu) = \lceil\mu/3\rceil$. □

In the next result, we investigate the domination number of the join of two graphs $H$ and $K$.

Theorem 3.2. Let $H$ and $K$ be any two graphs with vertex sets $V(H)$ and $V(K)$, respectively. Let $G'$ be a graph obtained by joining $H$ and $K$ through a bridge $e = uv$, where $u \in V(H)$ and $v \in V(K)$. Then $\gamma(G') = \gamma(H)+\gamma(K)$ or $\gamma(G') = \gamma(H)+\gamma(K)-1$.

Proof. Let $H$ and $K$ be any two graphs and $G'$ be a graph obtained by connecting $H$ and $K$ through a bridge $e = uv$, where $u \in V(H)$ and $v \in V(K)$ as shown in Figure 7.

Therefore, the graph $G'$ has $V(G') = V(H)\cup V(K)$ with $V(H)\cap V(K) = \varnothing$ and $E(G') = E(H)\cup E(K) \cup \{e \}$. Now, for any dominating set $\mathfrak{D}$ of the graph $G'$,

and $\big(\mathfrak{D} \cap V(H)\big)\cap \big(\mathfrak{D} \cap V(K)\big) = \varnothing.$

Moreover,

If ${\mathcal D}_1$ is a minimum dominating set of $H$ and ${\mathcal D}_2$ is a minimum dominating set of $K$, then ${\mathcal D} = {\mathcal D}_1\cup {\mathcal D}_2$ is a dominating set of $G'$ and so

Let $\mathfrak{D}$ be a minimum dominating set of $G'$ such that $\gamma(G') = \gamma(H)+\gamma(K)-q$, where $q \geq 2$. Then by Eq (3.9), $|\mathfrak{D}| = |\mathfrak{D} \cap V(H)|+|\mathfrak{D} \cap V(K)| = \gamma(G') = \gamma(H)+\gamma(K)-q$, where $q \geq 2$. Therefore, $|\mathfrak{D} \cap V(H)| = \gamma(H)-q_1$ and $|\mathfrak{D} \cap V(K)| = \gamma(K)-q_2$ with $q_1+q_2 = q$.

Suppose if neither $q_1 = 0$ nor $q_2 = 0$, then $\mathfrak{D} \cap V(H)$ will not be the dominating set of $H$. But as $\mathfrak{D}$ is the dominating set of $G'$, some of the vertices of $\mathfrak{D} \cap V(K)$ must dominate the vertices of $H$ which are not dominated by the vertices of $\mathfrak{D} \cap V(H)$. But as $e = uv$ is the only edge that connects $H$ with $K$, we must have that $v \in \mathfrak{D} \cap V(K)$ and $u \notin \mathfrak{D} \cap V(H)$. Similarly if we consider the set $\mathfrak{D} \cap V(K)$, then it is not the dominating set of $K$, and hence by above the argument we have $u \in \mathfrak{D} \cap V(H)$ and $v \notin \mathfrak{D} \cap V(K)$. This contradiction shows that both $q_1$ and $q_2$ cannot be non-zero simultaneously. Hence, either $q_1 = 0$ or $q_2 = 0$.

Without loss of generality, we take $q_1 = 0$, and then $|\mathfrak{D} \cap V(H)| = \gamma(H)$ and $|\mathfrak{D} \cap V(K)| = \gamma(K)-q$, where $q \geq 2$. This implies that $K-{v}$ has a dominating set $\mathfrak{D} \cap V(K)$ with cardinality less than or equal to $\gamma(K)-q$. Hence, $\big(\mathfrak{D} \cap V(K)\big)\cup \{v\}$ is a dominating set of $K$ with cardinality less than or equal to $\gamma(K)-(q-1)$, where $q > 1$. This contradicts the hypothesis of the dominating set. Hence, $q \leq 1$, thus, $\gamma(H)+ \gamma(K)-1 \leq \gamma(G') \leq \gamma(H)+ \gamma(K)$. □

Regarding Theorem 3.2, we refer to the work of Rajasekar and Nagarajan ^[25].

Corollary 3.3. For $\mu = 3 k$, the domination number of $\Pi_{\mu}$ and $L'(\Pi_{\mu})$ satisfy the following relation:

Proof. Comparing Lemma 2.2 and Theorem 3.1 completes the proof of this corollary. □

Theorem 3.3. For $\nu = 3$, let $G_{3, \mu} = L'(\mathcal{L'}_{3, \mu})$, where $\mu \geq1$. The domination number of $G_{3, \mu}$ is

Proof. For the fixed value of $\nu = 3$ and $\mu \geq 1$, the line graph of the lollipop graph $L'(\mathcal{L'}_{3, \mu})$ is given in Figure 8.

From Figure 8, it is clear that the line graph $G_{3, \mu} = L'(\mathcal{L'}_{3, \mu})$ is the combination of two graphs $H$ and $K$, connected by a bridge $e = v_1v_2$. Now, to prove this result, we use Theorem 3.2, which reveals the domination number of two graphs connected by a bridge. Thus, from Theorem 3.2, we have

Here, the domination number of the connected graph $H$ is $1$, i.e., $\gamma(H) = 1$. The connected graph $K$ is a $(\mu-1)$-th-order path graph $P_{\mu-1}$ with domination number $\gamma(P_{\mu-1}) = \lceil \frac{\mu-1}{3} \rceil$.

Equation (3.10) implies that

This completes the proof of this theorem. □

Next, we present a short result on the domination number in terms of the following lemma.

Lemma 3.1. For a given graph $G_{4, 2} = L'(\mathcal{L'}_{4, 2})$ as shown in Figure 9, the domination number is $G_{4, 2} = 2$.

Proof. From Figure 9, the minimal possible dominating set is $\{u_1, v_1 \}$, and hence $\gamma(G_{4, 2}) = 2$.

Theorem 3.4. For $\nu = 4$, let $G_{4, \mu} = L'(\mathcal{L'}_{4, \mu})$, where $\mu \geq1$. The domination number of $G_{4, \mu}$ is

Proof. For the fixed value of $\nu = 4$ and $\mu \geq 1$, the line graph of the lollipop graph $L'(\mathcal{L'}_{4, \mu})$ is given in Figure 10.

From Figure 10, it is clear that the line graph $G_{3, \mu} = L'(\mathcal{L'}_{3, \mu})$ is the combination of two graphs $H$ and $K$, connected by a bridge $e = v_2v_3$. Now, to prove this result, we use Theorem 3.2, which reveals the domination number of two graphs connected by a bridge. Thus, from Theorem 3.2, we have

In Lemma 3.1, we showed that the domination number of a connected graph $H$ is $2$, i.e., $\gamma(H) = 2$. The connected graph $K$ is a ($\mu-2$)-th-order path graph such that $P_{\mu-2}$ has the domination number $\gamma(P_{\mu-2}) = \lceil \frac{\mu-2}{3} \rceil$.

Equation (3.11) implies that

This completes the proof of this theorem. □

Here, we have to present a short result on the domination number in terms of a lemma.

Lemma 3.2. For a given graph $G_{5, 1} = L'(\mathcal{L'}_{5, 1})$ as shown in Figure 11, the domination number is $G_{5, 1} = 2$.

Proof. From Figure 11, the minimal possible dominating set is $\{u_1, u_{10}\}$ and hence $\gamma(G_{5, 1}) = 2$.

Theorem 3.5. For $\nu = 5$, let $G_{5, \mu} = L'(\mathcal{L'}_{5, \mu})$, where $\mu \geq1$. The domination number of $G_{5, \mu}$ is

Proof. For the fixed value of $\nu = 5$ and $\mu \geq 1$, the line graph of the lollipop graph $L'(\mathcal{L'}_{5, \mu})$ is given in Figure 12.

From Figure 12 it is clear that the line graph $G_{5, \mu} = L'(\mathcal{L'}_{5, \mu})$ is the combination of two graphs $H$ and $K$, connected by a bridge $e = v_1v_2$. Now, to prove this result, we use Theorem 3.2, which reveals about the domination number of two graphs connected by a bridge. Thus, from Theorem 3.2, we have

In Lemma 3.2, we showed that the domination number of a connected graph $H$ is $2$, i.e., $\gamma(H) = 2$. The connected graph $K$ is a ($\mu-1$)-th-order path graph such that $P_{\mu-1}$ has the domination number $\gamma(P_{\mu-1}) = \lceil \frac{\mu-1}{3} \rceil$.

Equation (3.12) implies that

This completes the proof of this theorem. □

Tables 1–3 give us the direction for Conjecture 3.1, and hence the idea to generalize the results for all $\mu \geq 1$ and $\nu \geq 3$.

Next, we generalize these results from to $L'(\mathcal{L'}_{\nu, \mu})$ by getting idea from above theorems and those of Tables 1–3. We present the general form for the domination number of $L'(\mathcal{L'}_{\nu, \mu})$ in the following conjecture.

Conjecture 3.2. For any $\nu \geq 3$, let $G_{\nu, \mu} = L'(\mathcal{L'}_{\nu, \mu})$, where $\mu \geq1$. The domination number of $G_{\nu, \mu}$ is

4.   Chromaticity

This section is dedicated for studying the chromaticity in the line graphs of pan and lollypop graphs.

From our observation and theory of chromatic numbers, the chromatic number for the union of two graphs $G$ and $G'$ is always the maximum one, that is, $\chi(G \cup G') = \max\{\chi(G), \chi(G')\}$.

Theorem 4.1. Let $G_{\mu} = L'(\Pi_{\mu})$. The chromatic number of $G_\mu$ is $\chi(G_\mu) = 3$.

Proof. We know that, for $\mu$-order cyclic graph, the chromatic number is given by

It is also clear that $G_\mu = C_\mu \cup C_3$, as shown in Figure 6. From the theory of chromatic numbers and our observation we have $\chi(G \cup G') = \max(\chi(G), \chi(G'))$. Clearly, $\max(\chi(C_\mu), \chi(C_3)) = \chi(C_3) = 3$, and hence $\chi(G_\mu) = 3$, which completes the proof. □

Proposition 4.1. Let $G_{\nu, \mu} = L'(\mathcal{L'}_{\nu, \mu})$, where $3 \leq \nu \leq 5$, and $\mu \geq1$. Then, the chromatic number of $G_{\nu, \mu}$ is

Proof. To prove this result, we assign colors to the vertices of $G_{\nu, \mu}$ in such a way that if any two vertices are adjacent they will be assign different colors. The colors and the notations that we use in this theorem are red "r", blue "b", yellow "y", sky blue "s", green "g", and so on. First, we prove some base results and then we generalize those results. Consider $V(G_{\nu, \mu})$ to be the set of vertices and $D(G_{\nu, \mu})$ to be the set of colors for $V(G_{\nu, \mu})$. Then we discuss the following cases.

Case 1. $\nu = 3\; \text{and}\; \mu \geq 1$

See Figure 13 for the line graph $L'(\mathcal{L'}_{3, \mu})$.

Case 2. $\nu = 4\; \text{and}\; \mu \geq 1$

See Figure 14 for the line graph $L'(\mathcal{L'}_{4, \mu})$.

Case 3. $\nu = 5\; \text{and}\; \mu \geq 1$

See Figure 15 for the line graph $L'(\mathcal{L'}_{5, \mu})$.

Since there are $(\frac{\nu(\nu-1)}{2}+\mu)$ vertices in the line graph of the lollipop graph, we think that such a result may be generalized, that is, the following conjecture is true.

Conjecture 4.1. Let $G_{\nu, \mu} = L'(\mathcal{L'}_{\nu, \mu})$ where $\nu \geq3$ and $\mu \geq1$. Then, the chromatic number of $G_{\nu, \mu}$ is

Corollary 4.1. Let $G = \mathcal{L'}_{\nu, \mu}$, and $H' = L'(\mathcal{L'}_{\nu, \mu})$, with $3 \leq \nu \leq 5$. Then, for the chromatic number of $G$ and $H'$, the following relation holds:

Proof. Comparing Lemma 2.5 and Proposition 4.1 completes the proof of this corollary.□

The following proposition delivers the chromatic number of the line graph of a pan graph.

Proposition 4.2. For $\mu \geq 3$, the chromatic numbers of $\Pi_{\mu}$ and $L'(\Pi_{\mu})$ satisfy the following relation:

(1) $\chi(\Pi_{\mu}) = \chi(L'(\Pi_{\mu})), \; if \; n\; is\; odd.$

(2) $\chi(\Pi_{\mu}) = 1+\chi(L'(\Pi_{\mu})), \; if \; n\; is\; even.$

Proof. From the Siddiqui and James results in Lemma 2.3, we say that

In Theorem 4.1, we showed that

Comparing Eqs (4.2) and (4.3) completes the proof of this corollary. □

5.   Hamiltoniancity and traceability

In this section, we discuss the Hamiltoniancity of line graphs of pan graphs and lollipop graphs. Here, we prove that $L'(\Pi_{\mu})$ is Hamiltonian, while $L'(\mathcal{L'}_{\nu, \mu})$ is traceable. Now, we introduce some undefined notations and symbols, which we will use in this part. Let $H_c$ (resp. $H_p$) be a Hamiltonian cycle (resp. path). The symbol $\sim$ represents the adjacency relation of two vertices, while the symbol $\circ$ represents the adjacency relation of a vertex to the set of vertices.

Theorem 5.1. Let $G = L'(\Pi_{\mu})$, where $\mu\geq3$. Then $G$ is Hamiltonian.

Proof. To show that $G$ is Hamiltonian, we construct a Hamiltonian cycle in $G$. Let $y$ denote an arbitrary vertex of $G$. Consider the labeling of the vertices of $G = L'(\Pi_\mu)$ in Figure 16, and following is the Hamiltonian cycle with the same initial and end vertex $y$:

Theorem 5.2. Let $G = L'(\mathcal{L'}_{\nu, \mu})$, where $\nu\geq3$. Then, $G$ is traceable.

Proof. To show that $G$ is traceable, we have to construct a Hamiltonian path in $L'(\mathcal{L'}_{\nu, \mu})$. Let $x_q$ and $y_q$ denote the arbitrary vertices of $L'(\mathcal{L'}_{\nu, \mu})$. Consider the vertex labeling of $G = L'(\mathcal{L'}_{\nu, \mu})$ in Figure 17, and the following three cases embrace the Hamiltonian path between $x_q$ and $y_q$.

Case 1. For $\nu = 3$ and $\mu \geq 1$,

Case 2. For $\nu = 4$ and $\mu \geq 1$,

Case 3. For $\nu\geq 5$ and $\mu \geq 1$,

6.   Conclusions

In this study, we investigated the domination number, chromatic number, and Hamiltonian properties of the line graphs of pan and lollipop graphs. Analytical formulas for the domination and chromatic numbers were derived, and their interrelationships with the original graphs were established. We demonstrated that the line graph of a pan graph is Hamiltonian, while that of a lollipop graph is traceable.

These findings enrich the theoretical understanding of line graphs and highlight their structural uniqueness. The contributions are significant for practical applications in network design, optimization, and graph algorithm development, where properties like domination and Hamiltonian paths are critical.

However, the study is limited to specific families of graphs (pan and lollipop) and their line graphs, leaving other graph families unexplored. Future research could extend this work by examining similar properties in broader classes of graphs or exploring algorithmic applications based on these structural insights. Additionally, computational methods could complement theoretical approaches to validate and generalize the findings further.

Author contributions

Yubin Zhong and Sakander Hayat: Conceptualization, Methodology, Validation, Formal analysis, Investigation, Writing–original draft preparation, Writing–review and editing, Visualization; Suliman Khan and Vito Napolitano: Formal analysis, Investigation, Writing–original draft preparation, Editing; Mohammed J. F. Alenazi: Methodology, Validation, Resources, Writing–original draft preparation. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Y. Zhong was sponsored by the Ministry of Science and Technology of China with grant No. WGXZ2023054L. S. Khan and V. Napolitano were partially supported by the Italian National Group for Algebraic and Geometric Structures and their Applications (GNSAGA-INdAM). V. Napolitano was partially supported by the COMPACT project of the Universitá della Campania "Luigi Vanvitelli". S. Hayat was supported by a UBD Faculty Research Grant with grant No. UBD/RSCH/1.4/FICBF(b)/2022/053. M. J. F. Alenazi extends his appreciation to the Researcher Supporting Project number (RSPD2025R582), King Saud University, Riyadh, Saudi Arabia.

Conflict of interest

The authors declare that they have no known competing financial interests.