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.展开更多
Let G be a simple connected graph with n vertices and m edges,L G be the line graph of G and λ 1(L G)≥λ 2(L G)≥...≥λ m(L G) be the eigenvalues of the graph L G.In this paper,the range of eigenvalues of a...Let G be a simple connected graph with n vertices and m edges,L G be the line graph of G and λ 1(L G)≥λ 2(L G)≥...≥λ m(L G) be the eigenvalues of the graph L G.In this paper,the range of eigenvalues of a line graph is considered.Some sharp upper bounds and sharp lower bounds of the eigenvalues of L G are obtained.In particular,it is proved that-2cos(πn)≤λ n-1 (L G)≤n-4 and λ n(L G)=-2 if and only if G is bipartite.展开更多
In this paper,we give a necessary and sufficient condition for the existence of P3-factors in the line graph of a tree.Then we present an algorithm to determine whether the line graph of a tree has a P3-factor.
This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result ...This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result of Veldman([8]) this result settles the conjecture of Benhocine, et.al([1]): Let G be a connected almost bridgeless graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1). If n is sufficintly large, L(G) is pancyclic.展开更多
A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x ,y) is in E for each x not equal to y . The motivation to study representable gr...A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x ,y) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.展开更多
The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamilt...The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamiltonian, Eulerian, planer, regular, locally and locally connected is given. The chromatic number when is a power of a prime is computed. Further properties for and are also discussed.展开更多
The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D...The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.展开更多
It is well known that a shaded link diagram corresponds to a signed plane multi-graph.In graph theory,line graph is an old and important concept originally introduced by H.Whitney in 1932.In this paper we define the l...It is well known that a shaded link diagram corresponds to a signed plane multi-graph.In graph theory,line graph is an old and important concept originally introduced by H.Whitney in 1932.In this paper we define the line graph link to be a link which has a diagram whose corresponding signed plane graph is a signed line graph.The main purpose of the paper is to illustrate the structure of planar line graphs,which permits us to deal with its signed Tutte polynomial and the Jones polynomials of line graph links.展开更多
Let G be a multigraph.Suppose that e=u1v1 and e′=u2v2 are two edges of G.If e≠e′,then G(e,e′)is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e′=u2v2 with a path u2ve′v2,where...Let G be a multigraph.Suppose that e=u1v1 and e′=u2v2 are two edges of G.If e≠e′,then G(e,e′)is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e′=u2v2 with a path u2ve′v2,where ve,ve′are two new vertices not in V(G).If e=e′,then G(e,e′),also denoted by G(e),is obtained from G by replacing e=u1v1 with a path u1vev1.A graph G is strongly spanning trailable if for any e,e′∈E(G),G(e,e′)has a spanning(ve,ve′)-trail.The design of n processor network with given number of connections from each processor and with a desirable strength of the network can be modelled as a degree sequence realization problem with certain desirable graphical properties.A sequence d=(d1,d2,⋯,dn)is multigraphic if there is a multigraph G with degree sequence d,and such a graph G is called a realization of d.A multigraphic degree sequence d is strongly spanning trailable if d has a realization G which is a strongly spanning trailable graph,and d is line-hamiltonian-connected if d has a realization G such that the line graph of G is hamiltonian-connected.In this paper,we prove that a nonincreasing multigraphic sequence d=(d1,d2)⋯,dn)is strongly spanning trailable if and only if either n=1 and d1=0 or n≥2 and dn≥3.Applying this result,we prove that for a nonincreasing multigraphic sequence d=(d1,d2,⋯,dn),if n≥2 and dn≥3,then d is line-hamiltonian-connected.展开更多
The Wiener index W(G)of a graph G is a distance-based topological index defined as the sum of distances between all pairs of vertices in G.It is shown that forλ=2 there is an infinite family of planar bipartite chemi...The Wiener index W(G)of a graph G is a distance-based topological index defined as the sum of distances between all pairs of vertices in G.It is shown that forλ=2 there is an infinite family of planar bipartite chemical graphs G of girth 4 with the cyclomatic numberλ,but their line graphs are not chemical graphs,and forλ≥2 there are two infinite families of planar nonbipartite graphs G of girth 3 with the cyclomatic numberλ;the three classes of graphs have the property W(G)=W(L(G)),where L(G)is the line graph of G.展开更多
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.展开更多
Which graphs are 1-factorizable? In other words, which graphs are regular graphs of class 1? It is an interesting open problem. The importance and difficulty of this problem become apparent when we realize that the fo...Which graphs are 1-factorizable? In other words, which graphs are regular graphs of class 1? It is an interesting open problem. The importance and difficulty of this problem become apparent when we realize that the four-colour theorem holds if and only if every bridgeless 3-regular planar graph is 1-factorable. Jaeger proved that if a regular展开更多
The authoros specialize in the field of optunization and automatic programme oftrain working graph. In this peper, at frist, a mixed 0-1 integer progranimingmodel about this problem for duuble-track lines is set up, t...The authoros specialize in the field of optunization and automatic programme oftrain working graph. In this peper, at frist, a mixed 0-1 integer progranimingmodel about this problem for duuble-track lines is set up, then the principle andProcess of selution are stated, with an application exaiiiple put forward.展开更多
BACKGROUND Gastric cancer is a leading cause of cancer-related deaths worldwide.Prognostic assessments are typically based on the tumor-node-metastasis(TNM)staging system,which does not account for the molecular heter...BACKGROUND Gastric cancer is a leading cause of cancer-related deaths worldwide.Prognostic assessments are typically based on the tumor-node-metastasis(TNM)staging system,which does not account for the molecular heterogeneity of this disease.LATS2,a tumor suppressor gene involved in the Hippo signaling pathway,has been identified as a potential prognostic biomarker in gastric cancer.AIM To construct and validate a nomogram model that includes LATS2 expression to predict the survival prognosis of advanced gastric cancer patients following ra-dical surgery,and compare its predictive performance with traditional TNM staging.METHODS A retrospective analysis of 245 advanced gastric cancer patients from the Fourth Hospital of Hebei Medical University was conducted.The patients were divided into a training group(171 patients)and a validation group(74 patients)to deve-lop and test our prognostic model.The performance of the model was determined using C-indices,receiver operating characteristic curves,calibration plots,and decision curves.RESULTS The model demonstrated a high predictive accuracy with C-indices of 0.829 in the training set and 0.862 in the validation set.Area under the curve values for three-year and five-year survival prediction were significantly robust,suggesting an excellent discrimination ability.Calibration plots confirmed the high concordance between the predictions and actual survival outcomes.CONCLUSION We developed a nomogram model incorporating LATS2 expression,which significantly outperformed conven-tional TNM staging in predicting the prognosis of advanced gastric cancer patients postsurgery.This model may serve as a valuable tool for individualized patient management,allowing for more accurate stratification and im-proved clinical outcomes.Further validation in larger patient cohorts will be necessary to establish its generaliza-bility and clinical utility.展开更多
基金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.
文摘Let G be a simple connected graph with n vertices and m edges,L G be the line graph of G and λ 1(L G)≥λ 2(L G)≥...≥λ m(L G) be the eigenvalues of the graph L G.In this paper,the range of eigenvalues of a line graph is considered.Some sharp upper bounds and sharp lower bounds of the eigenvalues of L G are obtained.In particular,it is proved that-2cos(πn)≤λ n-1 (L G)≤n-4 and λ n(L G)=-2 if and only if G is bipartite.
文摘In this paper,we give a necessary and sufficient condition for the existence of P3-factors in the line graph of a tree.Then we present an algorithm to determine whether the line graph of a tree has a P3-factor.
文摘This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result of Veldman([8]) this result settles the conjecture of Benhocine, et.al([1]): Let G be a connected almost bridgeless graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1). If n is sufficintly large, L(G) is pancyclic.
文摘A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x ,y) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.
文摘The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamiltonian, Eulerian, planer, regular, locally and locally connected is given. The chromatic number when is a power of a prime is computed. Further properties for and are also discussed.
基金Supported by the National Natural Science Foundation of China(No.10271114,No.10301031).
文摘The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.
基金This paper is supported by the Fundamental Research Funds for the Central Universities(Grant No.20720190071).
文摘It is well known that a shaded link diagram corresponds to a signed plane multi-graph.In graph theory,line graph is an old and important concept originally introduced by H.Whitney in 1932.In this paper we define the line graph link to be a link which has a diagram whose corresponding signed plane graph is a signed line graph.The main purpose of the paper is to illustrate the structure of planar line graphs,which permits us to deal with its signed Tutte polynomial and the Jones polynomials of line graph links.
基金This paper is supported by the National Natural Science Foundation of China(Nos.11771039,11971054)Fundamental Research Funds for the Central Universities of China(No.2015JBM107)the 111 Project of China(No.B16002)。
文摘Let G be a multigraph.Suppose that e=u1v1 and e′=u2v2 are two edges of G.If e≠e′,then G(e,e′)is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e′=u2v2 with a path u2ve′v2,where ve,ve′are two new vertices not in V(G).If e=e′,then G(e,e′),also denoted by G(e),is obtained from G by replacing e=u1v1 with a path u1vev1.A graph G is strongly spanning trailable if for any e,e′∈E(G),G(e,e′)has a spanning(ve,ve′)-trail.The design of n processor network with given number of connections from each processor and with a desirable strength of the network can be modelled as a degree sequence realization problem with certain desirable graphical properties.A sequence d=(d1,d2,⋯,dn)is multigraphic if there is a multigraph G with degree sequence d,and such a graph G is called a realization of d.A multigraphic degree sequence d is strongly spanning trailable if d has a realization G which is a strongly spanning trailable graph,and d is line-hamiltonian-connected if d has a realization G such that the line graph of G is hamiltonian-connected.In this paper,we prove that a nonincreasing multigraphic sequence d=(d1,d2)⋯,dn)is strongly spanning trailable if and only if either n=1 and d1=0 or n≥2 and dn≥3.Applying this result,we prove that for a nonincreasing multigraphic sequence d=(d1,d2,⋯,dn),if n≥2 and dn≥3,then d is line-hamiltonian-connected.
基金This work was supported by the National Natural Science Foundation of China(No.11171273)The authors would like to express their sincere gratitude to the anonymous referees for their comments and remarks,which improved the presentation of this paper.
文摘The Wiener index W(G)of a graph G is a distance-based topological index defined as the sum of distances between all pairs of vertices in G.It is shown that forλ=2 there is an infinite family of planar bipartite chemical graphs G of girth 4 with the cyclomatic numberλ,but their line graphs are not chemical graphs,and forλ≥2 there are two infinite families of planar nonbipartite graphs G of girth 3 with the cyclomatic numberλ;the three classes of graphs have the property W(G)=W(L(G)),where L(G)is the line graph of G.
基金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.
基金Project supported by the National Natural Science Foundation of China.
文摘Which graphs are 1-factorizable? In other words, which graphs are regular graphs of class 1? It is an interesting open problem. The importance and difficulty of this problem become apparent when we realize that the four-colour theorem holds if and only if every bridgeless 3-regular planar graph is 1-factorable. Jaeger proved that if a regular
文摘The authoros specialize in the field of optunization and automatic programme oftrain working graph. In this peper, at frist, a mixed 0-1 integer progranimingmodel about this problem for duuble-track lines is set up, then the principle andProcess of selution are stated, with an application exaiiiple put forward.
文摘BACKGROUND Gastric cancer is a leading cause of cancer-related deaths worldwide.Prognostic assessments are typically based on the tumor-node-metastasis(TNM)staging system,which does not account for the molecular heterogeneity of this disease.LATS2,a tumor suppressor gene involved in the Hippo signaling pathway,has been identified as a potential prognostic biomarker in gastric cancer.AIM To construct and validate a nomogram model that includes LATS2 expression to predict the survival prognosis of advanced gastric cancer patients following ra-dical surgery,and compare its predictive performance with traditional TNM staging.METHODS A retrospective analysis of 245 advanced gastric cancer patients from the Fourth Hospital of Hebei Medical University was conducted.The patients were divided into a training group(171 patients)and a validation group(74 patients)to deve-lop and test our prognostic model.The performance of the model was determined using C-indices,receiver operating characteristic curves,calibration plots,and decision curves.RESULTS The model demonstrated a high predictive accuracy with C-indices of 0.829 in the training set and 0.862 in the validation set.Area under the curve values for three-year and five-year survival prediction were significantly robust,suggesting an excellent discrimination ability.Calibration plots confirmed the high concordance between the predictions and actual survival outcomes.CONCLUSION We developed a nomogram model incorporating LATS2 expression,which significantly outperformed conven-tional TNM staging in predicting the prognosis of advanced gastric cancer patients postsurgery.This model may serve as a valuable tool for individualized patient management,allowing for more accurate stratification and im-proved clinical outcomes.Further validation in larger patient cohorts will be necessary to establish its generaliza-bility and clinical utility.
