
Line graphs are a fundamental class of graphs extensively studied for their structural properties and applications in diverse fields such as network design, optimization, and algorithm development. Pan and lollipop graphs, with their distinctive hybrid structures, offer a fertile ground for exploring combinatorial properties in their line graphs. Motivated by the need to better understand domination, chromaticity, and Hamiltonian properties in line graphs, this study examined the line graphs of pan and lollipop graphs. These investigations were inspired by their potential applications in connectivity analysis and optimization in networks. We derived analytical formulas for the domination and chromatic numbers of these line graphs, established relationships between these parameters and their corresponding original graphs, and proved that the line graph of a pan graph is Hamiltonian while that of a lollipop graph is traceable. The methodology combines established theoretical results and inequalities, including domination bounds and chromaticity relations, with rigorous combinatorial analysis. Our results not only contribute to the theoretical understanding of line graphs but also have implications for practical problems in network optimization and graph algorithm design, opening avenues for further research into hybrid graph structures.
Citation: Yubin Zhong, Sakander Hayat, Suliman Khan, Vito Napolitano, Mohammed J. F. Alenazi. Combinatorial analysis of line graphs: domination, chromaticity, and Hamiltoniancity[J]. AIMS Mathematics, 2025, 10(6): 13343-13364. doi: 10.3934/math.2025599
[1] | Betül ATAY ATAKUL . Stability and domination exponentially in some graphs. AIMS Mathematics, 2020, 5(5): 5063-5075. doi: 10.3934/math.2020325 |
[2] | Suliman Khan, Sakander Hayat, Asad Khan, Muhammad Yasir Hayat Malik, Jinde Cao . Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications. AIMS Mathematics, 2021, 6(4): 3947-3973. doi: 10.3934/math.2021235 |
[3] | Abel Cabrera-Martínez, Andrea Conchado Peiró . On the {2}-domination number of graphs. AIMS Mathematics, 2022, 7(6): 10731-10743. doi: 10.3934/math.2022599 |
[4] | Sufyan Asif, Muhammad Khalid Mahmood, Amal S. Alali, Abdullah A. Zaagan . Structures and applications of graphs arising from congruences over moduli. AIMS Mathematics, 2024, 9(8): 21786-21798. doi: 10.3934/math.20241059 |
[5] | Igal Sason . On H-intersecting graph families and counting of homomorphisms. AIMS Mathematics, 2025, 10(3): 6355-6378. doi: 10.3934/math.2025290 |
[6] | Igal Sason . Observations on graph invariants with the Lovász ϑ-function. AIMS Mathematics, 2024, 9(6): 15385-15468. doi: 10.3934/math.2024747 |
[7] | Gaixiang Cai, Fengru Xiao, Guidong Yu . The identification numbers of lollipop graphs. AIMS Mathematics, 2025, 10(4): 7813-7827. doi: 10.3934/math.2025358 |
[8] | G. Nandini, M. Venkatachalam, Raúl M. Falcón . On the r-dynamic coloring of subdivision-edge coronas of a path. AIMS Mathematics, 2020, 5(5): 4546-4562. doi: 10.3934/math.2020292 |
[9] | Jin Cai, Shuangliang Tian, Lizhen Peng . On star and acyclic coloring of generalized lexicographic product of graphs. AIMS Mathematics, 2022, 7(8): 14270-14281. doi: 10.3934/math.2022786 |
[10] | T. Deepa, Raúl M. Falcón, M. Venkatachalam . On the r-dynamic coloring of the direct product of a path with either a complete graph or a wheel graph. AIMS Mathematics, 2021, 6(2): 1470-1496. doi: 10.3934/math.2021090 |
Line graphs are a fundamental class of graphs extensively studied for their structural properties and applications in diverse fields such as network design, optimization, and algorithm development. Pan and lollipop graphs, with their distinctive hybrid structures, offer a fertile ground for exploring combinatorial properties in their line graphs. Motivated by the need to better understand domination, chromaticity, and Hamiltonian properties in line graphs, this study examined the line graphs of pan and lollipop graphs. These investigations were inspired by their potential applications in connectivity analysis and optimization in networks. We derived analytical formulas for the domination and chromatic numbers of these line graphs, established relationships between these parameters and their corresponding original graphs, and proved that the line graph of a pan graph is Hamiltonian while that of a lollipop graph is traceable. The methodology combines established theoretical results and inequalities, including domination bounds and chromaticity relations, with rigorous combinatorial analysis. Our results not only contribute to the theoretical understanding of line graphs but also have implications for practical problems in network optimization and graph algorithm design, opening avenues for further research into hybrid graph structures.
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 γ(G−e)−1≤γ(G)≤γ(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.
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∈V(G)∖D is adjacent to a vertex v∈D. The dominating number (domination number) γ(G) of a graph G is the size of the smallest dominating set of G. A dominating set D with |D|=γ(G) is called a minimum dominating set, see Haynes and Henning [12]. A γ-set in G is a dominating set of cardinality γ 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∈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 χ(G) for a graph G is the smallest or minimum number of colors necessary for a graph coloring. Recall that Pn (resp. Cn) 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 γ(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≥3, γ(Pn)=γ(Cn)=⌈n3⌉ (that is, γ=n3 if n≡0(mod3) and γ=⌈n3⌉ if n≥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
γ(G)≥13(diam(G)+1). |
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 Δ(G) is the maximum vertex-degree of a graph G of order p and size q, then
⌈p1+Δ(G)⌉≤γ(G)≤p−Δ(G). |
The next result delivers relations between the domination number of a graph in terms of its smallest degree δ(G).
Theorem 2.2. [5] (1) If G is a graph of order n and minimum degree δ, then γ(G)≤nδ+1δ+1∑j=11j.
(2) If G is a graph of order n with δ(G)=1, then γ(G)≤n/2.
(3) If G is a connected graph of order n with δ(G)=2 and n≥8, then γ(G)≤2n/5.
For more informations, see [3].
In [16], the following result is proved. Note that, by G∪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=G1∪G2, then γ(G)≤γ(G1)+γ(G2).
Proof. Let uv be an edge of a connected graph such that G−uv=G1∪G2. Let Si, i=1,2, be a dominating set of Gi. Let S=S1∪S2, and then N[S]=N[S1∪S2]=N[S1]∪N[S2]=V(G), and so S is a dominating set for G, hence, γ(G)≤|S|=|S1|+|S2|=γ(G1)+γ(G2).
In [31], the following result is proved for an edge-deleted graph.
Theorem 2.3. [31] If e∈E(G), then γ(G−e)−1≤γ(G)≤γ(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 Gk of a complete graph, also known as the triangular graph T(k) (or Tk), is the graph whose vertices are the pairs of the 2-subsets of [k]={1,2,…,k} and let us denote these (k2) vertices with v1,v2,…,v(k2). Two vertices vi,vj of Gk are adjacent if and only if vi∩vj≠∅. 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
γ(Gk)=⌈k−12⌉. |
If k is even, a γ-set is given by {1,2},{3,4},…,{k−1,k} and γ(Gk)=⌈k−12⌉. If k is odd, a γ-set of Gk is {1,2},{3,4},…,{k−2,k−1} and γ(Gk)=k−12.
Let G be a graph of order n, m≥0 be an integer, and Pm+1=y0y1…ym be a path of length m. Pick a vertex v0 in G, and the graph Gv0(m) (or simply G(m)) is the graph obtained from G by identifying the vertex v0 with the end vertex y0 of Pm+1, that is, its vertex set consists of all the vertices of G with those of Pm+1 with v0=y0, so its order is n+m. Its edge set consists of all the edges of G with those of Pm+1.
Thus, if G=P2, then G(m)=Pm+2. When G=Cν, we have the graph Cν(μ), and in [1] the following result is proved.
Proposition 2.4. For every ν≥3 and μ≥0, γ(Cν(μ))=⌈ν3⌉+⌈μ−13⌉.
Definition 2.1. If m=1, the graph Cν(1) is the pan graph Πn. If G=Kn is the complete graph on n vertices, then G(m)=Kn(m) is the lollipop graph L′n,m.
Thus, a lollipop graph L′ν,μ is a graph obtained by joining the complete graph (Kν) to the μ-order path graph (Pμ) with a bridge. A pan graph ∏μ is a graph obtained by joining a μ-cycle Cμ to K1 (singleton graph) with a bridge.
By Proposition 2.4, it follows that the domination number of the pan graph Πn is ⌈n3⌉.
Siddiqui and James, in [27], showed the following results for the pan and lollipop graphs.
Lemma 2.2. [27] Let G=∏μ, and the domination number of G is
γ(G)={μ3,for μ=3k,⌈μ3⌉,otherwise. |
Lemma 2.3. [27] Let G=∏μ, and the chromatic number of G is
χ(G)={3,if μ is odd,2,if μ is even. |
Lemma 2.4. [27] Let G=Lν,μ. The domination number of G is γ(G)=⌈μ+23⌉.
Lemma 2.5. [27] Let G=Lν,μ. The chromatic number of G is χ(G)=ν.
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∈E(G), then the following inequality holds for the domination number of G.
Theorem 2.4. [31] If e=E(G), then γ(G−e)−1≤γ(G)≤γ(G−e).
In 2006, Chartrand computed important results in his book [5] for the domination number of some well-known graphs. For the μ-th order path graph, we have the following:
Lemma 2.6. [5] γ(Pμ)=⌈μ3⌉, for μ≥1.
In [8], Chartrand and Zhang computed the domination number for Cμ, a cyclic graph of order μ, as given in the following lemma.
Lemma 2.7. [8] γ(Cμ)=⌈μ3⌉, for μ≥3.
Here, we extend the result of Chartrand and Zhang [8] for Cμ+1, because of their implication in our next results.
Lemma 2.8. Let Cμ+1 be the (μ+1)-th order cyclic graph. Then, the domination number of Cμ+1 is
γ(Cμ+1)={⌈μ+13⌉,if μ=3k, for all k≥1,⌈μ3⌉,if μ=3k+1, or 3k+2, for all k≥1. |
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.
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.
Note that a cycle of length n is isomorphic to its line graph, and so L′(Cn)≃Cn. Let G=Πn=Cν(1). Let v1,…,vν,u be its vertices, and then L′(G) is a graph of order ν+1 and it may be seen as a cycle Cν with an extra vertex, say, w plus two edges connecting w with two adjacent vertices of Cν. Next, we prove that this graph is a subgraph of the line graph of Cν(μ).
Let us denote the vertices of Cν(μ) with v1,…,vν,uν+1,…,uν+μ. Denote the vertices of its line graph with pij, where i and j are the pairs of indices of the endpoints of the edges of Cν(μ):
p12,p23,…,pn−1,n,pn1,pn,n+1,…,pn+m−1,n+m, |
so it consists of the cycle
Cn:p12p23…pn−1,npn1, |
the cycle
C3:pn−1,npn1pn,n+1, |
and the path
pn,n+1pn+1,n+2…pn+m−1,n+m. |
Consider the edge e=pn1pn,n+1 of G=L′(Cν(μ)) and let G′=L′(Cν(μ))−e. Then,
γ(G′)−1≤γ(G)≤γ(G′). | (3.1) |
Since G′ is isomorphic to Cν(μ), by Proposition 2.4 and Eq (3.1), we obtain
⌈ν3⌉+⌈μ−13⌉−1≤γ(G)≤⌈ν3⌉+⌈μ−13⌉. | (3.2) |
Now, consider the edge e′=pn−1,npn1 of G and let G″=G−e′. Then,
γ(G″)−1≤γ(G)≤γ(G″). | (3.3) |
Thus, G″ is isomorphic to Cν+1(μ−1). Note that one has to remark that for m=1, we have G″=Cν+1. By Proposition 2.4 and Eq (3.3), considering m≥2 implies that
⌈ν+13⌉+⌈μ−23⌉−1≤γ(G)≤⌈ν+13⌉+⌈μ−23⌉. | (3.4) |
Thus, if μ=1, we obtain the domination number for the line graph of the pan graph L′(Cν(1)) from Eq (3.4). Next, we conjecture that the domination of L′(Cν(μ)) for general μ is as follows:
Conjecture 3.1. The domination number of G=L′(Cν(μ)) is computed by the following formula:
γ(G)=⌈ν3⌉+⌈μ−13⌉. |
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ν(μ), where Cν(μ) is shown in Figure 1. Moreover, Figures 2 and 3 deliver the pan graph Π3 and lollipop graphs L′3,1 and L′4,1, respectively.
As a special case, we obtain the domination number of C3(μ), see Figure 4.
Corollary 3.1. For ν=3 and μ≥0, as shown in Figure 4, γ(C3(μ))=1+⌈μ−13⌉.
Proof. The proof of this corollary is immediately understood from Proposition 2.4 by considering ν=3.
Corollary 3.2. For ν=4 and μ≥0, as shown in Figure 5, the domination number of γ(C4(μ)) is
γ(C4(μ))=2+⌈μ−13⌉, |
for all k≥1.
Proof. The proof of this corollary is immediately from understood Proposition 2.4 by considering ν=4.
Theorem 3.1. For μ≥3, let Gμ=L′(Πμ). Then,
⌈μ3⌉−1≤γ(Gμ)≤⌈μ3⌉. |
If μ=3k, then the domination number of Gμ is
γ(Gμ)=⌈μ3⌉. |
Proof. Consider the μ-th-order line graph of the pan graph L′(Πμ), with vertices labeled as in Figure 6.
In any case, by Theorem 2.4, we have that γ(Gμ)≤⌈μ3⌉. Moreover, a minimal dominating set of the cycle Cμ with a vertex in v1 or vμ is a dominating set in the pan graph and so we have the result.
We prove this result by using the inequality γ(G−e)−1≤γ(G)≤γ(G−e) given in Theorem 2.4. Let us apply Theorem 2.4 to e=vμu1 in Gμ, and we obtain the following inequality:
γ(Πμ)−1≤γ(Gμ)≤γ(Πμ) |
⟹⌈μ3⌉−1≤γ(Gμ)≤⌈μ3⌉. | (3.5) |
Assume μ=3k and let γ(Gμ)=⌈μ/3⌉−1. Thus, γ(Gμ)=k−1.
Now, consider e=v1vμ in Figure 6, and by Theorem 2.4 we get
γ(Cμ+1)−1≤γ(Gμ)≤γ(Cμ+1) | (3.6) |
and so
⌈μ+13⌉−1≤γ(Gμ)≤⌈μ+13⌉. | (3.7) |
It follows that
k−1=γ(Gμ)≥⌈μ+13⌉−1>k−1, |
which is a contradiction, and so for μ=3k we have γ(Gμ)=⌈μ/3⌉.
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∈V(H) and v∈V(K). Then γ(G′)=γ(H)+γ(K) or γ(G′)=γ(H)+γ(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∈V(H) and v∈V(K) as shown in Figure 7.
Therefore, the graph G′ has V(G′)=V(H)∪V(K) with V(H)∩V(K)=∅ and E(G′)=E(H)∪E(K)∪{e}. Now, for any dominating set D of the graph G′,
D=D∩V(G′)=D∩(V(H)∪V(K))=(D∩V(H))∪(D∩V(K)), | (3.8) |
and (D∩V(H))∩(D∩V(K))=∅.
Moreover,
|D|=|D∩V(H)|+|D∩V(K)|. | (3.9) |
If D1 is a minimum dominating set of H and D2 is a minimum dominating set of K, then D=D1∪D2 is a dominating set of G′ and so
γ(G′)≤|D|=|D|+|D2|=γ(H)+γ(K). |
Let D be a minimum dominating set of G′ such that γ(G′)=γ(H)+γ(K)−q, where q≥2. Then by Eq (3.9), |D|=|D∩V(H)|+|D∩V(K)|=γ(G′)=γ(H)+γ(K)−q, where q≥2. Therefore, |D∩V(H)|=γ(H)−q1 and |D∩V(K)|=γ(K)−q2 with q1+q2=q.
Suppose if neither q1=0 nor q2=0, then D∩V(H) will not be the dominating set of H. But as D is the dominating set of G′, some of the vertices of D∩V(K) must dominate the vertices of H which are not dominated by the vertices of D∩V(H). But as e=uv is the only edge that connects H with K, we must have that v∈D∩V(K) and u∉D∩V(H). Similarly if we consider the set D∩V(K), then it is not the dominating set of K, and hence by above the argument we have u∈D∩V(H) and v∉D∩V(K). This contradiction shows that both q1 and q2 cannot be non-zero simultaneously. Hence, either q1=0 or q2=0.
Without loss of generality, we take q1=0, and then |D∩V(H)|=γ(H) and |D∩V(K)|=γ(K)−q, where q≥2. This implies that K−v has a dominating set D∩V(K) with cardinality less than or equal to γ(K)−q. Hence, (D∩V(K))∪{v} is a dominating set of K with cardinality less than or equal to γ(K)−(q−1), where q>1. This contradicts the hypothesis of the dominating set. Hence, q≤1, thus, γ(H)+γ(K)−1≤γ(G′)≤γ(H)+γ(K).
Regarding Theorem 3.2, we refer to the work of Rajasekar and Nagarajan [25].
Corollary 3.3. For μ=3k, the domination number of Πμ and L′(Πμ) satisfy the following relation:
γ(Πμ)=γ(L′(Πμ). |
Proof. Comparing Lemma 2.2 and Theorem 3.1 completes the proof of this corollary.
Theorem 3.3. For ν=3, let G3,μ=L′(L′3,μ), where μ≥1. The domination number of G3,μ is
γ(G3,μ)=1+⌈μ−13⌉,for allμ≥1. |
Proof. For the fixed value of ν=3 and μ≥1, the line graph of the lollipop graph L′(L′3,μ) is given in Figure 8.
From Figure 8, it is clear that the line graph G3,μ=L′(L′3,μ) is the combination of two graphs H and K, connected by a bridge e=v1v2. 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
γ(G3,μ)=γ(H)+γ(K). | (3.10) |
Here, the domination number of the connected graph H is 1, i.e., γ(H)=1. The connected graph K is a (μ−1)-th-order path graph Pμ−1 with domination number γ(Pμ−1)=⌈μ−13⌉.
Equation (3.10) implies that
γ(G3,μ)=L′(L′3,μ)=1+⌈μ−13⌉. |
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 G4,2=L′(L′4,2) as shown in Figure 9, the domination number is G4,2=2.
Proof. From Figure 9, the minimal possible dominating set is {u1,v1}, and hence γ(G4,2)=2.
Theorem 3.4. For ν=4, let G4,μ=L′(L′4,μ), where μ≥1. The domination number of G4,μ is
γ(G4,μ)=2+⌈μ−23⌉,for allμ≥1. |
Proof. For the fixed value of ν=4 and μ≥1, the line graph of the lollipop graph L′(L′4,μ) is given in Figure 10.
From Figure 10, it is clear that the line graph G3,μ=L′(L′3,μ) is the combination of two graphs H and K, connected by a bridge e=v2v3. 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
γ(G4,μ)=γ(H)+γ(K). | (3.11) |
In Lemma 3.1, we showed that the domination number of a connected graph H is 2, i.e., γ(H)=2. The connected graph K is a (μ−2)-th-order path graph such that Pμ−2 has the domination number γ(Pμ−2)=⌈μ−23⌉.
Equation (3.11) implies that
γ(G4,μ)=L′(L′4,μ)=2+⌈μ−23⌉. |
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 G5,1=L′(L′5,1) as shown in Figure 11, the domination number is G5,1=2.
Proof. From Figure 11, the minimal possible dominating set is {u1,u10} and hence γ(G5,1)=2.
Theorem 3.5. For ν=5, let G5,μ=L′(L′5,μ), where μ≥1. The domination number of G5,μ is
γ(G5,μ)=2+⌈μ−13⌉,for allμ≥1. |
Proof. For the fixed value of ν=5 and μ≥1, the line graph of the lollipop graph L′(L′5,μ) is given in Figure 12.
From Figure 12 it is clear that the line graph G5,μ=L′(L′5,μ) is the combination of two graphs H and K, connected by a bridge e=v1v2. 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
γ(G3,μ)=γ(H)+γ(K). | (3.12) |
In Lemma 3.2, we showed that the domination number of a connected graph H is 2, i.e., γ(H)=2. The connected graph K is a (μ−1)-th-order path graph such that Pμ−1 has the domination number γ(Pμ−1)=⌈μ−13⌉.
Equation (3.12) implies that
γ(G5,μ)=L′(L′5,μ)=2+⌈μ−13⌉. |
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 μ≥1 and ν≥3.
L′(L′ν,μ) | Line graph | γ(G) | χ(G) |
L′(L′3,1) | ![]() |
1 | 3 |
L′(L′3,2) | ![]() |
2 | 3 |
L′(L′3,3) | ![]() |
2 | 3 |
L′(L′3,4) | ![]() |
2 | 3 |
L′(L′3,5) | ![]() |
3 | 3 |
L′(L′3,6) | ![]() |
3 | 3 |
![]() |
![]() |
![]() |
![]() |
L′(L′3,μ) | ![]() |
1+⌈μ−13⌉ | ν |
L′(L′ν,μ) | Line graph | γ(G) | χ(G) |
L′(L′4,1) | ![]() |
2 | 4 |
L′(L′4,2) | ![]() |
2 | 4 |
L′(L′4,3) | ![]() |
3 | 4 |
L′(L′4,4) | ![]() |
3 | 4 |
L′(L′4,5) | ![]() |
3 | 4 |
L′(L′4,6) | ![]() |
4 | 4 |
![]() |
![]() |
![]() |
![]() |
L′(L′4,μ) | ![]() |
2+⌈μ−23⌉ | ν |
L′(L′ν,μ) | Line graph | γ(G) | χ(G) |
L′(L′5,1) | ![]() |
2 | 5 |
L′(L′5,2) | ![]() |
3 | 5 |
L′(L′5,3) | ![]() |
3 | 5 |
L′(L′5,4) | ![]() |
3 | 5 |
L′(L′5,5) | ![]() |
4 | 5 |
L′(L′5,6) | ![]() |
4 | 5 |
![]() |
![]() |
![]() |
![]() |
L′(L′5,μ) | ![]() |
2+⌈μ−13⌉ | ν |
Next, we generalize these results from to L′(L′ν,μ) by getting idea from above theorems and those of Tables 1–3. We present the general form for the domination number of L′(L′ν,μ) in the following conjecture.
Conjecture 3.2. For any ν≥3, let Gν,μ=L′(L′ν,μ), where μ≥1. The domination number of Gν,μ is
γ(Gν,μ)={k+⌈μ−13⌉,ν=odd(ν=2k+1 for all k≥1),k+⌈μ−23⌉,ν=even(ν=2k for all k≥2). |
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, χ(G∪G′)=max.
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
\begin{equation*} \chi(C_{\mu}) = \begin{cases} 3, & \text{if}\; n\; is\; odd,\\ 2, & otherwise. \end{cases} \end{equation*} |
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
\begin{equation*} \chi(G_{\nu,\mu}) = \nu,\; \mathit{\text{where}}\; 3 \leq \nu \leq 5. \end{equation*} |
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
V(G_{3,\mu}) = \{v_1,v_2,v_3\}\cup \{1,2, \ldots ,\mu-1,\mu\}, |
D(G_{3,\mu}) = \{r,b,g\}\cup\{r,b,...,r,b\}, |
\min(D(G_{3,\mu})) = \{r,b,g\} = 3 |
\Rightarrow \chi(G_{3,\mu}) = 3. |
See Figure 13 for the line graph L'(\mathcal{L'}_{3, \mu}) .
Case 2. \nu = 4\; \text{and}\; \mu \geq 1
V(G_{4,\mu}) = \{v_1,v_2,v_3,v_4,v_5,v_6\}\cup\{1,2,3,\ldots,\mu-1,\mu\}, |
D(G_{4,\mu}) = \{b,r,g,s,b,g\}\cup\{r,b,\ldots,r,b\}, |
\min(D(G_{4,\mu})) = \{b,r,g,s\} = 4 |
\Rightarrow \chi(G_{4,\mu}) = 4. |
See Figure 14 for the line graph L'(\mathcal{L'}_{4, \mu}) .
Case 3. \nu = 5\; \text{and}\; \mu \geq 1
V(G_{5,\mu}) = \{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10}\}\cup\{,1,2,\ldots,\mu-1,\mu\}, |
D(G_{5,\mu}) = \{b,r,g,s,y,b,r,g,s,y\}\cup\{r,b,\ldots,r,b\}, |
\min(D(G_{5,\mu})) = \{b,r,g,s,y\} = 5 |
\Rightarrow \chi(G_{5,\mu}) = 5. |
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
\begin{equation*} \chi(G_{\nu,\mu}) = \nu,\; \mathit{\text{where}}\; \nu \geq 3. \end{equation*} |
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:
\begin{equation} \chi(G) = \chi(H'). \end{equation} | (4.1) |
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
\begin{equation} \chi(\Pi_\mu) = \begin{cases} 3, & \text{if }\mu\; \text{is odd},\\ 2, & \text{if} \;\mu\; \text{is even}. \end{cases} \end{equation} | (4.2) |
In Theorem 4.1, we showed that
\begin{equation} \chi(L'(\Pi_\mu)) = 3, \; for \; all \; n\geq 3. \end{equation} | (4.3) |
Comparing Eqs (4.2) and (4.3) completes the proof of this corollary.
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 :
H_c(G): = y = v_1v_2v_3\circ \{v_{j+1}:3\leq j \leq \mu\}\circ v_1 = 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 ,
P_h(x_q,y_q):x_q = u_1\sim u_2\sim u_3\circ \{v_r: 1\leq r\leq \mu \} = y_q. |
Case 2. For \nu = 4 and \mu \geq 1 ,
P_h(x_q,y_q):x_q = u_1\sim u_2\sim u_3\sim u_4\sim u_5 \sim u_6 \circ \{v_r: 1\leq r\leq \mu \} = y_q. |
Case 3. For \nu\geq 5 and \mu \geq 1 ,
P_h(x_q,y_q):x_q = u_1\circ \{u_r: 2\leq r\leq \nu \} \circ \left\{u_t: \nu+1 \leq t \leq \frac{\nu(\nu-1)}{2}-\nu\right\} \circ |
\{v_j: 1 \leq j \leq \mu \} = y_q. |
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.
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.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
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.
The authors declare that they have no known competing financial interests.
[1] | S. Alikhani, Y. H. Peng, K. A. M. Atan, On the domination number of some graphs, Int. Math. Forum, 3 (2008), 1879–1884. |
[2] | C. Berge, The theory of graphs and its applications, London: Methuen, 1962. |
[3] |
C. Bujtás, Domination number of graphs with minimum degree five, Discuss. Math. Graph Theory, 41 (2021), 763–777. https://doi.org/10.7151/dmgt.2339 doi: 10.7151/dmgt.2339
![]() |
[4] |
R. A. Brualdi, R. F. Shanny, Hamiltonian line graphs, J. Graph Theory, 5 (1981), 307–314. https://doi.org/10.1002/jgt.3190050312 doi: 10.1002/jgt.3190050312
![]() |
[5] | G. Chartrand, Introduction to graph theory, New Delhi: Tata McGraw-Hill Education, 2006. |
[6] |
L. Clark, On Hamiltonian line graphs, J. Graph Theory, 8 (1984), 303–307. https://doi.org/10.1002/jgt.3190080210 doi: 10.1002/jgt.3190080210
![]() |
[7] |
D. H. Cai, P. Z. Fan, Q. Y. Zou, Y. Q. Xu, Z. G. Ding, Z. Q. Liu, Active device detection and performance analysis of massive non-orthogonal transmissions in cellular Internet of Things, Sci. China Inform. Sci., 65 (2022), 182301. https://doi.org/10.1007/s11432-021-3328-y doi: 10.1007/s11432-021-3328-y
![]() |
[8] | G. Chartrand, P. Zhang, A first course in graph theory, Courier Corporation, 2013. |
[9] |
D. Duffus, B. Sands, R. E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory, 9 (1985), 487–495. https://doi.org/10.1002/jgt.3190090409 doi: 10.1002/jgt.3190090409
![]() |
[10] |
W. Goddard, M. A. Henning, Domination in planar graphs with small diameter, J. Graph Theory, 40 (2002), 1–25. https://doi.org/10.1002/jgt.10027 doi: 10.1002/jgt.10027
![]() |
[11] |
Y. H. Guo, R. Zhao, S. W. Lai, L. S. Fan, X. F. Lei, G. K. Karagiannidis, Distributed machine learning for multiuser mobile edge computing systems, IEEE J. Sel. Top. Signal Process., 16 (2022), 460–473. https://doi.org/10.1109/jstsp.2022.3140660 doi: 10.1109/jstsp.2022.3140660
![]() |
[12] | T. W. Haynes, M. A. Henning, The domatic numbers of factors of graphs, Ars Combin., 56 (2000), 161–173. |
[13] | T. W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of domination in graphs, New York: Marcel Dekker, 1998. |
[14] |
S. Hayat, A. Khan, S. Khan, J. B. Liu, Hamilton connectivity of convex polytopes with applications to their detour index, Complexity, 2021 (2021), 6684784. https://doi.org/10.1155/2021/6684784 doi: 10.1155/2021/6684784
![]() |
[15] |
F. Harary, C. S. J. A. Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull., 8 (1965), 701–709. https://doi.org/10.4153/cmb-1965-051-3 doi: 10.4153/cmb-1965-051-3
![]() |
[16] | M. J. Jou, J. J. Lin, Domination numbers of trees, In: Proceedings of the 2017 International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017), 319–321. https://doi.org/10.2991/ammsa-17.2017.71 |
[17] |
C. X. Kang, On domination number and distance in graphs, Discrete Appl. Math., 200 (2016), 203–206. https://doi.org/10.1016/j.dam.2015.07.009 doi: 10.1016/j.dam.2015.07.009
![]() |
[18] |
S. Khan, S. Hayat, A. Khan, M. Y. H. Malik, J. D. Cao, Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications, AIMS Math., 6 (2021), 3947–3973. https://doi.org/10.3934/math.2021235 doi: 10.3934/math.2021235
![]() |
[19] |
J. B. Liu, Y. Bao, W. T. Zheng, Analyses of some structural properties on a class of hierarchical scale-free networks, Fractals, 30 (2022), 2250136. https://doi.org/10.1142/S0218348X22501365 doi: 10.1142/S0218348X22501365
![]() |
[20] |
J. B. Liu, Y. Bao, W. T. Zheng, S. Hayat, Network coherence analysis on a family of nested weighted n-polygon networks, Fractals, 29 (2021), 2150260. https://doi.org/10.1142/S0218348X21502601 doi: 10.1142/S0218348X21502601
![]() |
[21] |
J. B. Liu, C. X. Wang, S. H. Wang, B. Wei, Zagreb indices and multiplicative Zagreb indices of Eulerian graphs, Bull. Malays. Math. Sci. Soc., 42 (2019), 67–78. https://doi.org/10.1007/s40840-017-0463-2 doi: 10.1007/s40840-017-0463-2
![]() |
[22] |
G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory, 22 (1996), 213–229. https://doi.org/10.1002/(SICI)1097-0118(199607)22:3<213::AID-JGT2>3.0.CO;2-P doi: 10.1002/(SICI)1097-0118(199607)22:3<213::AID-JGT2>3.0.CO;2-P
![]() |
[23] | O. Ore, Theory of graphs, American Mathematical Society, 1962. |
[24] |
H. Pahlings, On the chromatic number of skew graphs, J. Combin. Theory Ser. B, 25 (1978), 303–306. https://doi.org/10.1016/0095-8956(78)90006-0 doi: 10.1016/0095-8956(78)90006-0
![]() |
[25] | G. Rajasekar, K. Nagarajan, Algorithm for finding location domination number of a graph connected by a bridge, Int. J. Pure Appl. Math., 118 (2018), 313–321. |
[26] |
I. A. Stewart, Sufficient conditions for Hamiltonicity in multiswapped networks, J. Parallel Distrib. Comput., 101 (2017), 17–26. https://doi.org/10.1016/j.jpdc.2016.10.015 doi: 10.1016/j.jpdc.2016.10.015
![]() |
[27] | N. Siddiqui, M. James, Domination and chromatic number of pan graph and lollipop graph, Int. J. Tech. Innov. Mod. Eng. Sci., 4 (2021), 932–939. |
[28] |
C. Y. Tan, D. H. Cai, F. Fang, Z. G. Ding, P. Z. Fan, Federated unfolding learning for CSI feedback in distributed edge networks, IEEE Trans. Commun., 73 (2025), 410–424. https://doi.org/10.1109/tcomm.2024.3429170 doi: 10.1109/tcomm.2024.3429170
![]() |
[29] |
B. Wei, Hamiltonian paths and Hamiltonian connectivity in graphs, Discrete Math., 121 (1993), 223–228. https://doi.org/10.1016/0012-365x(93)90555-8 doi: 10.1016/0012-365x(93)90555-8
![]() |
[30] | D. B. West, Introduction to graph theory, Upper Saddle River: Prentice Hall, 2001. |
[31] | H. B. Walikar, B. D. Acharya, Domination critical graphs, Nat. Acad. Sci. Lett., 2 (1979), 70–72. |
[32] |
Y. B. Zhong, S. Hayat, A. Khan, Hamilton-connectivity of line graphs with application to their detour index, J. Appl. Math. Comput., 68 (2022), 1193–1226. https://doi.org/10.1007/s12190-021-01565-2 doi: 10.1007/s12190-021-01565-2
![]() |
[33] |
S. H. Zheng, C. Shen, X. Chen, Design and analysis of uplink and downlink communications for federated learning, IEEE J. Sel. Areas Commun., 39 (2021), 2150–2167. https://doi.org/10.1109/jsac.2020.3041388 doi: 10.1109/jsac.2020.3041388
![]() |
L'(\mathcal{L'}_{\nu, \mu}) | Line graph | \gamma (G) | \chi(G) |
L'(\mathcal{L'}_{3, 1}) | ![]() |
1 | 3 |
L'(\mathcal{L'}_{3, 2}) | ![]() |
2 | 3 |
L'(\mathcal{L'}_{3, 3}) | ![]() |
2 | 3 |
L'(\mathcal{L'}_{3, 4}) | ![]() |
2 | 3 |
L'(\mathcal{L'}_{3, 5}) | ![]() |
3 | 3 |
L'(\mathcal{L'}_{3, 6}) | ![]() |
3 | 3 |
![]() |
![]() |
![]() |
![]() |
L'(\mathcal{L'}_{3, \mu}) | ![]() |
1+\lceil \frac{\mu-1}{3} \rceil | \nu |
L'(\mathcal{L'}_{\nu,\mu}) | Line graph | \gamma (G) | \chi(G ) |
L'(\mathcal{L'}_{4,1}) | ![]() |
2 | 4 |
L'(\mathcal{L'}_{4,2}) | ![]() |
2 | 4 |
L'(\mathcal{L'}_{4,3}) | ![]() |
3 | 4 |
L'(\mathcal{L'}_{4,4}) | ![]() |
3 | 4 |
L'(\mathcal{L'}_{4,5}) | ![]() |
3 | 4 |
L'(\mathcal{L'}_{4,6}) | ![]() |
4 | 4 |
![]() |
![]() |
![]() |
![]() |
L'(\mathcal{L'}_{4,\mu}) | ![]() |
2+\lceil \frac{\mu-2}{3} \rceil | \nu |
L'(\mathcal{L'}_{\nu,\mu}) | Line graph | \gamma (G) | \chi(G ) |
L'(\mathcal{L'}_{5,1}) | ![]() |
2 | 5 |
L'(\mathcal{L'}_{5,2}) | ![]() |
3 | 5 |
L'(\mathcal{L'}_{5,3}) | ![]() |
3 | 5 |
L'(\mathcal{L'}_{5,4}) | ![]() |
3 | 5 |
L'(\mathcal{L'}_{5,5}) | ![]() |
4 | 5 |
L'(\mathcal{L'}_{5,6}) | ![]() |
4 | 5 |
![]() |
![]() |
![]() |
![]() |
L'(\mathcal{L'}_{5,\mu}) | ![]() |
2+\lceil \frac{\mu-1}{3} \rceil | \nu |
L'(\mathcal{L'}_{\nu, \mu}) | Line graph | \gamma (G) | \chi(G) |
L'(\mathcal{L'}_{3, 1}) | ![]() |
1 | 3 |
L'(\mathcal{L'}_{3, 2}) | ![]() |
2 | 3 |
L'(\mathcal{L'}_{3, 3}) | ![]() |
2 | 3 |
L'(\mathcal{L'}_{3, 4}) | ![]() |
2 | 3 |
L'(\mathcal{L'}_{3, 5}) | ![]() |
3 | 3 |
L'(\mathcal{L'}_{3, 6}) | ![]() |
3 | 3 |
![]() |
![]() |
![]() |
![]() |
L'(\mathcal{L'}_{3, \mu}) | ![]() |
1+\lceil \frac{\mu-1}{3} \rceil | \nu |
L'(\mathcal{L'}_{\nu,\mu}) | Line graph | \gamma (G) | \chi(G ) |
L'(\mathcal{L'}_{4,1}) | ![]() |
2 | 4 |
L'(\mathcal{L'}_{4,2}) | ![]() |
2 | 4 |
L'(\mathcal{L'}_{4,3}) | ![]() |
3 | 4 |
L'(\mathcal{L'}_{4,4}) | ![]() |
3 | 4 |
L'(\mathcal{L'}_{4,5}) | ![]() |
3 | 4 |
L'(\mathcal{L'}_{4,6}) | ![]() |
4 | 4 |
![]() |
![]() |
![]() |
![]() |
L'(\mathcal{L'}_{4,\mu}) | ![]() |
2+\lceil \frac{\mu-2}{3} \rceil | \nu |
L'(\mathcal{L'}_{\nu,\mu}) | Line graph | \gamma (G) | \chi(G ) |
L'(\mathcal{L'}_{5,1}) | ![]() |
2 | 5 |
L'(\mathcal{L'}_{5,2}) | ![]() |
3 | 5 |
L'(\mathcal{L'}_{5,3}) | ![]() |
3 | 5 |
L'(\mathcal{L'}_{5,4}) | ![]() |
3 | 5 |
L'(\mathcal{L'}_{5,5}) | ![]() |
4 | 5 |
L'(\mathcal{L'}_{5,6}) | ![]() |
4 | 5 |
![]() |
![]() |
![]() |
![]() |
L'(\mathcal{L'}_{5,\mu}) | ![]() |
2+\lceil \frac{\mu-1}{3} \rceil | \nu |