In this paper, a new class of rings, called FIC rings, is introduced for studying quasi-zero-divisor graphs of rings. Let R be a ring. The quasi-zero-divisor graph of R, denoted by Г＊（R）, is a directed graph defin...In this paper, a new class of rings, called FIC rings, is introduced for studying quasi-zero-divisor graphs of rings. Let R be a ring. The quasi-zero-divisor graph of R, denoted by Г＊（R）, is a directed graph defined on its nonzero quasi-zero-divisors, where there is an arc from a vertex x to another vertex y if and only if xRy = 0. We show that the following three conditions on an FIC ring R are equivalent： （1） χ（R） is finite; （2） ω（R） is finite; （3） Nil＊ R is finite where Nil.R equals the finite intersection of prime ideals. Furthermore, we also completely determine the connectedness, the diameter and the girth of Г＊ （R）.展开更多
In [1], Joe Warfel investigated the diameter of a zero-divisor graph for a direct product R 1 × R 2 with respect to the diameter of the zero-divisor graph of R 1 and R 2 . But the author only considered those gra...In [1], Joe Warfel investigated the diameter of a zero-divisor graph for a direct product R 1 × R 2 with respect to the diameter of the zero-divisor graph of R 1 and R 2 . But the author only considered those graphs whose diameters ≥ 1 and discussed six cases. This paper further discusses the other nine cases and also gives a complete characterization for the possible diameters for left Artin rings.展开更多
This paper introduces an ideal-boyed zero-divisor graph of non-commutative rings,denoted ΓI（R）.ΓI（R） is a directed graph.The properties and possible structures of the graph is studied.
We introduce the zero-divisor graph for an abelian regular ring and show that if R,S are abelian regular, then (K0(R),[R])≌(K0(S),[S]) if and only if they have isomorphic reduced zero-divisor graphs. It is shown that...We introduce the zero-divisor graph for an abelian regular ring and show that if R,S are abelian regular, then (K0(R),[R])≌(K0(S),[S]) if and only if they have isomorphic reduced zero-divisor graphs. It is shown that the maximal right quotient ring of a potent semiprimitive normal ring is abelian regular, moreover, the zero-divisor graph of such a ring is studied.展开更多
Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R, denoted by , is a graph with vertices in , which is the set of all non-zero and non-unit elements of R, and two distinct vertices a an...Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R, denoted by , is a graph with vertices in , which is the set of all non-zero and non-unit elements of R, and two distinct vertices a and b in are adjacent if and only if and . In this paper, we investigate some combinatorial properties of the cozero-divisor graphs and such as connectivity, diameter, girth, clique numbers and planarity. We also study the cozero-divisor graphs of the direct products of two arbitrary commutative rings.展开更多
Chemical compounds are modeled as graphs.The atoms of molecules represent the graph vertices while chemical bonds between the atoms express the edges.The topological indices representing the molecular graph correspond...Chemical compounds are modeled as graphs.The atoms of molecules represent the graph vertices while chemical bonds between the atoms express the edges.The topological indices representing the molecular graph corresponds to the different chemical properties of compounds.Let a,b be are two positive integers,andΓ(Z_(a)×Z_(b))be the zero-divisor graph of the commutative ring Z_(a)×Z_(b).In this article some direct questions have been answered that can be utilized latterly in different applications.This study starts with simple computations,leading to a quite complex ring theoretic problems to prove certain properties.The theory of finite commutative rings is useful due to its different applications in the fields of advanced mechanics,communication theory,cryptography,combinatorics,algorithms analysis,and engineering.In this paper we determine the distance-based topological polynomials and indices of the zero-divisor graph of the commutative ring Z_(p^(2))×Z_(q)(for p,q as prime numbers)with the help of graphical structure analysis.The study outcomes help in understanding the fundamental relation between ring-theoretic and graph-theoretic properties of a zero-divisor graphΓ(G).展开更多
With network attack technology continuing to develop,traditional anomaly traffic detection methods that rely on feature engineering are increasingly insufficient in efficiency and accuracy.Graph Neural Network(GNN),a ...With network attack technology continuing to develop,traditional anomaly traffic detection methods that rely on feature engineering are increasingly insufficient in efficiency and accuracy.Graph Neural Network(GNN),a promising Deep Learning(DL)approach,has proven to be highly effective in identifying intricate patterns in graph⁃structured data and has already found wide applications in the field of network security.In this paper,we propose a hybrid Graph Convolutional Network(GCN)⁃GraphSAGE model for Anomaly Traffic Detection,namely HGS⁃ATD,which aims to improve the accuracy of anomaly traffic detection by leveraging edge feature learning to better capture the relationships between network entities.We validate the HGS⁃ATD model on four publicly available datasets,including NF⁃UNSW⁃NB15⁃v2.The experimental results show that the enhanced hybrid model is 5.71%to 10.25%higher than the baseline model in terms of accuracy,and the F1⁃score is 5.53%to 11.63%higher than the baseline model,proving that the model can effectively distinguish normal traffic from attack traffic and accurately classify various types of attacks.展开更多
基于深度学习的网络攻击检测是对欧几里得数据进行建模,无法学习攻击数据中的结构特征。为此,提出一种基于改进图采样与聚合(graph sample and aggregate,GraphSAGE)的网络攻击检测算法。首先,将攻击数据从平面结构转换为图结构数据。其...基于深度学习的网络攻击检测是对欧几里得数据进行建模,无法学习攻击数据中的结构特征。为此,提出一种基于改进图采样与聚合(graph sample and aggregate,GraphSAGE)的网络攻击检测算法。首先,将攻击数据从平面结构转换为图结构数据。其次,对GraphSAGE算法进行了改进,包括在消息传递阶段融合节点和边的特征,同时在消息聚合过程中考虑不同源节点对目标节点的影响程度,并在边嵌入生成时引入残差学习机制。在两个公开网络攻击数据集上的实验结果表明,在二分类情况下,所提算法的总体性能优于E-GraphSAGE、LSTM、RNN、CNN算法;在多分类情况下,所提算法在大多数攻击类型上的F1值高于对比算法。展开更多
Accurately predicting the synthesizability of inorganic crystal materials serves as a pivotal tool for the efficient screening of viable candidates,substantially reducing the costs associated with extensive experiment...Accurately predicting the synthesizability of inorganic crystal materials serves as a pivotal tool for the efficient screening of viable candidates,substantially reducing the costs associated with extensive experimental trial-and-error processes.However,existing methods,limited by static structural descriptors such as chemical composition and lattice parameters,fail to account for atomic vibrations,which may introduce spurious correlations and undermine predictive reliability.Here,we propose a deep learning model termed integrating graph and dynamical stability(IGDS)for predicting the synthesizability of inorganic crystals.IGDS employs graph representation learning to construct crystal graphs that precisely capture the static structures of crystals and integrates phonon spectral features extracted from pre-trained machine learning interatomic potentials to represent their dynamic properties.Our model exhibits outstanding performance in predicting the synthesizability of low-energy unsynthesizable crystals across 41 material systems,achieving precision and recall values of 0.916/0.863 for ternary compounds.By capturing both static structural descriptors and dynamic features,IGDS provides a physics-informed method for predicting the synthesizability of inorganic crystals.This approach bridges the gap between theoretical design concepts and their practical implementation,thereby streamlining the development cycle of new materials and enhancing overall research efficiency.展开更多
In this paper,we first give a sufficient condition for a graph being fractional ID-[a,b]-factor-critical covered in terms of its independence number and minimum degree,which partially answers the problem posed by Sizh...In this paper,we first give a sufficient condition for a graph being fractional ID-[a,b]-factor-critical covered in terms of its independence number and minimum degree,which partially answers the problem posed by Sizhong Zhou,Hongxia Liu and Yang Xu(2022).Then,an A_(α)-spectral condition is given to ensure that G is a fractional ID-[a,b]-factor-critical covered graph and an(a,b,k)-factor-critical graph,respectively.In fact,(a,b,k)-factor-critical graph is a graph which has an[a,b]-factor for k=0.Thus,these above results extend the results of Jia Wei and Shenggui Zhang(2023)and Ao Fan,Ruifang Liu and Guoyan Ao(2023)in some sense.展开更多
A graph G is H-free,if it contains no H as a subgraph.A graph G is said to be H-minor free,if it does not contain H as a minor.In 2010,Nikiforov asked that what the maximum spectral radius of an H-free graph of order ...A graph G is H-free,if it contains no H as a subgraph.A graph G is said to be H-minor free,if it does not contain H as a minor.In 2010,Nikiforov asked that what the maximum spectral radius of an H-free graph of order n is.In this paper,we consider some Brualdi-Solheid-Turan type problems on bipartite graphs.In 2015,Zhai,Lin and Gong in[Linear Algebra Appl.,2015,471:21-27]proved that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains a C_(2k+2) unless G≌K_(k,n-k).First,we give a new and more simple proof for the above theorem.Second,we prove that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains all T_(2k+3) unless G≌K_(k,n-k).Finally,we prove that among all outerplanar bipartite graphs on n≥308026 vertices,K_(1,n-1) attains the maximum spectral radius.展开更多
The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G ...The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G is defined as ME(G) = Pni=1 |λi|. By the famous Coulson’s formula, matching energies can also be calculated by an improper integral depending on a parameter. A k-claw attaching graph Gu(k) refers to the graph obtained by attaching k pendent edges to the graph G at the vertex u, where u is called the root of Gu(k). In this paper, we use some theories of mathematical analysis to obtain a new technique to compare the matching energies of two k-claw attaching graphs Gu(k) and Hv(k) with the same order, that is, limk→∞[ME(Gu(k)) − ME(Hv(k))] = ME(G − u) − ME(H − v). By the technique, we finally determine unicyclic graphs of order n with the 9th to 13th minimal matching energies for all n ≥ 58.展开更多
Let R be an associative ring with identity and Z^*(K)be its set of non-zero zero-divisors.The undirected zero-divisor graph of R、denoted byΓ(R),is the graph whose vert ices are the non-zero zero-divisors of R、and w...Let R be an associative ring with identity and Z^*(K)be its set of non-zero zero-divisors.The undirected zero-divisor graph of R、denoted byΓ(R),is the graph whose vert ices are the non-zero zero-divisors of R、and where two distinct verticesγand s are adjacent if and only ifγs=0 or sγ=0.The dist ance bet ween vertices a and b is the length of the shortest path connecting them,and the diameter of the graph,diam(Γ(R)),is the superimum of these distances.In this paper,first we prove some results aboutΓ(R)of a semi-commutative ring R.Then,for a reversible ring R and a unique product monoid M、we prove 0≦diam(Γ(R))<diam(Γ(R[M]))≦3.We describe all the possibilities for the pair diam(Γ(R))and diam(Γ(R[M])),strictly in terms of the properties of a ring R,where K is a reversible ring and M is a unique product monoid.Moreover,an example showing the necessity of our assumptions is provided.展开更多
Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m...Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m−2), G^((2))m (m ≥ 4) is the graph obtained from Cm by adding two edges v1v3 and v2v4. The famous Zarankiewicz’s conjecture on the crossing number of the complete bipartite graph Km,n states that cr(Km,n)=Z(m,n)=[m/2][m-1/2][n/2[n-1/2].Based on Zarankiewicz’s conjecture, a natural problem is to study the change in the crossingnumber of the graphs obtained from the complete bipartite graph by adding certain edge sets.If Zarankiewicz’s conjecture is true, this paper proves that cr(G^((1))_(m)+Kn)=Z(m,n)+2[n/2] and cr(G^((2))_(m)+Kn)=Z(m,n)+n.展开更多
A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-dege...A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-degenerate.In this paper,we show that if G is a planar graph without kites and 9-or 10-cycles,then G is 3-degenerate,hence 4-choosable and list vertex 2-arborable.展开更多
DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improve...DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improves the results of[Discrete Math.,2018,341(7):1983–1986]and[Discrete Appl.Math.,2020,277:245–251].展开更多
For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant verti...For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant vertices,whereβe{1,2,3,4,n-3,n-2,n-1}.展开更多
基金Supported by the National Natural Science Foundation of China(Grant Nos.1137134311161006+4 种基金1166101411171142)the Guangxi Science Research and Technology Development Project(Grant No.1599005-2-13)the Scientic Research Fund of Guangxi Education Department(Grant No.KY2015ZD075)the Natural Science Foundation of Guangxi(Grant No.2016GXSFDA380017)
文摘In this paper, a new class of rings, called FIC rings, is introduced for studying quasi-zero-divisor graphs of rings. Let R be a ring. The quasi-zero-divisor graph of R, denoted by Г＊（R）, is a directed graph defined on its nonzero quasi-zero-divisors, where there is an arc from a vertex x to another vertex y if and only if xRy = 0. We show that the following three conditions on an FIC ring R are equivalent： （1） χ（R） is finite; （2） ω（R） is finite; （3） Nil＊ R is finite where Nil.R equals the finite intersection of prime ideals. Furthermore, we also completely determine the connectedness, the diameter and the girth of Г＊ （R）.
基金Supported by the Natural Sciences Foundation of Guangxi Province(0575052, 0640070)Supported by the Innovation Project of Guangxi Graduate Education(2006106030701M05)Supported by the Scientific Research Foundation of Guangxi Educational Committee(200707LX233
文摘In [1], Joe Warfel investigated the diameter of a zero-divisor graph for a direct product R 1 × R 2 with respect to the diameter of the zero-divisor graph of R 1 and R 2 . But the author only considered those graphs whose diameters ≥ 1 and discussed six cases. This paper further discusses the other nine cases and also gives a complete characterization for the possible diameters for left Artin rings.
基金Supported by Guangxi Natural Sciences Foundation(0575052,0640070)Supported byInnovation Project of Guangxi Graduate Education(2006106030701M05)Supported Scientific Research Foun-dation of Guangxi Educational Committee
文摘This paper introduces an ideal-boyed zero-divisor graph of non-commutative rings,denoted ΓI（R）.ΓI（R） is a directed graph.The properties and possible structures of the graph is studied.
基金Partially supported by the NSF (10071035) of China.
文摘We introduce the zero-divisor graph for an abelian regular ring and show that if R,S are abelian regular, then (K0(R),[R])≌(K0(S),[S]) if and only if they have isomorphic reduced zero-divisor graphs. It is shown that the maximal right quotient ring of a potent semiprimitive normal ring is abelian regular, moreover, the zero-divisor graph of such a ring is studied.
文摘Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R, denoted by , is a graph with vertices in , which is the set of all non-zero and non-unit elements of R, and two distinct vertices a and b in are adjacent if and only if and . In this paper, we investigate some combinatorial properties of the cozero-divisor graphs and such as connectivity, diameter, girth, clique numbers and planarity. We also study the cozero-divisor graphs of the direct products of two arbitrary commutative rings.
文摘Chemical compounds are modeled as graphs.The atoms of molecules represent the graph vertices while chemical bonds between the atoms express the edges.The topological indices representing the molecular graph corresponds to the different chemical properties of compounds.Let a,b be are two positive integers,andΓ(Z_(a)×Z_(b))be the zero-divisor graph of the commutative ring Z_(a)×Z_(b).In this article some direct questions have been answered that can be utilized latterly in different applications.This study starts with simple computations,leading to a quite complex ring theoretic problems to prove certain properties.The theory of finite commutative rings is useful due to its different applications in the fields of advanced mechanics,communication theory,cryptography,combinatorics,algorithms analysis,and engineering.In this paper we determine the distance-based topological polynomials and indices of the zero-divisor graph of the commutative ring Z_(p^(2))×Z_(q)(for p,q as prime numbers)with the help of graphical structure analysis.The study outcomes help in understanding the fundamental relation between ring-theoretic and graph-theoretic properties of a zero-divisor graphΓ(G).
基金National Natural Science Foundation of China(Grant No.62103434)National Science Fund for Distinguished Young Scholars(Grant No.62176263).
文摘With network attack technology continuing to develop,traditional anomaly traffic detection methods that rely on feature engineering are increasingly insufficient in efficiency and accuracy.Graph Neural Network(GNN),a promising Deep Learning(DL)approach,has proven to be highly effective in identifying intricate patterns in graph⁃structured data and has already found wide applications in the field of network security.In this paper,we propose a hybrid Graph Convolutional Network(GCN)⁃GraphSAGE model for Anomaly Traffic Detection,namely HGS⁃ATD,which aims to improve the accuracy of anomaly traffic detection by leveraging edge feature learning to better capture the relationships between network entities.We validate the HGS⁃ATD model on four publicly available datasets,including NF⁃UNSW⁃NB15⁃v2.The experimental results show that the enhanced hybrid model is 5.71%to 10.25%higher than the baseline model in terms of accuracy,and the F1⁃score is 5.53%to 11.63%higher than the baseline model,proving that the model can effectively distinguish normal traffic from attack traffic and accurately classify various types of attacks.
文摘基于深度学习的网络攻击检测是对欧几里得数据进行建模,无法学习攻击数据中的结构特征。为此,提出一种基于改进图采样与聚合(graph sample and aggregate,GraphSAGE)的网络攻击检测算法。首先,将攻击数据从平面结构转换为图结构数据。其次,对GraphSAGE算法进行了改进,包括在消息传递阶段融合节点和边的特征,同时在消息聚合过程中考虑不同源节点对目标节点的影响程度,并在边嵌入生成时引入残差学习机制。在两个公开网络攻击数据集上的实验结果表明,在二分类情况下,所提算法的总体性能优于E-GraphSAGE、LSTM、RNN、CNN算法;在多分类情况下,所提算法在大多数攻击类型上的F1值高于对比算法。
文摘Accurately predicting the synthesizability of inorganic crystal materials serves as a pivotal tool for the efficient screening of viable candidates,substantially reducing the costs associated with extensive experimental trial-and-error processes.However,existing methods,limited by static structural descriptors such as chemical composition and lattice parameters,fail to account for atomic vibrations,which may introduce spurious correlations and undermine predictive reliability.Here,we propose a deep learning model termed integrating graph and dynamical stability(IGDS)for predicting the synthesizability of inorganic crystals.IGDS employs graph representation learning to construct crystal graphs that precisely capture the static structures of crystals and integrates phonon spectral features extracted from pre-trained machine learning interatomic potentials to represent their dynamic properties.Our model exhibits outstanding performance in predicting the synthesizability of low-energy unsynthesizable crystals across 41 material systems,achieving precision and recall values of 0.916/0.863 for ternary compounds.By capturing both static structural descriptors and dynamic features,IGDS provides a physics-informed method for predicting the synthesizability of inorganic crystals.This approach bridges the gap between theoretical design concepts and their practical implementation,thereby streamlining the development cycle of new materials and enhancing overall research efficiency.
基金Supported by the National Natural Science Foundation of China(Grant Nos.11961041,12261055)the Key Project of Natural Science Foundation of Gansu Province(Grant No.24JRRA222)the Foundation for Innovative Fundamental Research Group Project of Gansu Province(Grant No.25JRRA805).
文摘In this paper,we first give a sufficient condition for a graph being fractional ID-[a,b]-factor-critical covered in terms of its independence number and minimum degree,which partially answers the problem posed by Sizhong Zhou,Hongxia Liu and Yang Xu(2022).Then,an A_(α)-spectral condition is given to ensure that G is a fractional ID-[a,b]-factor-critical covered graph and an(a,b,k)-factor-critical graph,respectively.In fact,(a,b,k)-factor-critical graph is a graph which has an[a,b]-factor for k=0.Thus,these above results extend the results of Jia Wei and Shenggui Zhang(2023)and Ao Fan,Ruifang Liu and Guoyan Ao(2023)in some sense.
基金Supported by NSFC(No.12271162)Natural Science Foundation of Shanghai(No.22ZR1416300).
文摘A graph G is H-free,if it contains no H as a subgraph.A graph G is said to be H-minor free,if it does not contain H as a minor.In 2010,Nikiforov asked that what the maximum spectral radius of an H-free graph of order n is.In this paper,we consider some Brualdi-Solheid-Turan type problems on bipartite graphs.In 2015,Zhai,Lin and Gong in[Linear Algebra Appl.,2015,471:21-27]proved that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains a C_(2k+2) unless G≌K_(k,n-k).First,we give a new and more simple proof for the above theorem.Second,we prove that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains all T_(2k+3) unless G≌K_(k,n-k).Finally,we prove that among all outerplanar bipartite graphs on n≥308026 vertices,K_(1,n-1) attains the maximum spectral radius.
基金Supported by the National Natural Science Foundation of China(Nos.12271439,11871398)the National College Students Innovation and Entrepreneurship Training Program(No.201910699173)。
文摘The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G is defined as ME(G) = Pni=1 |λi|. By the famous Coulson’s formula, matching energies can also be calculated by an improper integral depending on a parameter. A k-claw attaching graph Gu(k) refers to the graph obtained by attaching k pendent edges to the graph G at the vertex u, where u is called the root of Gu(k). In this paper, we use some theories of mathematical analysis to obtain a new technique to compare the matching energies of two k-claw attaching graphs Gu(k) and Hv(k) with the same order, that is, limk→∞[ME(Gu(k)) − ME(Hv(k))] = ME(G − u) − ME(H − v). By the technique, we finally determine unicyclic graphs of order n with the 9th to 13th minimal matching energies for all n ≥ 58.
文摘Let R be an associative ring with identity and Z^*(K)be its set of non-zero zero-divisors.The undirected zero-divisor graph of R、denoted byΓ(R),is the graph whose vert ices are the non-zero zero-divisors of R、and where two distinct verticesγand s are adjacent if and only ifγs=0 or sγ=0.The dist ance bet ween vertices a and b is the length of the shortest path connecting them,and the diameter of the graph,diam(Γ(R)),is the superimum of these distances.In this paper,first we prove some results aboutΓ(R)of a semi-commutative ring R.Then,for a reversible ring R and a unique product monoid M、we prove 0≦diam(Γ(R))<diam(Γ(R[M]))≦3.We describe all the possibilities for the pair diam(Γ(R))and diam(Γ(R[M])),strictly in terms of the properties of a ring R,where K is a reversible ring and M is a unique product monoid.Moreover,an example showing the necessity of our assumptions is provided.
基金Supported by Changsha Natural Science Foundation(No.kq2208001)the Key Project Funded by Hunan Provincial Department of Education(No.21A0590)。
文摘Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m−2), G^((2))m (m ≥ 4) is the graph obtained from Cm by adding two edges v1v3 and v2v4. The famous Zarankiewicz’s conjecture on the crossing number of the complete bipartite graph Km,n states that cr(Km,n)=Z(m,n)=[m/2][m-1/2][n/2[n-1/2].Based on Zarankiewicz’s conjecture, a natural problem is to study the change in the crossingnumber of the graphs obtained from the complete bipartite graph by adding certain edge sets.If Zarankiewicz’s conjecture is true, this paper proves that cr(G^((1))_(m)+Kn)=Z(m,n)+2[n/2] and cr(G^((2))_(m)+Kn)=Z(m,n)+n.
文摘A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-degenerate.In this paper,we show that if G is a planar graph without kites and 9-or 10-cycles,then G is 3-degenerate,hence 4-choosable and list vertex 2-arborable.
基金Partially supported by NSFC(No.12301436)NSF of Guangxi Province(No.2025GXNSFAA069811)。
文摘DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improves the results of[Discrete Math.,2018,341(7):1983–1986]and[Discrete Appl.Math.,2020,277:245–251].
文摘For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant vertices,whereβe{1,2,3,4,n-3,n-2,n-1}.
