
We revisit results obtained in [
Citation: Milica Anđelić, Tamara Koledin, Zoran Stanić. Notes on Hamiltonian threshold and chain graphs[J]. AIMS Mathematics, 2021, 6(5): 5078-5087. doi: 10.3934/math.2021300
[1] | Wenke Zhou, Guo Chen, Hongzhi Deng, Jianhua Tu . Enumeration of dissociation sets in grid graphs. AIMS Mathematics, 2024, 9(6): 14899-14912. doi: 10.3934/math.2024721 |
[2] | Xia Liu . A related problem on $ s $-Hamiltonian line graphs. AIMS Mathematics, 2022, 7(10): 19553-19561. doi: 10.3934/math.20221073 |
[3] | Bader Alshamary, Milica Anđelić, Edin Dolićanin, Zoran Stanić . Controllable multi-agent systems modeled by graphs with exactly one repeated degree. AIMS Mathematics, 2024, 9(9): 25689-25704. doi: 10.3934/math.20241255 |
[4] | Yinzhen Mei, Chengxiao Guo, Mengtian Liu . The bounds of the energy and Laplacian energy of chain graphs. AIMS Mathematics, 2021, 6(5): 4847-4859. doi: 10.3934/math.2021284 |
[5] | Huani Li, Ruiqin Fu, Xuanlong Ma . Forbidden subgraphs in reduced power graphs of finite groups. AIMS Mathematics, 2021, 6(5): 5410-5420. doi: 10.3934/math.2021319 |
[6] | Natarajan Chidambaram, Swathi Mohandoss, Xinjie Yu, Xiujun Zhang . On leap Zagreb indices of bridge and chain graphs. AIMS Mathematics, 2020, 5(6): 6521-6536. doi: 10.3934/math.2020420 |
[7] | Luigi Accardi, Amenallah Andolsi, Farrukh Mukhamedov, Mohamed Rhaima, Abdessatar Souissi . Clustering quantum Markov chains on trees associated with open quantum random walks. AIMS Mathematics, 2023, 8(10): 23003-23015. doi: 10.3934/math.20231170 |
[8] | Bilal A. Rather, M. Aijaz, Fawad Ali, Nabil Mlaiki, Asad Ullah . On distance signless Laplacian eigenvalues of zero divisor graph of commutative rings. AIMS Mathematics, 2022, 7(7): 12635-12649. doi: 10.3934/math.2022699 |
[9] | Jean-Guy Caputo, Imene Khames, Arnaud Knippel . Nonlinear normal modes in a network with cubic couplings. AIMS Mathematics, 2022, 7(12): 20565-20578. doi: 10.3934/math.20221127 |
[10] | B.L. Mayer, L.H.A. Monteiro . On the divisors of natural and happy numbers: a study based on entropy and graphs. AIMS Mathematics, 2023, 8(6): 13411-13424. doi: 10.3934/math.2023679 |
We revisit results obtained in [
A threshold graph can be defined in many ways, as can be seen in [2]. Here we follow the definition via binary generating sequences. Accordingly, a threshold graph G(b) is obtained from its binary generating sequence of the form b=(b1b2⋯bn) in the following way:
(i) for i=1, G1=G(b1)=K1, i.e., a single vertex;
(ii) for i≥2, with Gi−1=G(b1b2⋯bi−1) already constructed, Gi=G(b1b2⋯bi−1bi) is formed by adding an isolated vertex to Gi−1 if bi=0 (that is, a vertex non-adjacent to any vertex in Gi−1) or by adding a dominating vertex to Gi−1 if bi=1 (that is, a vertex adjacent to all the vertices in Gi−1).
Clearly, G(b)=Gn. A schematic representation of a threshold graph is illustrated in Figure 1(a); its vertices are partitioned into cells Ui,Vi(1≤i≤h).
The vertices in U=⋃hi=1Ui induce a co-clique, while the vertices in V=⋃hi=1Vi induce a clique. An equivalent definition of a threshold graph says that a graph is a threshold graph if it does not contain neither 2K2 (the disjoint union of two edges), P4 (the 4-vertex path) or C4 (the 4-vertex cycle) as an induced subetaaph [6].
A bipartite counterpart to the threshold graph is a chain graph which is generated by the same binary sequence in the following way:
(i) for i=1, G1=G(b1)=K1, i.e., a single vertex belonging to one colour class, say white vertex;
(ii) for i≥2, with Gi−1=G(b1b2⋯bi−1), Gi=G(b1b2⋯bi−1bi) is obtained by adding to Gi−1 an isolated white vertex if bi=0 or a black vertex which dominates all previously added white vertices if bi=1.
A schematic representation is illustrated in Figure 1(b).
Here are some conventions on binary generating sequences. First, observing that due to the defining rule (i), (either a threshold or a chain) graph is independent of b1, we use the convention that the binary sequences always start with zero. Moreover, if bn=1, then the corresponding graph is connected; otherwise, it is connected up to isolated vertices. Accordingly, since we restricted ourselves to connected graphs, a binary sequence can be written as
b=(0t11s1)(0t21s2)⋯(0th1sh),whereti,si>0,for1≤i≤h. | (1.1) |
(Naturally, ti's and si's are lengths of maximum runs of consecutive zeros and ones, respectively.)
In a so-called split graph the vertex set can be divided into two disjunct sets, say U and V, in such a way that U induces a co-clique and V induces a clique. Evidently, every threshold graph is a split graph and the neighbourhoods of the vertices are totally ordered by inclusion. By deleting all the edges that belong to the clique V=⋃hi=1Vi (see Figure 1) of a threshold graph, we obtain the chain graph that is generated by the same binary sequence. {Note that for any x∈U1, the subetaaph induced by V∪{x} induces a maximal clique in the corresponding threshold graph.
We say that a graph is Hamiltonian if it contains a cycle passing through all of its vertices. Every such a cycle is called a Hamilton cycle.
In this paper we revisit the results obtained in [1] on Hamiltonicity of threshold graphs. We give necessary and sufficient conditions for a threshold graph to be Hamiltonian in terms of its generating binary sequence.
The paper is organized as follows. In Section 2 we recall the results of Harary and Peled [1]. In Section 3 we interpret these results in terms of the entries of the generating binary sequence of a threshold graph and give a criterion for Hamiltonicity of a threshold graph that can be deduced directly from its binary sequence. This criterion is implemented in the algorithm presented in Section 4, where we also include an algorithm that determines whether a given chain graph is Hamiltonian. In Section 5 we identify the chain graph of a given order that contains minimum number of Hamilton cycles. Some concluding notes and directions for future research are given in Section 6.
Let G be a threshold graph with vertex set I∪J, where I (with |I|=r) induces a co-clique and J (with |J|=s) induces a maximal clique. Let further B denote the chain graph obtained from G by deleting all edges in the subetaaph induced by J. For B, let d1≤d2≤⋯≤dr and e1≤e2≤⋯≤es denote the degrees of the vertices x1,x2,…,xr∈I and y1,y2,…,ys∈J, respectively.
In order to determine whether a given threshold graph is Hamiltonian, the authors of [1] first showed that this problem can be reduced to the question of Hamiltonicity of the corresponding chain graph B with the colour classes of the same size, as shown in the sequel.
The first lemma gives sufficient conditions for a split graph to be non-Hamiltonian.
Lemma 2.1. ([1]) Let G be a split graph with vertex set I∪J, where I induces a co-clique of size r and J induces a maximal clique of size s. If either r>s or r<s with es−r=0, then G is not Hamiltonian.
In what follows we only consider threshold graphs with r≥2, since for r=0, G is Hamiltonian if and only if s≥3, while for r=1, G is Hamiltonian if and only if d1≥2.
Since any threshold graph is a split graph, by the previous lemma, Hamiltonian threshold graphs satisfy 2≤r≤s and es−r>0. The next lemma shows that the problem under the consideration can be reduced to the Hamiltonicity of threshold graphs with |U|=|V|.
Lemma 2.2. ([1]) If 2≤r<s and es−r>0, then the threshold graph G is Hamiltonian if and only if the threshold subetaaph G∗ obtained by deleting the vertices y1,y2,…,ys−r is Hamiltonian.
Remark 2.1. In [1] the conclusion that after dropping y1,y2,…,ys−r from J the resulting threshold graph will have a maximal clique and co-clique of the same size is wrong. The correct conclusion is that in this case we have s=r+2 and in the resulting graph a clique induced by {ys−r+1,…,ys} is not a maximal one. A maximal one can be obtained by adding a vertex from a co-clique of the smallest degree. For example, in the threshold graph generated by (02120213), the size of a maximal clique is 6 and the size of a co-clique is 3. After dropping y1,y2,y3 we obtain the threshold graph generated by (0313). However, in this graph r≠s, since r=2 and s=4.
In what follows we assume that in a threshold graph G, |U|=|V|. Then the edges in the clique cannot be used in any Hamiltonian cycle, and therefore can be dropped from G, yielding the chain graph B with |U|=|V|≥2.
For q∈{0,1,…,|U|−1}, we denote by Sq the set of inequalities
dj≥j+1,for1≤j≤q;ej≥j+1,for1≤j≤|U|−1−q. |
The next theorem gives two equivalent conditions for a chain graph B with |U|=|V|≥2 to be Hamiltonian.
Theorem 2.3. ([1]) If |U|=|V|≥2, then the following conditions are equivalent:
(a) B is Hamiltonian;
(b) Sq holds for some q∈{0,1,…,|U|−1};
(c) Sq holds for each q∈{0,1,…,|U|−1}.
To conclude, in order to determine whether an arbitrary threshold graph is Hamiltonian, all three results reported in Lemma 2.1, Lemma 2.2 and Theorem 2.3 should be employed.
In this section we restate the results from Section 2 in terms of the entries of the generating binary sequence of a given threshold graph. Afterwards, we amalgamate them to obtain a result that gives necessary and sufficient conditions for a threshold graph to be Hamiltonian.
Let G and B be a threshold graph and a chain graph generated by a binary sequence (1.1). If t1≠1, then the degrees of vertices in B corresponding to {a co-clique I and a maximal clique J=V∪{x} for some x∈U1 are:
dth1,dth−12,…,dt1−1h,withdj=h∑i=h+1−jsi01,es11,es22,…,eshh,withej=j∑i=1ti−1. | (3.1) |
Note that the vertex degrees are given in non-decreasing order, and according to Figure 1, they are the degrees of vertices in Uh,Uh−1,…,U1∖{x} and {x},V1,V2,…,Vh, respectively.
Otherwise, if t1=1, then G is a split graph in which the subetaaph induced by V∪U1 gives a maximal clique. Then the degrees of vertices in B corresponding to the colour classes ⋃hi=2Ui and V∪U1 are:
dth1,dth−12,…,dt2h−1,withdj=h∑i=h+1−jsi,01+s1,es22,…,eshh,withej=j∑i=2ti. | (3.2) |
Let T=∑hi=1ti and S=∑hi=1si. From the previous observations, it follows that the size of the maximal clique s and the size of the corresponding co-clique r satisfy r=T−1 and s=S+1.
We first state the following lemma that determines when es−r=0 may occur.
Lemma 3.1. Let G be a threshold graph generated by (1.1), such that s>r. Then es−r=0 holds if and only if t1≠1 and s−r=1 or t1=1 and s−r∈{1,2,…,s1+1}.
Proof. From (3.1), it follows that for t1≠1, ei=0 if and only if i=1. Otherwise, from (3.2) ei=0 if and only if i∈{1,2,…,s1+1}. This completed the proof.
Next, Lemma 2.1 applied to threshold graphs states the following.
Lemma 3.2. Let G be a threshold graph generated by (1.1). If r>s or t1≠1 and s−r=1 or t1=1 and s−r∈{1,2,…,s1+1}, then G is not Hamiltonian.
In the sequel we consider only threshold graphs with s≥r+2 if t1≠1 and with s≥r+s1+2 if t1=1. Let the integer ℓ be defined in the following way: if s−r−1<s1, then ℓ=0; otherwise, ℓ is the least integer such that ∑ℓi=1si≤s−r−1<∑ℓ+1i=1si (obviously, such an integer exists). The dropping of the vertices y1,y2,…,ys−r from J is equivalent to dropping y1 from U1 and y2,…,ys−r from V. Consequently, the new graph G∗ is generated by the binary sequence
(0∑ℓ+1i=1ti−11∑ℓ+1i=1si−(s−r−1)0tℓ+21sℓ+2⋯0th1sh). | (3.3) |
Next we state a reformulation of Lemma 2.2.
Lemma 3.3. Let G be a threshold graph generated by (1.1) with s≥r≥2. Then G is Hamiltonian if and only if a threshold graph G∗ generated by (3.3) is Hamiltonian.
For s∗ℓ+1=∑ℓ+1i=1si−(s−r−1), the degrees of vertices in U∗ and V∗ in the corresponding bipartite graph B∗ of G∗ given in non-decreasing order are
d∗1=⋯=d∗th=sh,d∗th+1=⋯=d∗th+th−1=sh−1+sh,a⋮d∗tℓ+3+⋯+th+1=⋯=d∗tℓ+2+⋯+th=h∑i=ℓ+2si,d∗tℓ+2+⋯+th+1=⋯=d∗t1+t2+⋯+th−1=h∑i=1ti−1ande∗1=⋯=e∗s∗ℓ+1=ℓ+1∑i=1ti−1,e∗s∗ℓ+1+1=⋯=e∗s∗ℓ+1+sℓ+2=ℓ+2∑i=1ti−1,a⋮e∗s∗ℓ+1+sℓ+2+⋯+sh−1+1=⋯=e∗s∗ℓ+1+sℓ+2+⋯+sh=h∑i=1ti−1. |
Next, we consider the system of inequalities Sq, q∈{0,1,…,T−1}, for ∑hi=1si=∑hi=1ti.
Lemma 3.4. Let G be a threshold graph generated by (1.1), with ∑hi=1si=∑hi=1ti≥2. Then G is Hamiltonian if and only if
h∑i=jsi≥h∑i=jti+1,for2≤j≤h. | (3.4) |
Proof. Recall from Section 2 that a threshold graph G, with S=T, is Hamiltonian if and only if the corresponding chain graph B is Hamiltonian. Next, by Theorem 2.3, the chain graph B is Hamiltonian if and only Sq holds for q=T−1. On the other hand, for (3.4) and each repeated vertex degree, we have
{h∑i=jsi≥∑hi=j+1ti+2,a,,,⋮h∑i=jsi≥h∑i=j+1ti+tj+1=∑hi=jti+1. |
Now, it is easy to see that ST−1 holds if and only if (3.4) holds. Note that the inequality ∑hi=1si≥∑hi=1ti−1+1 is not included, since (by the assumption that S=T) it holds as equality.
Remark 3.1. The left hand sides of (3.4) are equal to the vertex degrees, while the right hand sides register the position of the last occurrence of the corresponding vertex degree augmented by 1.
Gathering all the previous results, we arrive at our main result – the criterion for the Hamiltonicity of a threshold graph based on its generating binary sequence.
Theorem 3.5. Let G be a threshold graph generated by (1.1) such that r≥2. If either s≤r+1 for t1≠1 or s≤r+s1+1 for t1=1, then G is not Hamiltonian. Otherwise, G is Hamiltonian if and only if ℓ+1=h or
h∑i=jsi≥h∑i=jti,forℓ+2≤j≤h, | (3.5) |
where for s−r−1<s1, ℓ=0, and otherwise ℓ is the least integer such that ∑ℓi=1si≤s−r−1<∑ℓ+1i=1si.
Proof. A threshold graph G generated by (1.1) is Hamiltonian if and only G∗ generated by (3.3) is Hamiltonian. Now, G∗ is Hamiltonian if and only if the corresponding chain graph B∗ generated by (3.3) is Hamiltonian. The last one holds if and only if ℓ+1=h or otherwise if and only if the system of inequalities (3.4) holds for B∗, i.e., if and only if
h∑i=jsi≥h∑i=jti,forℓ+2≤j≤h, |
which completes the proof.
As a corollary we state a necessary and sufficient condition for a chain graph to be Hamiltonian. Note that Hamiltonian chain graph has the colour classes of the same size (see [3]) and cannot have any pendant edges. Moreover, in any Hamiltonian chain graph generated by (1.1), the inequalities t1≥s1+1 and sh≥th+1 must hold.
Corollary 3.6. Let G be a chain graph generated by (1.1), such that T≥2. If either S≠T or S=T and t1<s1+1 or sh<th+1, then G is not Hamiltonian. Otherwise, G is Hamiltonian if and only if
h∑i=jsi≥h∑i=jti+1,for2≤j≤h. |
In this section we present algorithms for recognition of Hamiltonian threshold graph and Hamiltonian chain graph. The input is a binary generating sequence, and in return we obtain the decision whether the corresponding threshold (resp. chain) graph is Hamiltonian or not.
Algorithm 1 (checks if a given threshold graph is Hamiltonian).
(0) INPUT: Generating binary sequence (0t11s1)(0t21s2)⋯(0th1sh).
1.Calculate r and s. r=∑hi=1ti−1; s=∑hi=1si+1.
2.If r=1∧d1=sh≥2 then RETURN TRUE. If r=1∧d1=sh=1 then RETURN FALSE.
3.If (t1≠1∧s≤r+1)∨(t1=1∧s≤r+s1+1) then RETURN FALSE.
4.Determine the least integer ℓ such that ∑ℓi=1si≤s−r−1<∑ℓ+1i=1si. If s−r−1<s1, take ℓ=0.
5.If ℓ+1=h or all inequalities in (3.5) hold then RETURN TRUE. Otherwise, RETURN FALSE.
Algorithm 2 (checks if a given chain graph is Hamiltonian).
(0) INPUT: Generating binary sequence (0t11s1)(0t21s2)⋯(0th1sh).
1.Calculate T and S. T=∑hi=1ti and S=∑hi=1si.
2.If T≠S∨(T=S∧(t1<s1+1∨sh<th+1)) then RETURN FALSE.
3.If the inequalities ∑hi=jsi≥∑hi=jti+1 hold for 2≤j≤h then RETURN TRUE. Otherwise, RETURN FALSE.
It is not difficult to deduce that both algorithms are linear. Indeed, for step (5) of the former one and step (3) of the latter one we first compute and compare the sums for j=h, then for j=h−1, and so on. In this way, every sum is computed on the basis of the previous one and we have at most n iterations such that each one is performed with O(1) operations, which gives O(n) for these steps. The complexity of the remaining steps is obvious.
We give some examples illustrating the applications of the algorithms.
Example 4.1. Let G be a complete split graph, i.e, a threshold graph generated by (0t11s1). If t1=1, s1>1 then G is Hamiltonian. Otherwise, for t1≥2, if s1≤t1−1 then G is not Hamiltonian. If s1≥t1 then G is Hamiltonian, since in this case we have ℓ=0 and ℓ+1=h=1.
Therefore, we conclude that a complete split graph is Hamiltonian if and only if the size of the clique is greater than or equal to the size of the co-clique, except for the case where both are equal to 1.
Example 4.2. Let G be a threshold graph generated by (0t11s10t21s2). If r=1 (i.e., t1=t2=1), then G is Hamiltonian if and only if s2≥2. For r≥2, if either t1+t2+2>s1+s2, t1≠1 or s2<1+t2, t1=1 then G is not Hamiltonian. Otherwise, if s−r−1<s1, then G is Hamiltonian if and only if s2≥t2, while if s−r−1≥s1 then G is necessarily Hamiltonian.
Example 4.3. Let G be a particular threshold graph generated by (031401016051110318). In this case we have r=20 and s=30. Implementing the step (4) of Algorithm 1, we get 4<30−20−1<10, which implies that ℓ=1. We next verify that the following inequalities hold: s3+s4≥t3+t4 and s4≥t4, and since they do, we conclude that G is Hamiltonian.
Example 4.4. Let G be a particular chain graph generated by (03140101605130318). In this case we have r=s=21. By the step (3) of the algorithm 2, we get s2+s3+s4≱t2+t3+t4+1, which implies that G is not Hamiltonian.
In this section we give some observations on Hamiltonian chain graphs and we also determine chain graphs with minimum number of Hamilton cycles. The problem on the value of the minimum number of Hamilton cycles in a given graph has been considered for some special graph classes. For existing literature and recent results related to threshold graphs, we refer the reader to [4].
An edge of a chain graph G generated by (1.1) is called a key edge of G if it joins a vertex in Ui to a vertex in Vi for some 1≤i≤h (see 1 (b)). As it will be shown in the sequel, key edges play a significant role in determining Hamiltonian chain graphs. We proceed by the following lemmas.
Lemma 5.1. Let e be a key edge of a chain graph G generated by (1.1), then G−e is a chain graph.
Proof. Let e=uv, where u∈Ui and v∈Vi. We consider the following cases.
Case 1. If ti>1, si>1 then G−e is a chain graph generated by
(0t11s1)⋯(0ti−11si−1)(0ti−111)(011si−1)(0ti+11si+1)⋯(0th1sh). |
Case 2. If ti>1, si=1, i.e., if G is generated by
(0t11s1)⋯(0ti−11si−1)(0ti11)(0ti+11si+1)⋯(0th1sh), |
then G−e is a chain graph generated by
(0t11s1)⋯(0ti−11si−1)(0ti−111)(0ti+1+11si+1)⋯(0th1sh). |
Case 3. If ti=1, si>1, i.e, if G is generated by
(0t11s1)⋯(0ti−11si−1)(011si)(0ti+11si+1)⋯(0th1sh), |
then G−e is a chain graph generated by
(0t11s1)⋯(0ti−11si−1+1)(011si−1)(0ti+1+11si+1)⋯(0th1sh). |
Case 4. If ti=si=1, i.e., if G is generated by
(0t11s1)⋯(0ti−11si−1)(0111)(0ti+11si+1)⋯(0th1sh), |
then G−e is a chain graph generated by
(0t11s1)⋯(0ti−11si−1+1)(0ti+1+11si+1)⋯(0th1sh). |
Lemma 5.2. Every key edge of a Hamiltonian chain graph lies in at least one Hamilton cycle.
Proof. Let G be Hamiltonian chain graph, e=uv be a key edge of G, with u∈Ui and v∈Vi, and let C be a Hamilton cycle. If e∈C, there is nothing to prove. Otherwise, let C has the form (u,s,…,v,t…). Then u∼s and v∼t which implies s∈Vj for some j≥i and v∈Uk for some k≤i, and consequently s∼t. So, both uv and st are the edges of G. The cycle C′ obtained by adding these two edges to C and deleting us and vt from C is Hamilton and contains e.
We are ready for the main result of this section.
Theorem 5.3. The minimum number of Hamilton cycles in a Hamiltonian chain graph of order n=2h,h≥2, is 2h−2 and this number is attained uniquely by the chain graph Gn generated by
(021)(01)⋯(012)⏟2(h−1). | (5.1) |
Proof. If G is Hamiltonian chain graph, then G has colour classes of the same order, say h (see [3]). If G is generated by (0t11s1⋯0tk1sk), then t1≠1 and sk≠1. The chain graph with minimum number of Hamilton cycles is defined with minimum values of ti's, si's that, according to Corollary 3.6, are t1=sk=2, ti=1,i≠1, sj=1,j≠k. The graph under consideration, i.e., the graph generated by (5.1) is Hamiltonian, which is an easy exercise to prove. If any of ti's, si's takes a greater value than the given one, then by deleting any key edge (which by Lemma 5.2 belongs to at least one Hamilton cycle), we would obtain a graph that, in case that it is Hamiltonian, would have fewer number of Hamilton cycles (as the deletion of an edge cannot increase the number of Hamilton cycles).
It remains to compute the number of Hamilton cycles, say c2h, which can be performed by induction on h. If h=2, then G4=C4 and c4=22−2=1.
Let n=2(h+1). If U1={x,y} and V1={z}, then by Lemma 5.2, neither G2(h+1)−xz nor G2(h+1)−yz is Hamiltonian. Thus the path xzy must lie in every Hamilton cycle of G2(h+1) and so every Hamilton cycle of G2(h+1) must go through z. And from z it may continue either through x or y. Assume, without loss of generality, that z is followed by x. The remaining part of the Hamilton cycle must continue through a vertex a∉{x,y,z} and before it returns to z it should go through y. Since G2(h+1)∖{xz} is isomorphic to G2h, together with 2 possible choices starting from z we obtain c2(h+1)=2c2h=2h−1. This completes the proof.
It is well known that the problem of deciding whether a graph is Hamiltonian is NP-complete [5, Chapter 8]. In this paper we showed that for some graphs with a particular structure, such as threshold and chain graphs, the same decision can be obtained by employing very fast algorithms. We also determined the minimum number of Hamilton cycles in Hamiltonian chain graphs.
Presented results can be extended in several directions. First, by considering more general classes of graphs. A natural step after threshold graphs are the so-called cographs. By definition a graph is a cograph if it does not contain the path P4 as an induced subetaaph. Evidently, every threshold graph is a cograph. It is known that every cograph can be obtained by the iterative procedure based on the fact that if two graphs are cographs then their disjoint union and their join are cographs, as well [6]. Such a procedure can be seen as an extension of the procedure that generates threshold graphs (defined in the opening section and frequently used in this paper).
Next, one may consider the constructions of algorithms that would determine some other structural properties of threshold, chain, or some similar graphs. The question of the minimum number of Hamilton cycles in a cograph is also an open problem.
Finally, our algorithms presented in Section 4 work in general cases for threshold and chain graphs and both employ checking of a sequence of inequalities. It would be interesting to see under which conditions some of these inequalities can be avoided, i.e., what is the structure of the corresponding threshold or chain graph for which this part of the corresponding algorithm can be simplified.
We would like to thank the anonymous referees for their careful reading. Their suggestions and observations improved the content of the paper.
The authors declare no conflict of interests.
[1] | F. Harary, U. Peled, Hamiltonian threshold graphs, Discrete Appl. Math., 16 (1987), 11–15. |
[2] | N. V. R. Mahadev, U. N. Peled, Threshold Graphs and Related Topics, New York: North-Holland, 1995. |
[3] | J. Moon, L. Moser, On Hamiltonian bipartite graphs, Israel J. Math., 1 (1963), 163–165. |
[4] | P. Qiao, X. Zhan, The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order, J. Graph Theory, 93 (2020), 222–229. |
[5] | A. Schrijver, Combinatorial Optimization-Polyhedra and Efficiency, Berlin: Springer, 2003. |
[6] | Z. Stanić, Laplacian controllability for graphs with integral Laplacian spectrum, Mediterr. J. Math., 18 (2021), 35. |