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.展开更多
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.展开更多
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.展开更多
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 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.展开更多
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring u...An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.展开更多
An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get disti...An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get distinct colors if and only if they conflict each other,i.e.,(i)u=v,(ii)uv is e or f,or(iii)there is a vertex w such that uw=e and vw=f.The minimum number of colors used among all conflict-free incidence colorings of a graph is the conflict-free incidence chromatic number.A graph is outer-1-planar if it can be drawn in the plane so that vertices are on the outer-boundary and each edge is crossed at most once.In this paper,we show that the conflict-free incidence chromatic number of an outer-1-planar graph with maximum degree△is either 2△or 2△+1 unless the graph is a cycle on three vertices,and moreover,all outer-1-planar graphs with conflict-free incidence chromatic number 2△or 2△+1 are completely characterized.An efficient algorithm for constructing an optimal conflict-free incidence coloring of a connected outer-1-planar graph is given.展开更多
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.展开更多
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.展开更多
基金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.
文摘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.
文摘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.
文摘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 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.
基金Research supported by the National Natural Science Foundation of China (No.12031018)Research supported by the National Natural Science Foundation of China (No.12071048)+3 种基金Research supported by the National Natural Science Foundation of China(No.12071351)Science and Technology Commission of Shanghai Municipality (No.18dz2271000)Doctoral Scientific Research Foundation of Weifang University (No.2021BS01)Natural Science Foundation of Shandong Province (No.ZR2022MA060)。
文摘An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.
基金supported by the Research Funds for the Central Universities(No.QTZX22053)the National Natural Science Foundation of China(No.11871055)。
文摘An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get distinct colors if and only if they conflict each other,i.e.,(i)u=v,(ii)uv is e or f,or(iii)there is a vertex w such that uw=e and vw=f.The minimum number of colors used among all conflict-free incidence colorings of a graph is the conflict-free incidence chromatic number.A graph is outer-1-planar if it can be drawn in the plane so that vertices are on the outer-boundary and each edge is crossed at most once.In this paper,we show that the conflict-free incidence chromatic number of an outer-1-planar graph with maximum degree△is either 2△or 2△+1 unless the graph is a cycle on three vertices,and moreover,all outer-1-planar graphs with conflict-free incidence chromatic number 2△or 2△+1 are completely characterized.An efficient algorithm for constructing an optimal conflict-free incidence coloring of a connected outer-1-planar graph is given.
文摘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.
文摘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.
基金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)
