This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be i...This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be induced.展开更多
Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n...Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.展开更多
The linear relationship between fractal dimensions of a type of generalized Weierstrass functions and the order of their fractional calculus has been proved. The graphs and numerical results given here further indicat...The linear relationship between fractal dimensions of a type of generalized Weierstrass functions and the order of their fractional calculus has been proved. The graphs and numerical results given here further indicate the corresponding relationship.展开更多
We consider the block matrices and 3-dimensional graph manifolds associated with a special type of tree graphs. We demonstrate that the linking matrices of these graph manifolds coincide with the reduced matrices obta...We consider the block matrices and 3-dimensional graph manifolds associated with a special type of tree graphs. We demonstrate that the linking matrices of these graph manifolds coincide with the reduced matrices obtained from the Laplacian block matrices by means of Gauss partial diagonalization procedure described explicitly by W. Neumann. The linking matrix is an important topological invariant of a graph manifold which is possible to interpret as a matrix of coupling constants of gauge interaction in Kaluza-Klein approach, where 3-dimensional graph manifold plays the role of internal space in topological 7-dimensional BF theory. The Gauss-Neumann method gives us a simple algorithm to calculate the linking matrices of graph manifolds and thus the coupling constants matrices.展开更多
We present a new algorithm for the fast expansion of rational numbers into continued fractions. This algorithm permits to compute the complete set of integer Euler numbers of the sophisticate tree graph manifolds, whi...We present a new algorithm for the fast expansion of rational numbers into continued fractions. This algorithm permits to compute the complete set of integer Euler numbers of the sophisticate tree graph manifolds, which we used to simulate the coupling constant hierarchy for the universe with five fundamental interactions. Moreover, we can explicitly compute the integer Laplacian block matrix associated with any tree plumbing graph. This matrix coincides up to sign with the integer linking matrix (the main topological invariant) of the graph manifold corresponding to the plumbing graph. The need for a special algorithm appeared during computations of these topological invariants of complicated graph manifolds since there emerged a set of special rational numbers (fractions) with huge numerators and denominators;for these rational numbers, the ordinary methods of expansion in continued fraction became unusable.展开更多
A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p≥5,every planar graph of girth p without cycles of length from p+1 to p(p-2)is Cp-colorable(that is,it admits a homomorphism t...A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p≥5,every planar graph of girth p without cycles of length from p+1 to p(p-2)is Cp-colorable(that is,it admits a homomorphism to the odd cycle Cp).The assumption of p≥5 being prime number is necessary,and this conjecture implies a special case of Jaeger’s Conjecture that every planar graph of girth 2p-2 is Cp-colorable for prime p≥5.In this paper,combining our previous results,we show the fractional coloring version of this conjecture is true.Particularly,the p=5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.展开更多
Let h:E(G)→[0,1]be a function.If a≤∑e∋xh(e)≤b holds for each x∈V(G),then we call G[Fh]a fractional[a,b]-factor of G with indicator function h,where Fh={e:e∈E(G),h(e)>0}.A graph G is called a fractional[a,b]-c...Let h:E(G)→[0,1]be a function.If a≤∑e∋xh(e)≤b holds for each x∈V(G),then we call G[Fh]a fractional[a,b]-factor of G with indicator function h,where Fh={e:e∈E(G),h(e)>0}.A graph G is called a fractional[a,b]-covered graph if for every edge e of G,there is a fractional[a,b]-factor G[Fh]with h(e)=1.Zhou,Xu and Sun[S.Zhou,Y.Xu,Z.Sun,Degree conditions for fractional(a,b,k)-critical covered graphs,Information Processing Letters 152(2019)105838]defined the concept of a fractional(a,b,k)-critical covered graph,i.e.,for every vertex subset Q with|Q|=k of G,G−Q is a fractional[a,b]-covered graph.In this article,we study the problem of a fractional(2,b,k)-critical covered graph,and verify that a graph G withδ(G)≥3+k is a fractional(2,b,k)-critical covered graph if its toughness t(G)≥1+1b+k2b,where b and k are two nonnegative integers with b≥2+k2.展开更多
The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, ...The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.展开更多
In computer networks, toughness is an important parameter which is used to measure the vulnerability of the network. Zhou et al. obtains a toughness condition for a graph to be fractional(κ, m)-deleted and presents a...In computer networks, toughness is an important parameter which is used to measure the vulnerability of the network. Zhou et al. obtains a toughness condition for a graph to be fractional(κ, m)-deleted and presents an example to show the sharpness of the toughness bound. In this paper, we remark that the previous example does not work and inspired by this fact, we present a new toughness condition for fractional(κ, m)-deleted graphs improving the existing one. Finally, we state an open problem.展开更多
Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-criti...Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-critical graphs. Then using the result, we prove that G is all fractional （a, b, k）-critical if δ（G） ≥ （r-1）b2/a ＋k and ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn＋ak/a＋b for any independent subset {xl, x2, .., xr} in G. Furthermore, it is shown that the lower bound on the condition ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn=ak/ a＋b is best possible in some sense, and it is an extension of Lu＇s previous result.展开更多
Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉（a＋2 b）（r（a＋b）-2）/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ（G）≥bn/a...Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉（a＋2 b）（r（a＋b）-2）/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ（G）≥bn/a＋2 b＋a（r-1）and ｜NG（x1） ∪ NG（x2） ∪…∪ NG（xr）｜ ≥（a＋b）n/（a＋2 b） for any independent subset {x1,x2,…,xr} in G. It is a generalization of Zhou et al.＇s previous result [Discussiones Mathematicae Graph Theory, 36： 409-418（2016）]in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.展开更多
Let G be a graph, and k a positive integer. A graph G is fractional independent-set-deletable k-factor-critical(in short, fractional ID-k-factor-critical) if G-I has a fractional k-factor for every independent set I o...Let G be a graph, and k a positive integer. A graph G is fractional independent-set-deletable k-factor-critical(in short, fractional ID-k-factor-critical) if G-I has a fractional k-factor for every independent set I of G. In this paper, we present a sufficient condition for a graph to be fractional ID-k-factor-critical,depending on the minimum degree and the neighborhoods of independent sets. Furthermore, it is shown that this result in this paper is best possible in some sense.展开更多
基金This work is supported by NNSF of ChinaRFDP of Higher Education
文摘This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be induced.
文摘Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.
文摘The linear relationship between fractal dimensions of a type of generalized Weierstrass functions and the order of their fractional calculus has been proved. The graphs and numerical results given here further indicate the corresponding relationship.
文摘We consider the block matrices and 3-dimensional graph manifolds associated with a special type of tree graphs. We demonstrate that the linking matrices of these graph manifolds coincide with the reduced matrices obtained from the Laplacian block matrices by means of Gauss partial diagonalization procedure described explicitly by W. Neumann. The linking matrix is an important topological invariant of a graph manifold which is possible to interpret as a matrix of coupling constants of gauge interaction in Kaluza-Klein approach, where 3-dimensional graph manifold plays the role of internal space in topological 7-dimensional BF theory. The Gauss-Neumann method gives us a simple algorithm to calculate the linking matrices of graph manifolds and thus the coupling constants matrices.
文摘We present a new algorithm for the fast expansion of rational numbers into continued fractions. This algorithm permits to compute the complete set of integer Euler numbers of the sophisticate tree graph manifolds, which we used to simulate the coupling constant hierarchy for the universe with five fundamental interactions. Moreover, we can explicitly compute the integer Laplacian block matrix associated with any tree plumbing graph. This matrix coincides up to sign with the integer linking matrix (the main topological invariant) of the graph manifold corresponding to the plumbing graph. The need for a special algorithm appeared during computations of these topological invariants of complicated graph manifolds since there emerged a set of special rational numbers (fractions) with huge numerators and denominators;for these rational numbers, the ordinary methods of expansion in continued fraction became unusable.
基金partially supported by the National Natural Science Foundation of China(Grant No.11971196)Hubei Provincial Science and Technology Innovation Base(Platform)Special Project 2020DFH002+1 种基金the second author was partially supported by the National Natural Science Foundation of China(Grant Nos.11901318,12131013)the Young Elite Scientists Sponsorship Program by Tianjin(Grant No.TJSQNTJ-2020-09)。
文摘A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p≥5,every planar graph of girth p without cycles of length from p+1 to p(p-2)is Cp-colorable(that is,it admits a homomorphism to the odd cycle Cp).The assumption of p≥5 being prime number is necessary,and this conjecture implies a special case of Jaeger’s Conjecture that every planar graph of girth 2p-2 is Cp-colorable for prime p≥5.In this paper,combining our previous results,we show the fractional coloring version of this conjecture is true.Particularly,the p=5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.
文摘Let h:E(G)→[0,1]be a function.If a≤∑e∋xh(e)≤b holds for each x∈V(G),then we call G[Fh]a fractional[a,b]-factor of G with indicator function h,where Fh={e:e∈E(G),h(e)>0}.A graph G is called a fractional[a,b]-covered graph if for every edge e of G,there is a fractional[a,b]-factor G[Fh]with h(e)=1.Zhou,Xu and Sun[S.Zhou,Y.Xu,Z.Sun,Degree conditions for fractional(a,b,k)-critical covered graphs,Information Processing Letters 152(2019)105838]defined the concept of a fractional(a,b,k)-critical covered graph,i.e.,for every vertex subset Q with|Q|=k of G,G−Q is a fractional[a,b]-covered graph.In this article,we study the problem of a fractional(2,b,k)-critical covered graph,and verify that a graph G withδ(G)≥3+k is a fractional(2,b,k)-critical covered graph if its toughness t(G)≥1+1b+k2b,where b and k are two nonnegative integers with b≥2+k2.
文摘The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.
基金partially supported by MINECO(Grant No.MTM2014–51891–P and Fundación Séneca de la Región de Murcia 19219/PI/14)National Science Foundation of China(Grant No.11401519)
文摘In computer networks, toughness is an important parameter which is used to measure the vulnerability of the network. Zhou et al. obtains a toughness condition for a graph to be fractional(κ, m)-deleted and presents an example to show the sharpness of the toughness bound. In this paper, we remark that the previous example does not work and inspired by this fact, we present a new toughness condition for fractional(κ, m)-deleted graphs improving the existing one. Finally, we state an open problem.
基金Supported by National Natural Science Foundation of China(Grant No.11371009)
文摘Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-critical graphs. Then using the result, we prove that G is all fractional （a, b, k）-critical if δ（G） ≥ （r-1）b2/a ＋k and ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn＋ak/a＋b for any independent subset {xl, x2, .., xr} in G. Furthermore, it is shown that the lower bound on the condition ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn=ak/ a＋b is best possible in some sense, and it is an extension of Lu＇s previous result.
基金supported by the National Natural Science Foundation of China(Nos.11371052,11731002)the Fundamental Research Funds for the Central Universities(Nos.2016JBM071,2016JBZ012)the 111 Project of China(B16002)
文摘Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉（a＋2 b）（r（a＋b）-2）/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ（G）≥bn/a＋2 b＋a（r-1）and ｜NG（x1） ∪ NG（x2） ∪…∪ NG（xr）｜ ≥（a＋b）n/（a＋2 b） for any independent subset {x1,x2,…,xr} in G. It is a generalization of Zhou et al.＇s previous result [Discussiones Mathematicae Graph Theory, 36： 409-418（2016）]in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.
基金supported by the National Natural Science Foundation of China(Grant No.11371009,11501256,61503160)Six Big Talent Peak of Jiangsu Province(Grant No.JY–022)+3 种基金333 Project of Jiangsu Provincethe National Social Science Foundation of China(Grant No.14AGL001)the Natural Science Foundation of Xinjiang Province of China(Grant No.2015211A003)the Natural Science Foundation of the Higher Education Institutions of Jiangsu Province(Grant No.14KJD110002)
文摘Let G be a graph, and k a positive integer. A graph G is fractional independent-set-deletable k-factor-critical(in short, fractional ID-k-factor-critical) if G-I has a fractional k-factor for every independent set I of G. In this paper, we present a sufficient condition for a graph to be fractional ID-k-factor-critical,depending on the minimum degree and the neighborhoods of independent sets. Furthermore, it is shown that this result in this paper is best possible in some sense.
