In this paper,we prove that L(K_(x,y))(λ),theλ-fold line graph of the complete bipartite graph Ka,y,has a C_(6)-decomposition if and only if ry≥6,λxy(c+y-2)=0(mod 12)and(x+y)=0(mod 2),where x,y are nonnegative int...In this paper,we prove that L(K_(x,y))(λ),theλ-fold line graph of the complete bipartite graph Ka,y,has a C_(6)-decomposition if and only if ry≥6,λxy(c+y-2)=0(mod 12)and(x+y)=0(mod 2),where x,y are nonnegative integers and(x,y)≠(2,4)or(2,5).展开更多
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.展开更多
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.展开更多
A signed graph S=(S^(u),σ)has an underlying graph Suand a functionσ:E(S^(u))-→{+,-}.Let E^(-)(S)denote the set of negative edges of S.Then S is eulerian signed graph(or subeulerian signed graph,or balanced eulerian...A signed graph S=(S^(u),σ)has an underlying graph Suand a functionσ:E(S^(u))-→{+,-}.Let E^(-)(S)denote the set of negative edges of S.Then S is eulerian signed graph(or subeulerian signed graph,or balanced eulerian signed graph,respectively)if Suis eulerian(or subeulerian,or eulerian and|E-(S)|is even,respectively).We say that S is balanced subeulerian signed graph if there exists a balanced eulerian signed graph S′such that S′is spanned by S.The signed line graph L(S)of a signed graph S is a signed graph with the vertices of L(S)being the edges of S,where an edge eiej is in L(S)if and only if the edges e_(i)and e_(j)of S have a vertex in common in S such that an edge eiej in L(S)is negative if and only if both edges ei and ej are negative in S.In this paper,two families of signed graphs S and S′are identified,which are applied to characterize balanced subeulerian signed graphs and balanced subeulerian signed line graphs.In particular,it is proved that a signed graph S is balanced subeulerian if and only if S∈S,and that a signed line graph of signed graph S is balanced subeulerian if and only if S∈S′.展开更多
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.展开更多
The increasing popularity of the Internet and the widespread use of information technology have led to a rise in the number and sophistication of network attacks and security threats.Intrusion detection systems are cr...The increasing popularity of the Internet and the widespread use of information technology have led to a rise in the number and sophistication of network attacks and security threats.Intrusion detection systems are crucial to network security,playing a pivotal role in safeguarding networks from potential threats.However,in the context of an evolving landscape of sophisticated and elusive attacks,existing intrusion detection methodologies often overlook critical aspects such as changes in network topology over time and interactions between hosts.To address these issues,this paper proposes a real-time network intrusion detection method based on graph neural networks.The proposedmethod leverages the advantages of graph neural networks and employs a straightforward graph construction method to represent network traffic as dynamic graph-structured data.Additionally,a graph convolution operation with a multi-head attention mechanism is utilized to enhance the model’s ability to capture the intricate relationships within the graph structure comprehensively.Furthermore,it uses an integrated graph neural network to address dynamic graphs’structural and topological changes at different time points and the challenges of edge embedding in intrusion detection data.The edge classification problem is effectively transformed into node classification by employing a line graph data representation,which facilitates fine-grained intrusion detection tasks on dynamic graph node feature representations.The efficacy of the proposed method is evaluated using two commonly used intrusion detection datasets,UNSW-NB15 and NF-ToN-IoT-v2,and results are compared with previous studies in this field.The experimental results demonstrate that our proposed method achieves 99.3%and 99.96%accuracy on the two datasets,respectively,and outperforms the benchmark model in several evaluation metrics.展开更多
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.展开更多
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.
For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which ...For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.展开更多
文摘In this paper,we prove that L(K_(x,y))(λ),theλ-fold line graph of the complete bipartite graph Ka,y,has a C_(6)-decomposition if and only if ry≥6,λxy(c+y-2)=0(mod 12)and(x+y)=0(mod 2),where x,y are nonnegative integers and(x,y)≠(2,4)or(2,5).
文摘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.
基金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 the National Natural Science Foundation of China(Grant No.12261016)。
文摘A signed graph S=(S^(u),σ)has an underlying graph Suand a functionσ:E(S^(u))-→{+,-}.Let E^(-)(S)denote the set of negative edges of S.Then S is eulerian signed graph(or subeulerian signed graph,or balanced eulerian signed graph,respectively)if Suis eulerian(or subeulerian,or eulerian and|E-(S)|is even,respectively).We say that S is balanced subeulerian signed graph if there exists a balanced eulerian signed graph S′such that S′is spanned by S.The signed line graph L(S)of a signed graph S is a signed graph with the vertices of L(S)being the edges of S,where an edge eiej is in L(S)if and only if the edges e_(i)and e_(j)of S have a vertex in common in S such that an edge eiej in L(S)is negative if and only if both edges ei and ej are negative in S.In this paper,two families of signed graphs S and S′are identified,which are applied to characterize balanced subeulerian signed graphs and balanced subeulerian signed line graphs.In particular,it is proved that a signed graph S is balanced subeulerian if and only if S∈S,and that a signed line graph of signed graph S is balanced subeulerian if and only if S∈S′.
文摘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.
文摘The increasing popularity of the Internet and the widespread use of information technology have led to a rise in the number and sophistication of network attacks and security threats.Intrusion detection systems are crucial to network security,playing a pivotal role in safeguarding networks from potential threats.However,in the context of an evolving landscape of sophisticated and elusive attacks,existing intrusion detection methodologies often overlook critical aspects such as changes in network topology over time and interactions between hosts.To address these issues,this paper proposes a real-time network intrusion detection method based on graph neural networks.The proposedmethod leverages the advantages of graph neural networks and employs a straightforward graph construction method to represent network traffic as dynamic graph-structured data.Additionally,a graph convolution operation with a multi-head attention mechanism is utilized to enhance the model’s ability to capture the intricate relationships within the graph structure comprehensively.Furthermore,it uses an integrated graph neural network to address dynamic graphs’structural and topological changes at different time points and the challenges of edge embedding in intrusion detection data.The edge classification problem is effectively transformed into node classification by employing a line graph data representation,which facilitates fine-grained intrusion detection tasks on dynamic graph node feature representations.The efficacy of the proposed method is evaluated using two commonly used intrusion detection datasets,UNSW-NB15 and NF-ToN-IoT-v2,and results are compared with previous studies in this field.The experimental results demonstrate that our proposed method achieves 99.3%and 99.96%accuracy on the two datasets,respectively,and outperforms the benchmark model in several evaluation metrics.
基金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.
文摘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 National Natural Science Foundation of China(Grant Nos.1097102510901035)
文摘For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.
