Research article

Notes on Hamiltonian threshold and chain graphs

  • Received: 08 November 2020 Accepted: 19 February 2021 Published: 09 March 2021
  • MSC : 05C45

  • We revisit results obtained in [1], where several necessary and necessary and sufficient conditions for a connected threshold graph to be Hamiltonian were obtained. We present these results in new forms, now stated in terms of structural parameters that uniquely define the threshold graph and we extend them to chain graphs. We also identify the chain graph with minimum number of Hamilton cycles within the class of Hamiltonian chain graphs of a given order.

    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

    Related Papers:

    [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 [1], where several necessary and necessary and sufficient conditions for a connected threshold graph to be Hamiltonian were obtained. We present these results in new forms, now stated in terms of structural parameters that uniquely define the threshold graph and we extend them to chain graphs. We also identify the chain graph with minimum number of Hamilton cycles within the class of Hamiltonian chain graphs of a given order.



    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=(b1b2bn) in the following way:

    (i) for i=1, G1=G(b1)=K1, i.e., a single vertex;

    (ii) for i2, with Gi1=G(b1b2bi1) already constructed, Gi=G(b1b2bi1bi) is formed by adding an isolated vertex to Gi1 if bi=0 (that is, a vertex non-adjacent to any vertex in Gi1) or by adding a dominating vertex to Gi1 if bi=1 (that is, a vertex adjacent to all the vertices in Gi1).

    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(1ih).

    Figure 1.  A schematic representation of a threshold and a chain graph.

    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 i2, with Gi1=G(b1b2bi1), Gi=G(b1b2bi1bi) is obtained by adding to Gi1 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,for1ih. (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 xU1, 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 IJ, 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 d1d2dr and e1e2es denote the degrees of the vertices x1,x2,,xrI and y1,y2,,ysJ, 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 IJ, 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 esr=0, then G is not Hamiltonian.

    In what follows we only consider threshold graphs with r2, since for r=0, G is Hamiltonian if and only if s3, while for r=1, G is Hamiltonian if and only if d12.

    Since any threshold graph is a split graph, by the previous lemma, Hamiltonian threshold graphs satisfy 2rs and esr>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 2r<s and esr>0, then the threshold graph G is Hamiltonian if and only if the threshold subetaaph G obtained by deleting the vertices y1,y2,,ysr is Hamiltonian.

    Remark 2.1. In [1] the conclusion that after dropping y1,y2,,ysr 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 {ysr+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 rs, 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

    djj+1,for1jq;ejj+1,for1j|U|1q.

    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 t11, then the degrees of vertices in B corresponding to {a co-clique I and a maximal clique J=V{x} for some xU1 are:

    dth1,dth12,,dt11h,withdj=hi=h+1jsi01,es11,es22,,eshh,withej=ji=1ti1. (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,Uh1,,U1{x} and {x},V1,V2,,Vh, respectively.

    Otherwise, if t1=1, then G is a split graph in which the subetaaph induced by VU1 gives a maximal clique. Then the degrees of vertices in B corresponding to the colour classes hi=2Ui and VU1 are:

    dth1,dth12,,dt2h1,withdj=hi=h+1jsi,01+s1,es22,,eshh,withej=ji=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=T1 and s=S+1.

    We first state the following lemma that determines when esr=0 may occur.

    Lemma 3.1. Let G be a threshold graph generated by (1.1), such that s>r. Then esr=0 holds if and only if t11 and sr=1 or t1=1 and sr{1,2,,s1+1}.

    Proof. From (3.1), it follows that for t11, 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 t11 and sr=1 or t1=1 and sr{1,2,,s1+1}, then G is not Hamiltonian.

    In the sequel we consider only threshold graphs with sr+2 if t11 and with sr+s1+2 if t1=1. Let the integer be defined in the following way: if sr1<s1, then =0; otherwise, is the least integer such that i=1sisr1<+1i=1si (obviously, such an integer exists). The dropping of the vertices y1,y2,,ysr from J is equivalent to dropping y1 from U1 and y2,,ysr from V. Consequently, the new graph G is generated by the binary sequence

    (0+1i=1ti11+1i=1si(sr1)0t+21s+20th1sh). (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 sr2. Then G is Hamiltonian if and only if a threshold graph G generated by (3.3) is Hamiltonian.

    For s+1=+1i=1si(sr1), the degrees of vertices in U and V in the corresponding bipartite graph B of G given in non-decreasing order are

    d1==dth=sh,dth+1==dth+th1=sh1+sh,adt+3++th+1==dt+2++th=hi=+2si,dt+2++th+1==dt1+t2++th1=hi=1ti1ande1==es+1=+1i=1ti1,es+1+1==es+1+s+2=+2i=1ti1,aes+1+s+2++sh1+1==es+1+s+2++sh=hi=1ti1.

    Next, we consider the system of inequalities Sq, q{0,1,,T1}, for hi=1si=hi=1ti.

    Lemma 3.4. Let G be a threshold graph generated by (1.1), with hi=1si=hi=1ti2. Then G is Hamiltonian if and only if

    hi=jsihi=jti+1,for2jh. (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=T1. On the other hand, for (3.4) and each repeated vertex degree, we have

    {hi=jsihi=j+1ti+2,a,,,hi=jsihi=j+1ti+tj+1=hi=jti+1.

    Now, it is easy to see that ST1 holds if and only if (3.4) holds. Note that the inequality hi=1sihi=1ti1+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 r2. If either sr+1 for t11 or sr+s1+1 for t1=1, then G is not Hamiltonian. Otherwise, G is Hamiltonian if and only if +1=h or

    hi=jsihi=jti,for+2jh, (3.5)

    where for sr1<s1, =0, and otherwise is the least integer such that i=1sisr1<+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

    hi=jsihi=jti,for+2jh,

    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 t1s1+1 and shth+1 must hold.

    Corollary 3.6. Let G be a chain graph generated by (1.1), such that T2. If either ST or S=T and t1<s1+1 or sh<th+1, then G is not Hamiltonian. Otherwise, G is Hamiltonian if and only if

    hi=jsihi=jti+1,for2jh.

    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=1ti1; s=hi=1si+1.

    2.If r=1d1=sh2 then RETURN TRUE. If r=1d1=sh=1 then RETURN FALSE.

    3.If (t11sr+1)(t1=1sr+s1+1) then RETURN FALSE.

    4.Determine the least integer such that i=1sisr1<+1i=1si. If sr1<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 TS(T=S(t1<s1+1sh<th+1)) then RETURN FALSE.

    3.If the inequalities hi=jsihi=jti+1 hold for 2jh 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=h1, 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 t12, if s1t11 then G is not Hamiltonian. If s1t1 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 s22. For r2, if either t1+t2+2>s1+s2, t11 or s2<1+t2, t1=1 then G is not Hamiltonian. Otherwise, if sr1<s1, then G is Hamiltonian if and only if s2t2, while if sr1s1 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<30201<10, which implies that =1. We next verify that the following inequalities hold: s3+s4t3+t4 and s4t4, 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+s4t2+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 1ih (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 Ge is a chain graph.

    Proof. Let e=uv, where uUi and vVi. We consider the following cases.

    Case 1. If ti>1, si>1 then Ge is a chain graph generated by

    (0t11s1)(0ti11si1)(0ti111)(011si1)(0ti+11si+1)(0th1sh).

    Case 2. If ti>1, si=1, i.e., if G is generated by

    (0t11s1)(0ti11si1)(0ti11)(0ti+11si+1)(0th1sh),

    then Ge is a chain graph generated by

    (0t11s1)(0ti11si1)(0ti111)(0ti+1+11si+1)(0th1sh).

    Case 3. If ti=1, si>1, i.e, if G is generated by

    (0t11s1)(0ti11si1)(011si)(0ti+11si+1)(0th1sh),

    then Ge is a chain graph generated by

    (0t11s1)(0ti11si1+1)(011si1)(0ti+1+11si+1)(0th1sh).

    Case 4. If ti=si=1, i.e., if G is generated by

    (0t11s1)(0ti11si1)(0111)(0ti+11si+1)(0th1sh),

    then Ge is a chain graph generated by

    (0t11s1)(0ti11si1+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 uUi and vVi, and let C be a Hamilton cycle. If eC, there is nothing to prove. Otherwise, let C has the form (u,s,,v,t). Then us and vt which implies sVj for some ji and vUk for some ki, and consequently st. 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,h2, is 2h2 and this number is attained uniquely by the chain graph Gn generated by

    (021)(01)(012)2(h1). (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 (0t11s10tk1sk), then t11 and sk1. 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,i1, sj=1,jk. 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=222=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=2h1. 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.
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2492) PDF downloads(101) Cited by(0)

Figures and Tables

Figures(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog