Perfect 1-k Matchings of Bipartite Graphs

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.

2-Factors with a Few Components in Balanced Bipartite Graphs

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).

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K 7,n when7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.

ORTHOGONAL (g,f)-FACTORIZAFIONS OF BIPARTITE GRAPHS

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.

K_(1,p)~k-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS

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)) .

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

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.

Two conditions for a bipartite graph to be a k-deleted graph

A k-regular spanning subgraph of graph G is called a k-factor of G. Graph G is called a k-deleted graph if G-e has a k-factor for each edge e. A graph G=(X,Y) with bipartition (X,Y) is called a bipartite graph if every edge of G has one endpoint in X and the other in Y.It is proved that a bipartite graph G=(X,Y) with X=Y is a k-deleted graph if and only if kS≤r 1+2r 2+...+k(r k+...+r Δ)-ε(S) for all SX. Using this result we give a sufficient neighborhood condition for a bipartite to be a k-deleted graph.

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

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.

MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS

The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

Bipartite Graphs with the First and Second Largest Laplacian Spectral Radius

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.

A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs

The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.

Neighborhood Complex of Bipartite Graph

In this paper the structure of neighborhood complex of a bipartite graph is discussed, the concept of dusl complex is introduced, the main result that a pair of dual complexes is exactly the neighborhood complex or a connected bipartite graph is proved.

The Signless Laplacian Spectral Radius of Some Special Bipartite Graphs

This paper mainly researches on the signless laplacian spectral radius of bipartite graphs Dr(m1,m2;n1,n2). We consider how the signless laplacian spectral radius of Dr(m1,m2;n1,n2)?changes under some special cases. As application, we give two upper bounds on the signless laplacian spectral radius of Dr(m1,m2;n1,n2), and determine the graphs that obtain the upper bounds.

The Symbolic OBDD Algorithm for Finding Optimal Semi-matching in Bipartite Graphs

The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large graphs.

On the Wiener Index of the Complements of Bipartite Graphs

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.

Rainbow Matchings in Properly Colored Bipartite Graphs

Let G be a properly colored bipartite graph. A rainbow matching of G is such a matching in which no two edges have the same color. Let G be a properly colored bipartite graph with bipartition (X,Y) and . We show that if , then G has a rainbow coloring of size at least .

Cycle Multiplicity of Total Graph of Complete Bipartite Graph

Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].

The Further Results of the Chromatic Uniqueness of Certain Bipartite Graphs K(m, n)-A

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.

The Chromatic Uniqueness of Bipartite Graphs K(m,n)-A with |A|=2

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.

Solving the Maximum Matching Problem on Bipartite Star123-Free Graphs in Linear Time

The bipartite Star123-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star123-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star123, P7-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.