Xiong and Liu[21]gave a characterization of the graphs G for which the n-iterated line graph L^(n)(G)is hamiltonian,for n≥2.In this paper,we study the existence of a hamiltonian path in L^(n)(G),and give a characteri...Xiong and Liu[21]gave a characterization of the graphs G for which the n-iterated line graph L^(n)(G)is hamiltonian,for n≥2.In this paper,we study the existence of a hamiltonian path in L^(n)(G),and give a characterization of G for which L^(n)(G)has a hamiltonian path.As applications,we use this characterization to give several upper bounds on the hamiltonian path index of a graph.展开更多
We consider even factors with a bounded number of components in the n-times iterated line graphs L^n(G). We present a characterization of a simple graph G such that L^n(G) has an even factor with at most k components,...We consider even factors with a bounded number of components in the n-times iterated line graphs L^n(G). We present a characterization of a simple graph G such that L^n(G) has an even factor with at most k components, based on the existence of a certain type of subgraphs in G. Moreover, we use this result to give some upper bounds for the minimum number of components of even factors in L^n(G) and also show that the minimum number of components of even factors in L^n(G) is stable under the closure operation on a claw-free graph G, which extends some known results. Our results show that it seems to be NP-hard to determine the minimum number of components of even factors of iterated line graphs. We also propose some problems for further research.展开更多
In this note,we show a sharp lower bound of min{Σ_(i=1)^(k)dG(u_(i)):u1u2...uk is a path of(2-)connected G}on its order such that(k-1)-iterated line graphs L^(k-1)(G)are hamiltonian.
Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
基金Supported by the Natural Science Foundation of China(12131013,12371356)the special fund for Science and Technology Innovation Teams of Shanxi Province(202204051002015)the Fundamental Research Program of Shanxi Province(202303021221064).
文摘Xiong and Liu[21]gave a characterization of the graphs G for which the n-iterated line graph L^(n)(G)is hamiltonian,for n≥2.In this paper,we study the existence of a hamiltonian path in L^(n)(G),and give a characterization of G for which L^(n)(G)has a hamiltonian path.As applications,we use this characterization to give several upper bounds on the hamiltonian path index of a graph.
基金supported by National Natural Science Foundation of China (Grant Nos. 11471037 and 11171129)Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20131101110048)
文摘We consider even factors with a bounded number of components in the n-times iterated line graphs L^n(G). We present a characterization of a simple graph G such that L^n(G) has an even factor with at most k components, based on the existence of a certain type of subgraphs in G. Moreover, we use this result to give some upper bounds for the minimum number of components of even factors in L^n(G) and also show that the minimum number of components of even factors in L^n(G) is stable under the closure operation on a claw-free graph G, which extends some known results. Our results show that it seems to be NP-hard to determine the minimum number of components of even factors of iterated line graphs. We also propose some problems for further research.
基金Supported by the National Natural Science Foundation of China(11871099).
文摘In this note,we show a sharp lower bound of min{Σ_(i=1)^(k)dG(u_(i)):u1u2...uk is a path of(2-)connected G}on its order such that(k-1)-iterated line graphs L^(k-1)(G)are hamiltonian.
文摘Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
