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.展开更多
We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices...We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices u and w,|φ(u)-φ(w)|≥p when they are adjacent,and|φ(u)-φ(w)|≥1 when they are at distance 2.In this paper,we proved that:(1)for every planar graph with g(G)≥5 andΔ≥5,G is 12-L(1,1)-choosable.(2)for every planar graph with g(G)≥6 andΔ≥15,G is(Δ+6)-L(2,1)-choosable.展开更多
In this paper, a necessary condition for a bipartite graph λK m,n to be K 1,k factorizable and a sufficient condition for kK m,n to have a K 1,k factorization whenever k is a prime numbe...In this paper, a necessary condition for a bipartite graph λK m,n to be K 1,k factorizable and a sufficient condition for kK m,n to have a K 1,k factorization whenever k is a prime number are given.展开更多
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 G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G ...Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.展开更多
An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference betw...An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.展开更多
Let G be a graph of order n, and let a and b be integers, such that 1 ≤ a b. Let H be a subgraph of G with m(≤b) edges, and δ(G) be the minimum degree. We prove that G has a [a,b]-factor containing all edges of H i...Let G be a graph of order n, and let a and b be integers, such that 1 ≤ a b. Let H be a subgraph of G with m(≤b) edges, and δ(G) be the minimum degree. We prove that G has a [a,b]-factor containing all edges of H if , , and when a ≤ 2, .展开更多
Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is inc...Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.展开更多
A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))...A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))|≥1 if the edges e_(1)and e_(2)are adjacent,and|c(u)-c(e)|≥2 if the vertex u is incident to the edge e.A graph G is k-(2,1)-Total choosable if G is L-(2,1)-Total labeling for every list assignment L provided that|L(x)|=k,x∈V(G)∪E(G).The(2,1)-Total choice number of G,denoted by C_(2,1)^T(G),is the minimum k such that G is k-(2,1)-Total choosable.In this paper,we prove that if G is a planar graph with△(G)≥11,then C_(2,1)^T(G)≤△+4.展开更多
A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this pape...A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.展开更多
In this study, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on weighted graphs. Then, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on i...In this study, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on weighted graphs. Then, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on interval weighted graphs. Their behaviors are investigated under some graph operations by using these definitions.展开更多
The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-F...The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-Flipper operation preserves the regularity and weak connectivity of multi-digraphs.The generalized 1-Flipper operation is proved to be symmetric.Moreover,it is presented that a series of random generalized 1-Flipper operations eventually lead to a uniform probability distribution over all connected d-regular multi-digraphs without loops.展开更多
In this paper, a sufficient condition for a balanced bipartite graph to contain a 2-factor F is given. We show that every balanced bipartite graph of order 2n (n≥6)and e(G)>n2−2n+4contains a 2-factor with k compon...In this paper, a sufficient condition for a balanced bipartite graph to contain a 2-factor F is given. We show that every balanced bipartite graph of order 2n (n≥6)and e(G)>n2−2n+4contains a 2-factor with k components, 2d1-cycle, ⋯, 2dk-cycle, if one of the following is satisfied: (1) k=2, δ(G)≥2and d1−2≥d2≥2;(2) k=3, δ(G)≥d3+2and d1−2≥d2≥d3≥4. In particular, this extends one result of Moon and Moser in 1963 under condition (1).展开更多
The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that ...The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.展开更多
We report a bioinformatic analysis of the datasets of sequences of all ten genes from the 2009 H1N1 influenza A pandemic in the state of Wisconsin. The gene with the greatest summed information entropy was found to be...We report a bioinformatic analysis of the datasets of sequences of all ten genes from the 2009 H1N1 influenza A pandemic in the state of Wisconsin. The gene with the greatest summed information entropy was found to be the hemagglutinin (HA) gene. Based upon the viral ID identifier of the HA gene sequence, the sequences of all of the genes were sorted into two subsets, depending upon whether the nucleotide occupying the position of maximum entropy, position 658 of the HA sequence, was either A or U. It was found that the information entropy (H) distributions of subsets differed significantly from each other, from H distributions of randomly generated subsets and from the H distributions of the complete datasets of each gene. Mutual information (MI) values facilitated identification of nine nucleotide positions, distributed over seven of the influenza genes, at which the nucleotide subsets were disjoint, or almost disjoint. Nucleotide frequencies at these nine positions were used to compute mutual information values that subsequently served as weighting factors for edges in a graph net-work. Seven of the nucleotide positions in the graph network are sites of synonymous mutations. Three of these sites of synonymous mutation are within a single gene, the M1 gene, which occupied the position of greatest graph centrality. It is proposed that these bioinformatic and network graph results may reflect alterations in M1-mediated viral packaging and exteriorization, known to be susceptible to synonymous mutations.展开更多
基金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.
文摘We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices u and w,|φ(u)-φ(w)|≥p when they are adjacent,and|φ(u)-φ(w)|≥1 when they are at distance 2.In this paper,we proved that:(1)for every planar graph with g(G)≥5 andΔ≥5,G is 12-L(1,1)-choosable.(2)for every planar graph with g(G)≥6 andΔ≥15,G is(Δ+6)-L(2,1)-choosable.
文摘In this paper, a necessary condition for a bipartite graph λK m,n to be K 1,k factorizable and a sufficient condition for kK m,n to have a K 1,k factorization whenever k is a prime number are given.
基金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.
基金This work was supported by NNSF. RFDP and NNSF of shandong province(Z2000A02 ).
文摘Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.
文摘An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.
文摘Let G be a graph of order n, and let a and b be integers, such that 1 ≤ a b. Let H be a subgraph of G with m(≤b) edges, and δ(G) be the minimum degree. We prove that G has a [a,b]-factor containing all edges of H if , , and when a ≤ 2, .
文摘Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.
基金Supported by the National Natural Science Foundation of China(Grant No.12071265)the Natural Science Foundation of Shandong Province(Grant No.ZR2019MA032)。
文摘A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))|≥1 if the edges e_(1)and e_(2)are adjacent,and|c(u)-c(e)|≥2 if the vertex u is incident to the edge e.A graph G is k-(2,1)-Total choosable if G is L-(2,1)-Total labeling for every list assignment L provided that|L(x)|=k,x∈V(G)∪E(G).The(2,1)-Total choice number of G,denoted by C_(2,1)^T(G),is the minimum k such that G is k-(2,1)-Total choosable.In this paper,we prove that if G is a planar graph with△(G)≥11,then C_(2,1)^T(G)≤△+4.
文摘A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.
文摘In this study, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on weighted graphs. Then, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on interval weighted graphs. Their behaviors are investigated under some graph operations by using these definitions.
基金National Natural Science Foundation of China(No.11671258)。
文摘The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-Flipper operation preserves the regularity and weak connectivity of multi-digraphs.The generalized 1-Flipper operation is proved to be symmetric.Moreover,it is presented that a series of random generalized 1-Flipper operations eventually lead to a uniform probability distribution over all connected d-regular multi-digraphs without loops.
文摘In this paper, a sufficient condition for a balanced bipartite graph to contain a 2-factor F is given. We show that every balanced bipartite graph of order 2n (n≥6)and e(G)>n2−2n+4contains a 2-factor with k components, 2d1-cycle, ⋯, 2dk-cycle, if one of the following is satisfied: (1) k=2, δ(G)≥2and d1−2≥d2≥2;(2) k=3, δ(G)≥d3+2and d1−2≥d2≥d3≥4. In particular, this extends one result of Moon and Moser in 1963 under condition (1).
文摘The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.
文摘We report a bioinformatic analysis of the datasets of sequences of all ten genes from the 2009 H1N1 influenza A pandemic in the state of Wisconsin. The gene with the greatest summed information entropy was found to be the hemagglutinin (HA) gene. Based upon the viral ID identifier of the HA gene sequence, the sequences of all of the genes were sorted into two subsets, depending upon whether the nucleotide occupying the position of maximum entropy, position 658 of the HA sequence, was either A or U. It was found that the information entropy (H) distributions of subsets differed significantly from each other, from H distributions of randomly generated subsets and from the H distributions of the complete datasets of each gene. Mutual information (MI) values facilitated identification of nine nucleotide positions, distributed over seven of the influenza genes, at which the nucleotide subsets were disjoint, or almost disjoint. Nucleotide frequencies at these nine positions were used to compute mutual information values that subsequently served as weighting factors for edges in a graph net-work. Seven of the nucleotide positions in the graph network are sites of synonymous mutations. Three of these sites of synonymous mutation are within a single gene, the M1 gene, which occupied the position of greatest graph centrality. It is proposed that these bioinformatic and network graph results may reflect alterations in M1-mediated viral packaging and exteriorization, known to be susceptible to synonymous mutations.
基金National Natural Science Foundation of China(10971121,11101243,61070230)The Research Fund for the Doctoral Program of Higher Education(20100131120017) Graduate Independent Innovation Foundation of Shandong University(yzc10040)
