The circular clique number of a graph G is the maximum fractional k/d suchthat G_d^k admits a homomorphism to G. In this paper, we give some sufficient conditions for graphswhose circular clique number equal the cliqu...The circular clique number of a graph G is the maximum fractional k/d suchthat G_d^k admits a homomorphism to G. In this paper, we give some sufficient conditions for graphswhose circular clique number equal the clique number, we also characterize the K_(1,3)-free graphsand planar graphs with the desired property.展开更多
Let R be a commutative ring and Γ(R)be its zero-divisor graph.We completely determine the structure of all finite commutative rings whose zero-divisor graphs have clique number one,two,or three.Furthermore,if R■R1&#...Let R be a commutative ring and Γ(R)be its zero-divisor graph.We completely determine the structure of all finite commutative rings whose zero-divisor graphs have clique number one,two,or three.Furthermore,if R■R1×R2×…×Rn(each Ri is local for i=1,2,3,...,n),we also give algebraic characterizations of the ring R when the clique number of Γ(R)is four.展开更多
We study the algebraic structure of rings R whose zero-divisor graph T(R)has clique number four.Furthermore,we give complete characterizations of all the finite commutative local rings with clique number 4.
Given two ideals I and J of a commutative ring R,there are two extreme connections between I and J:I+J=R and I∩J={0}.For the former case,graphs whose vertices are defined as the proper ideals of R and that two vertic...Given two ideals I and J of a commutative ring R,there are two extreme connections between I and J:I+J=R and I∩J={0}.For the former case,graphs whose vertices are defined as the proper ideals of R and that two vertices are adjacent if and only if their sum is the whole ring R are known as co-maximal ideal graphs.In this paper,we introduce a new kind of graph structure on R,called co-minimal ideal graph,according to the second case:Its vertices are the nonzero ideals of R and two vertices are adjacent if and only if their intersection is zero.Some important graph parameters(including girth,diameter,clique number and chromatic number)and graph structures(including tree and bipartite graph)of co-minimal ideal graphs over finite commutative rings are studied.In particular,we show that the co-maximal ideal graph and the co-minimal ideal graph over R are isomorphic if and only if the number of maximal ideals of R and the number of minimal ideals of R coincide.展开更多
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）.展开更多
Let G and H be two induced subgraph isomorphic to conjectured that, for every tree function, depending only on T graphs. We say that G induces H if G has an H. A. Gyarfas and D. Sumner, independently, T, there exists ...Let G and H be two induced subgraph isomorphic to conjectured that, for every tree function, depending only on T graphs. We say that G induces H if G has an H. A. Gyarfas and D. Sumner, independently, T, there exists a function fT, called binding with the property that every graph G with chromatic number fT（ω（G）） induces T. A. Gyarfas, E. Szemeedi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyarfas et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with co（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（14^r-1（r - 1）!） times. We extend the approach of A. Gyarfas and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott＇s upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（6^r-2） times.展开更多
Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this no...Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved： 1. max {φ（G）： ｜V（G）｜ = 2n, κ（G）≤ k} = k[（2n - 3）!!], 2. max{φ（G）： ｜V（G）｜ = 2n,α（G） ≥ k} =[∏ i=0^k-1 （2n - k-i]（2n - 2k - 1）!!], 3. max{φ（G）： ｜V（G）｜=2n, χ（G） ≤ k} =φ（Tk,2n） Tk,2n is the Turán graph, that is a complete k-partitc graph on 2n vertices in which all parts are as equal in size as possible, 4. max{φ（G）： ｜V（G）｜ = 2n, cl（G） = 2} = n!, 5. max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥〉 2} = （2n - 2）（2n - 3）[（2n - 5）!!], max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥ 3} = （n - 1）^2[（2n - 5）!!].展开更多
Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainb...Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc（G）, is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that trc（G） = 3 if （n-12） ＋ 1 ≤ ｜E（G）｜≤ （n2） - 1, and trc（G） ≤ 6 if ｜E（G）｜≥ （n22） ＋2. Next, we investigate the total rainbow connection numbers of graphs G with ｜V（G）｜ = n, diam（G） ≥ 2, and clique number w（G） = n - s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31（2）： 313-320] is not completely correct, and we provide a complete result for this theorem.展开更多
Let G be a graph.We useχ(G)andω(G)to denote the chromatic number and clique number of G respectively.A P_(5)is a path on 5 vertices,and an HVN is a K_(4)together with one more vertex which is adjacent to exactly two...Let G be a graph.We useχ(G)andω(G)to denote the chromatic number and clique number of G respectively.A P_(5)is a path on 5 vertices,and an HVN is a K_(4)together with one more vertex which is adjacent to exactly two vertices of K_(4).Combining with some known result,in this paper we show that if G is(P_(5),HVN)-free,thenχ(G)≤max{min{16,ω(G)+3},ω(G)+1}.This upper bound is almost sharp.展开更多
An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors...An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.展开更多
Let R be a commutative ring and A（R） be the set of ideals with non-zero annihilators. The annihilating-ideal graph of R is defined as the graph AG（R） with the vertex set A（R）＊ = A（R）／{（0）} and two distinct...Let R be a commutative ring and A（R） be the set of ideals with non-zero annihilators. The annihilating-ideal graph of R is defined as the graph AG（R） with the vertex set A（R）＊ = A（R）／{（0）} and two distinct vertices I and J are adjacent if and only if IJ = （0）. Here, we present some results on the clique number and the chromatic number of the annihilating-ideal graph of a commutative ring. It is shown that if R is an Artinian ring and w（AG（R）） = 2, then R is Gorenstein. Also, we investigate commutative rings whose annihilating-ideal graphs are complete or bipartite.展开更多
In this paper, we introduce some new definitions such as the U＊L＊ condition to describe the zero-divisor graph G = F（P） of a poser P, and give a new and quick proof to a main result in [2, 4]. By deleting a typica...In this paper, we introduce some new definitions such as the U＊L＊ condition to describe the zero-divisor graph G = F（P） of a poser P, and give a new and quick proof to a main result in [2, 4]. By deleting a typical vertex with least degree, we provide an algorithm for finding a maximum clique of a finite graph G. We study some properties of the zero-divisor graphs of posets concerning diameters and girths. We also provide stratified presentations of posets.展开更多
基金This research is supported partially by the National Natural Science Foundation of China(10371055).
文摘The circular clique number of a graph G is the maximum fractional k/d suchthat G_d^k admits a homomorphism to G. In this paper, we give some sufficient conditions for graphswhose circular clique number equal the clique number, we also characterize the K_(1,3)-free graphsand planar graphs with the desired property.
基金This research was supported by the National Natural Science Foundation of China(No.11801356,No.11401368,No.11971338)by the Natural Science Foundation of Shanghai(No.19ZR1424100).
文摘Let R be a commutative ring and Γ(R)be its zero-divisor graph.We completely determine the structure of all finite commutative rings whose zero-divisor graphs have clique number one,two,or three.Furthermore,if R■R1×R2×…×Rn(each Ri is local for i=1,2,3,...,n),we also give algebraic characterizations of the ring R when the clique number of Γ(R)is four.
基金This research was supported by the National Natural Science Foundation of China(No.11801356,No.11401368,No.11971338)by the Natural Science Foundation of Shanghai(No.19ZR1424100).
文摘We study the algebraic structure of rings R whose zero-divisor graph T(R)has clique number four.Furthermore,we give complete characterizations of all the finite commutative local rings with clique number 4.
基金partially supported by the Open Research Fund of Key Laboratory of Nonlinear Analysis&Applications(Central China Normal University),Ministry of Education,P.R.Chinathe Guiding Science and Technology Plan Project of Suqian City in 2023(No.Z2023130)partially supported by NSFC(No.12271234)。
文摘Given two ideals I and J of a commutative ring R,there are two extreme connections between I and J:I+J=R and I∩J={0}.For the former case,graphs whose vertices are defined as the proper ideals of R and that two vertices are adjacent if and only if their sum is the whole ring R are known as co-maximal ideal graphs.In this paper,we introduce a new kind of graph structure on R,called co-minimal ideal graph,according to the second case:Its vertices are the nonzero ideals of R and two vertices are adjacent if and only if their intersection is zero.Some important graph parameters(including girth,diameter,clique number and chromatic number)and graph structures(including tree and bipartite graph)of co-minimal ideal graphs over finite commutative rings are studied.In particular,we show that the co-maximal ideal graph and the co-minimal ideal graph over R are isomorphic if and only if the number of maximal ideals of R and the number of minimal ideals of R coincide.
基金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）.
基金Acknowledgements The authors thank the referees for their valuable comments. This work was partially supported by the National Natural Science Foundation of China （Grant Nos. 11331003, 11571180） and a Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘Let G and H be two induced subgraph isomorphic to conjectured that, for every tree function, depending only on T graphs. We say that G induces H if G has an H. A. Gyarfas and D. Sumner, independently, T, there exists a function fT, called binding with the property that every graph G with chromatic number fT（ω（G）） induces T. A. Gyarfas, E. Szemeedi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyarfas et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with co（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（14^r-1（r - 1）!） times. We extend the approach of A. Gyarfas and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott＇s upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（6^r-2） times.
基金Supported by the National Natural Science Foundation of China(No.10331020)
文摘Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved： 1. max {φ（G）： ｜V（G）｜ = 2n, κ（G）≤ k} = k[（2n - 3）!!], 2. max{φ（G）： ｜V（G）｜ = 2n,α（G） ≥ k} =[∏ i=0^k-1 （2n - k-i]（2n - 2k - 1）!!], 3. max{φ（G）： ｜V（G）｜=2n, χ（G） ≤ k} =φ（Tk,2n） Tk,2n is the Turán graph, that is a complete k-partitc graph on 2n vertices in which all parts are as equal in size as possible, 4. max{φ（G）： ｜V（G）｜ = 2n, cl（G） = 2} = n!, 5. max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥〉 2} = （2n - 2）（2n - 3）[（2n - 5）!!], max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥ 3} = （n - 1）^2[（2n - 5）!!].
文摘Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc（G）, is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that trc（G） = 3 if （n-12） ＋ 1 ≤ ｜E（G）｜≤ （n2） - 1, and trc（G） ≤ 6 if ｜E（G）｜≥ （n22） ＋2. Next, we investigate the total rainbow connection numbers of graphs G with ｜V（G）｜ = n, diam（G） ≥ 2, and clique number w（G） = n - s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31（2）： 313-320] is not completely correct, and we provide a complete result for this theorem.
基金supported by the National Natural Science Foundation of China(No.12101117)Natural Science Foundation of Jiangsu Province(No.BK20200344)。
文摘Let G be a graph.We useχ(G)andω(G)to denote the chromatic number and clique number of G respectively.A P_(5)is a path on 5 vertices,and an HVN is a K_(4)together with one more vertex which is adjacent to exactly two vertices of K_(4).Combining with some known result,in this paper we show that if G is(P_(5),HVN)-free,thenχ(G)≤max{min{16,ω(G)+3},ω(G)+1}.This upper bound is almost sharp.
基金supported by National Natural Science Foundation of China(Grant Nos.11271267 and 11371204)
文摘An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.
文摘Let R be a commutative ring and A（R） be the set of ideals with non-zero annihilators. The annihilating-ideal graph of R is defined as the graph AG（R） with the vertex set A（R）＊ = A（R）／{（0）} and two distinct vertices I and J are adjacent if and only if IJ = （0）. Here, we present some results on the clique number and the chromatic number of the annihilating-ideal graph of a commutative ring. It is shown that if R is an Artinian ring and w（AG（R）） = 2, then R is Gorenstein. Also, we investigate commutative rings whose annihilating-ideal graphs are complete or bipartite.
基金Supported by the National Natural Science Foundation of China （11271250）.Acknowledgements. The authors express their sincere thanks to the referees for the careful reading and suggestions which improved the exposition of the paper.
文摘In this paper, we introduce some new definitions such as the U＊L＊ condition to describe the zero-divisor graph G = F（P） of a poser P, and give a new and quick proof to a main result in [2, 4]. By deleting a typical vertex with least degree, we provide an algorithm for finding a maximum clique of a finite graph G. We study some properties of the zero-divisor graphs of posets concerning diameters and girths. We also provide stratified presentations of posets.
