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.展开更多
Let G be a graph and H be a set of subgraphs of G.An h-edge-coloring of G is H-polychromatic if every subgraph of G isomorphic to some element in H receives all h colors.The largest integer h,for which G admits an H-p...Let G be a graph and H be a set of subgraphs of G.An h-edge-coloring of G is H-polychromatic if every subgraph of G isomorphic to some element in H receives all h colors.The largest integer h,for which G admits an H-polychromatic h-edge-coloring,is called the H-polychromatic number of G and denoted by pH(G).In this paper,we prove that pk_(s,t)(K_(m,n))=[m+n-8-t+1/mn]for 2≤s<m,2≤t<n and max{m,n}<s+t,which extends a result of Zhang,Jiang and Zhang that pk_(n-1,n-1)(K_(n,n))=[3/n^(2)].展开更多
In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple set...In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple sets.The vertex-distinguishing E-total chromatic numbers of this kind of graph are determined.展开更多
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.展开更多
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).展开更多
Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of verte...Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.展开更多
Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges i...Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u） =fi C（v） for any two different vertices u and v of V（G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The ie iV., minimum number of colors required for a VDIET coloring of G is denoted by X,t[ 1, and it is called the VDIET chromatic number of G. We will give VDIET chromatic numbers for complete bipartite graph K4,n（n ≥ 4）, Kn,n （5 ≤ n ≤21） in this article.展开更多
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.展开更多
A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for ...A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.展开更多
In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2...In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2) n≤p km,(3)p kn-m≡p km-n ≡0(mod( p 2k -1 )) and (4) (p kn-m)(p km-n) ≡0(mod( p k -1)p k×(p 2k -1)(m+n)) .展开更多
Let Bn^k be the class of bipartite graphs with n vertices and k cut edges. The extremal graphs with the first and the second largest Laplacian spectral radius among all graphs in Bn^K are presented. The bounds of the ...Let Bn^k be the class of bipartite graphs with n vertices and k cut edges. The extremal graphs with the first and the second largest Laplacian spectral radius among all graphs in Bn^K are presented. The bounds of the Laplacian spectral radius of these extremal graphs are also obtained.展开更多
Let G =（V1,V2,E） be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B（G）,is defined to be n if G =Kn and min i∈{1,2}｜N（S）｜〈n min ｜N（S）｜/｜S｜otherwise.We call G b...Let G =（V1,V2,E） be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B（G）,is defined to be n if G =Kn and min i∈{1,2}｜N（S）｜〈n min ｜N（S）｜/｜S｜otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B（G） 〉 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows：Let 0 〈 c 〈 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n（n is large enough） vertices such that B（G） c and δ（G）（2-c）n/（3-c）＋2/3.Then G is bipancyclic.展开更多
The chromatically uniqueness of bipartite graphs K （m, n） - A（]A] = 2） was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condi...The chromatically uniqueness of bipartite graphs K （m, n） - A（]A] = 2） was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condition guaranteeing that K（ m, n） - A （ I A ] = 2） is chromatically unique were obtained. This covers and improves the former correlative results.展开更多
The Wiener index W（G） of a graph G is defined as the sum of distances between all pairs of vertices of the graph, Let G＊c, is the set of the complements of bipartite graphs with order n. In this paper, we character...The Wiener index W（G） of a graph G is defined as the sum of distances between all pairs of vertices of the graph, Let G＊c, is the set of the complements of bipartite graphs with order n. In this paper, we characterize the graphs with the maximum and second-maximum Wiener indices among all the graphs in G＊c, respectively.展开更多
With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleter...With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.展开更多
Cohesive subgraph search is a fundamental problem in bipartite graph analysis.Given integers k andℓ,a(k,ℓ)-biplex is a cohesive structure which requires each vertex to disconnect at most k orℓvertices in the other sid...Cohesive subgraph search is a fundamental problem in bipartite graph analysis.Given integers k andℓ,a(k,ℓ)-biplex is a cohesive structure which requires each vertex to disconnect at most k orℓvertices in the other side.Computing(k,ℓ)-biplexes has been a popular research topic in recent years and has various applications.However,most existing studies considered the problem of finding(k,ℓ)-biplex with the largest number of edges.In this paper,we instead consider another variant and focus on the maximum vertex(k,ℓ)-biplex problem which aims to search for a(k,ℓ)-biplex with the maximum cardinality.We first show that this problem is Non-deterministic Polynomial-time hard(NP-hard)for any positive integers k andℓwhile max{k,ℓ}is at least 3.Guided by this negative result,we design an efficient branch-and-bound algorithm with a novel framework.In particular,we introduce a branching strategy based on whether there is a pivot in the current set,with which our proposed algorithm has the time complexity ofγ^(n)n^(O(1)),whereγ<2.In addition,we also apply multiple speed-up techniques and various pruning strategies.Finally,we conduct extensive experiments on various real datasets which demonstrate the efficiency of our proposed algorithm in terms of running time.展开更多
Given a distribution of pebbles on the vertices of a connected graph G,a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex.Rubbling is a version of pebbling where a...Given a distribution of pebbles on the vertices of a connected graph G,a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex.Rubbling is a version of pebbling where an additional move is allowed.In this new move,one pebble each is removed at vertices u and w that are adjacent to a vertex v,and an extra pebble is added at vertex v.The rubbling number of G,denoted byρ(G),is the smallest number m such that for every distribution of m pebbles on G and every vertex v,at least one pebble can be moved to v by a sequence of rubbling moves.The optimal rubbling number of G,denoted byρopt(G),is the smallest number k such that for some distribution of k pebbles on G,one pebble can be moved to any vertex of G.In this paper,we determineρ(G)for a non-complete bipartite graph G∈B(s,t)with,give an upper bound ofρ(G)for G∈B(s,t)withδ(G)≥[2s+1/3],give an upper bound ofρ(G)for G∈B(s,t),withδ(G)≥[s+1/2],and also obtainρopt(G)for a non-complete bipartite graph G∈B(s,t)withδ(G)≥[s+1/2],where B(s,t)is the set of all connected bipartite graphs with partite sets of size s and t(s≥t)andδ(G)is the minimum degree of G.展开更多
A linear forest is a graph consisting of paths.In this paper,the authors determine the maximum number of edges in an(m,n)-bipartite graph which does not contain a linear forest consisting of paths on at least four ver...A linear forest is a graph consisting of paths.In this paper,the authors determine the maximum number of edges in an(m,n)-bipartite graph which does not contain a linear forest consisting of paths on at least four vertices for n≥m when m is sufficiently large.展开更多
H. Wang considered the minimum degrees condition that G has largevertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjointcycles in bipartite graphs in this paper. We prove t...H. Wang considered the minimum degrees condition that G has largevertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjointcycles in bipartite graphs in this paper. We prove the following result: Let m ≥ 3, n ≥ 2 and k≥ 1 be three integers. Let G = (V_1,V_2;E) be a bipartite graph with |V_1| = |V_2| = n ≥ 2k+1.展开更多
For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s andt such that 2≤ s ≤ t, 0≤ m-s ≤ n-t, andre＋n≤ 2s＋t-1, we prove that if G has at least mn- （2（m - s） ＋...For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s andt such that 2≤ s ≤ t, 0≤ m-s ≤ n-t, andre＋n≤ 2s＋t-1, we prove that if G has at least mn- （2（m - s） ＋ n - t） edges then it contains a subdivision of the complete bipartite K（s,t） with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn- （2（m - s） ＋ n - t ＋ 1） edges for this topological Turan type problem.展开更多
基金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(Grant No.12071265)the Natural Science Foundation of Shandong Province(Grant No.ZR2025MS11)。
文摘Let G be a graph and H be a set of subgraphs of G.An h-edge-coloring of G is H-polychromatic if every subgraph of G isomorphic to some element in H receives all h colors.The largest integer h,for which G admits an H-polychromatic h-edge-coloring,is called the H-polychromatic number of G and denoted by pH(G).In this paper,we prove that pk_(s,t)(K_(m,n))=[m+n-8-t+1/mn]for 2≤s<m,2≤t<n and max{m,n}<s+t,which extends a result of Zhang,Jiang and Zhang that pk_(n-1,n-1)(K_(n,n))=[3/n^(2)].
基金Supported by the National Natural Science Foundation of China (11761064)。
文摘In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple sets.The vertex-distinguishing E-total chromatic numbers of this kind of graph are determined.
文摘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.
文摘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).
基金Supported by the National Natural Science Foundation of China（61163037, 61163054, 11261046, 61363060）
文摘Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 6116303761163054)+2 种基金the Scientific Research Project of Northwest Normal University (No. nwnu-kjcxgc-03-61)the Natural Foudation Project of Ningxia (No. NZ1154)the Scientific Research Foudation Project of Ningxia University (No. (E):ndzr10-7)
文摘Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u） =fi C（v） for any two different vertices u and v of V（G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The ie iV., minimum number of colors required for a VDIET coloring of G is denoted by X,t[ 1, and it is called the VDIET chromatic number of G. We will give VDIET chromatic numbers for complete bipartite graph K4,n（n ≥ 4）, Kn,n （5 ≤ n ≤21） in this article.
基金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.
基金The NSF(11271365)of Chinathe NSF(BK20151117)of Jiangsu Province
文摘A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.
文摘In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2) n≤p km,(3)p kn-m≡p km-n ≡0(mod( p 2k -1 )) and (4) (p kn-m)(p km-n) ≡0(mod( p k -1)p k×(p 2k -1)(m+n)) .
基金Fundamental Research Funds for the Central Universities of China(No. 11D10902,No. 11D10913)
文摘Let Bn^k be the class of bipartite graphs with n vertices and k cut edges. The extremal graphs with the first and the second largest Laplacian spectral radius among all graphs in Bn^K are presented. The bounds of the Laplacian spectral radius of these extremal graphs are also obtained.
基金Supported by the Scientific Research Fund of Hubei Provincial Education Department(B2015021)
文摘Let G =（V1,V2,E） be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B（G）,is defined to be n if G =Kn and min i∈{1,2}｜N（S）｜〈n min ｜N（S）｜/｜S｜otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B（G） 〉 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows：Let 0 〈 c 〈 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n（n is large enough） vertices such that B（G） c and δ（G）（2-c）n/（3-c）＋2/3.Then G is bipancyclic.
基金Supported by the Natural Science Foundation of Jiangxi , China (No.0511006)
文摘The chromatically uniqueness of bipartite graphs K （m, n） - A（]A] = 2） was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condition guaranteeing that K（ m, n） - A （ I A ] = 2） is chromatically unique were obtained. This covers and improves the former correlative results.
文摘The Wiener index W（G） of a graph G is defined as the sum of distances between all pairs of vertices of the graph, Let G＊c, is the set of the complements of bipartite graphs with order n. In this paper, we characterize the graphs with the maximum and second-maximum Wiener indices among all the graphs in G＊c, respectively.
基金Natural Science Foundation of Fujian, China (No.S0650011)
文摘With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.
基金partially supported by the Shenzhen Science and Technology Program(No.RCBS20210609103900003)Department of Education of Guangdong Province(Nos.2022KTSCX214,2023KTSCX226,and 2023KQNCX152)National Natural Science Foundation of China(No.62102117).
文摘Cohesive subgraph search is a fundamental problem in bipartite graph analysis.Given integers k andℓ,a(k,ℓ)-biplex is a cohesive structure which requires each vertex to disconnect at most k orℓvertices in the other side.Computing(k,ℓ)-biplexes has been a popular research topic in recent years and has various applications.However,most existing studies considered the problem of finding(k,ℓ)-biplex with the largest number of edges.In this paper,we instead consider another variant and focus on the maximum vertex(k,ℓ)-biplex problem which aims to search for a(k,ℓ)-biplex with the maximum cardinality.We first show that this problem is Non-deterministic Polynomial-time hard(NP-hard)for any positive integers k andℓwhile max{k,ℓ}is at least 3.Guided by this negative result,we design an efficient branch-and-bound algorithm with a novel framework.In particular,we introduce a branching strategy based on whether there is a pivot in the current set,with which our proposed algorithm has the time complexity ofγ^(n)n^(O(1)),whereγ<2.In addition,we also apply multiple speed-up techniques and various pruning strategies.Finally,we conduct extensive experiments on various real datasets which demonstrate the efficiency of our proposed algorithm in terms of running time.
基金supported by National Natural Science Foundation of China(Nos.11461017,12361068)Hainan Provincial Natural Science Foundation of China(No.125RC628)。
文摘Given a distribution of pebbles on the vertices of a connected graph G,a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex.Rubbling is a version of pebbling where an additional move is allowed.In this new move,one pebble each is removed at vertices u and w that are adjacent to a vertex v,and an extra pebble is added at vertex v.The rubbling number of G,denoted byρ(G),is the smallest number m such that for every distribution of m pebbles on G and every vertex v,at least one pebble can be moved to v by a sequence of rubbling moves.The optimal rubbling number of G,denoted byρopt(G),is the smallest number k such that for some distribution of k pebbles on G,one pebble can be moved to any vertex of G.In this paper,we determineρ(G)for a non-complete bipartite graph G∈B(s,t)with,give an upper bound ofρ(G)for G∈B(s,t)withδ(G)≥[2s+1/3],give an upper bound ofρ(G)for G∈B(s,t),withδ(G)≥[s+1/2],and also obtainρopt(G)for a non-complete bipartite graph G∈B(s,t)withδ(G)≥[s+1/2],where B(s,t)is the set of all connected bipartite graphs with partite sets of size s and t(s≥t)andδ(G)is the minimum degree of G.
基金supported by the National Natural Science Foundation of China(Nos.12125106,12271169,12331014)National Key R and D Program of China(No.2020YFA0713100)+1 种基金Anhui Initiative in Quantum Information Technologies(No.AHY150200)Science and Technology Commission of Shanghai Municipality(No.22DZ2229014)。
文摘A linear forest is a graph consisting of paths.In this paper,the authors determine the maximum number of edges in an(m,n)-bipartite graph which does not contain a linear forest consisting of paths on at least four vertices for n≥m when m is sufficiently large.
基金This research is supported by the National Natural Science Foundation of China(60172003) and NSF of Shandong Province(Z2000A02).
文摘H. Wang considered the minimum degrees condition that G has largevertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjointcycles in bipartite graphs in this paper. We prove the following result: Let m ≥ 3, n ≥ 2 and k≥ 1 be three integers. Let G = (V_1,V_2;E) be a bipartite graph with |V_1| = |V_2| = n ≥ 2k+1.
文摘For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s andt such that 2≤ s ≤ t, 0≤ m-s ≤ n-t, andre＋n≤ 2s＋t-1, we prove that if G has at least mn- （2（m - s） ＋ n - t） edges then it contains a subdivision of the complete bipartite K（s,t） with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn- （2（m - s） ＋ n - t ＋ 1） edges for this topological Turan type problem.
