An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λp,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λp,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal. 相似文献
Let Km,nbe a complete bipartite graph with two partite sets having m and n vertices, respectively. A Kp,q-factorization of Km,n is a set of edge-disjoint Kp,q-factors of Km,n which partition the set of edges of Km,n. When p = 1 and q is a prime number, Wang, in his paper “On K1,k-factorizations of a complete bipartite graph” (Discrete Math, 1994, 126: 359—364), investigated the K1,q-factorization of Km,nand gave a sufficient condition for such a factorization to exist. In the paper “K1,k-factorizations of complete bipartite graphs” (Discrete Math, 2002, 259: 301—306), Du and Wang extended Wang’s result to the
case that q is any positive integer. In this paper, we give a sufficient condition for Km,n to have a Kp,q-factorization. As a special case, it is shown that the Martin’s BAC conjecture is true when p : q = k : (k+ 1) for any positive integer k. 相似文献
Let λKm,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A Kp,q-factorization of λKm,n is a set of edge-disjoint Kp,q-factors of λKm,n which partition the set of edges of λKm,n. When p = 1 and q is a prime number, Wang, in his paper [On K1,q-factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K1,q-factorization of Km,n and gave a sufficient condition for such a factorization to exist. In papers [K1,k-factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; Kp,q-factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λKm,n to have a Kp,q-factorization. As a special case, it is shown that the necessary condition for the Kp,q-factorization of λKm,n is always sufficient when p : q = k : (k + 1) for any positive integer k. 相似文献
A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3. 相似文献
It is known that, if the minimal eigenvalue of a graph is ?2, then the graph satisfies Hoffman’s condition: for any generated complete bipartite subgraph K1,3 (a 3-claw) with parts {p} and {q1, q2, q3}, any vertex distinct from p and adjacent to the vertices q1 and q2 is adjacent to p but not adjacent to q3. We prove the converse statement for amply regular graphs containing a 3-claw and satisfying the condition µ > 1. 相似文献
It is known that if the minimal eigenvalue of a graph is ?2, then the graph satisfies Hoffman’s condition; i.e., for any generated complete bipartite subgraph K1,3 with parts {p} and {q1, q2, q3}, any vertex distinct from p and adjacent to two vertices from the second part is not adjacent to the third vertex and is adjacent to p. We prove the converse statement, formulated for strongly regular graphs containing a 3-claw and satisfying the condition gm > 1. 相似文献
We will prove that sphericity exceeds cubicity for complete bipartite graphs K(m,n) with max (m,n) > n0, that sph K(n,n) ≥ n, and that as a result of the latter there is a complete bipartite graph with sphericity exceeding cubicity for every value of cubicity at least 6. This answers the question of Fishburn [1]. 相似文献
An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by tr(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we give an explicit formula for the heterochromatic tree partition number of an r-edge-colored complete bipartite graph Km,n. 相似文献
In this paper some extremal properties of 3-colorings of bipartite complete graphs in the class of all bipartite p-threshold graphs that are uniquely 2-colorable are proved. As a consequence it is shown that the complete bipartite graphs Kp, p + r where p ? 2 and 0 ? r < are chromatically unique. A useful result concerning the maximization of a sum of powers of two under certain restrictions, which has an arithmetical interest, is also presented. 相似文献
A block B denotes a set of k = k1 + k2 elements which are divided into two subsets, B1 and B2, where ∣Bi∣ = ki, i = 1 or 2. Two elements are said to be linked in B if and only if they belong to different subsets of B. A balanced bipartite design, BBD(v, k1, k2, λ), is an arrangement of v elements into b blocks, each containing k elements such that each element occurs in exactly r blocks and any two distinct elements are linked in exactly λ blocks. A resolvable balanced bipartite design, RBBD(v, k1, k2, λ), is a BBD(v, k1, k2, λ), the b blocks of which can be divided into r sets which are called complete replications, such that each complete replication contains all the v elements of the design.Necessary conditions for the existence of RBBD(v, 1, k2, λ) and RBBD(v, n, n, λ) are obtained and it is shown that some of the conditions are also sufficient. In particular, necessary and sufficient conditions for the existence of RBBD(v, 1, k2, λ), where k2 is odd or equal to two, and of RBBD(v, n, n, λ), where n is even and 2n ? 1 is a prime power, are given. 相似文献
It is shown that the complete bipartite graph Km,n, for any pair m, n, and all subgraphs of K2,n, for any n, are uniquely reconstructable from their spanning trees. 相似文献
Current graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of Kn and Kn, n into graphs with quadrilateral embeddings are discussed, and some thickness results are obtained. Some new genus results are also obtained. 相似文献
Let K(p, q), p ≤ q, denote the complete bipartite graph in which the two partite sets consist of p and q vertices, respectively. In this paper, we prove that (1) the graph K(p, q) is chromatically unique if p ≥ 2; and (2) the graph K(p, q) - e obtained by deleting an edge e from K(p, q) is chromatically unique if p ≥ 3. The first result was conjectured by Salzberg, López, and Giudici, who also proved the second result under the condition that q - p ≤ 1. 相似文献
In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p1,p2,…,pk are distinct odd primes and ai>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph Kn,n up to isomorphism, where t=1 if a=0, t=2k if a=1, t=2k+1 if a=2, and t=3·2k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of Kn,n up to isomorphism, where s=1 if a=0, s=2k if a=1, s=2k+1 if a=2, and s=2k+2 if a?3. 相似文献
A connected graph Γ is said to be distance-balanced whenever for any pair of adjacent vertices u,v of Γ the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In [K. Handa, Bipartite graphs with balanced (a,b)-partitions, Ars Combin.51 (1999), 113-119] Handa asked whether every bipartite distance-balanced graph, that is not a cycle, is 3-connected. In this paper the Handa question is answered in the negative. Moreover, we show that a minimal bipartite distance-balanced graph, that is not a cycle and is not 3-connected, has 18 vertices and is unique. In addition, we give a complete classification of non-3-connected bipartite distance-balanced graphs for which the minimal distance between two vertices in a 2-cut is three. All such graphs are regular and for each k≥3 there exists an infinite family of such graphs which are k-regular.Furthermore, we determine a number of structural properties that a bipartite distance-balanced graph, which is not 3-connected, must have. As an application, we give a positive answer to the Handa question for the subfamily of bipartite strongly distance-balanced graphs. 相似文献
A bipartite graph G is an absolute retract if every isometric embedding g of G into a bipartite graph H is a coretraction (that is, there exists an edge-preserving map h from H to G such that hg is the identity map on G). Examples of absolute retracts are provided by chordal bipartite graphs and the covering graphs of modular lattices of breadth two. We give a construction and several characterizations of bipartite absolute retracts involving Helly type conditions. Bipartite absolute retracts apply to competitive location theory: they are precisely those bipartite graphs on which locational equilibria (Condorcet solutions) always exist.All graphs in this paper are finite, connected, and without loops or multiple edges. 相似文献