			Home About us Contact

Bipartite Graphs (bipartite + graph)

Distribution by Scientific Domains

Mathematics and Statistics	95%

Kinds of Bipartite Graphs

complete bipartite graph

Terms modified by Bipartite Graphs

bipartite graph g

Selected Abstracts

d -Regular graphs of acyclic chromatic index at least d+2

JOURNAL OF GRAPH THEORY, Issue 3 2010
Manu Basavaraju
Abstract An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a,(G). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a,(G),,+2, where ,=,(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require ,+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d -regular graphs with 2n vertices and d>n, requires at least d+ 2 colors. We also show that a,(Kn, n),n+ 2, when n is odd using a more non-trivial argument. (Here Kn, n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn, n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d,5, n,2d+ 3 and dn even, there exist d -regular graphs which require at least d+2-colors to be acyclically edge colored. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226,230, 2010 [source]

Forbidden induced bipartite graphs

JOURNAL OF GRAPH THEORY, Issue 3 2009
Peter Allen
Abstract Given a fixed bipartite graph H, we study the asymptotic speed of growth of the number of bipartite graphs on n vertices which do not contain an induced copy of H. Whenever H contains either a cycle or the bipartite complement of a cycle, the speed of growth is . For every other bipartite graph except the path on seven vertices, we are able to find both upper and lower bounds of the form . In many cases we are able to determine the correct value of c. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 219,241, 2009 [source]

Designs for two-colour microarray experiments

JOURNAL OF THE ROYAL STATISTICAL SOCIETY: SERIES C (APPLIED STATISTICS), Issue 4 2007
R. A. Bailey
Summary., Designs for two-colour microarray experiments can be viewed as block designs with two treatments per block. Explicit formulae for the A- and D-criteria are given for the case that the number of blocks is equal to the number of treatments. These show that the A- and D-optimality criteria conflict badly if there are 10 or more treatments. A similar analysis shows that designs with one or two extra blocks perform very much better, but again there is a conflict between the two optimality criteria for moderately large numbers of treatments. It is shown that this problem can be avoided by slightly increasing the number of blocks. The two colours that are used in each block effectively turn the block design into a row,column design. There is no need to use a design in which every treatment has each colour equally often: rather, an efficient row,column design should be used. For odd replication, it is recommended that the row,column design should be based on a bipartite graph, and it is proved that the optimal such design corresponds to an optimal block design for half the number of treatments. Efficient row,column designs are given for replications 3,6. It is shown how to adapt them for experiments in which some treatments have replication only 2. [source]

Mutually independent hamiltonian paths in star networks

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2005
Cheng-Kuan Lin
Abstract Two hamiltonian paths P1 = ,u1, u2,,,un(G), and P2 = ,v1, v2,,,vn(G), of G from u to v are independent if u = u1 = v1, v = vn(G) = un(G), and vi , ui for every 1 < i < n(G). A set of hamiltonian paths, {P1, P2,,,Pk}, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A bipartite graph G is hamiltonian laceable if there exists a hamiltonian path joining any two nodes from different partite sets. A bipartite graph is k -mutually independent hamiltonian laceable if there exists k -mutually independent hamiltonian paths between any two nodes from distinct partite sets. The mutually independent hamiltonian laceability of a bipartite graph G, IHPL(G), is the maximum integer k such that G is k -mutually independent hamiltonian laceable. Let Sn denote the n -dimensional star graph. We prove that IHPL(S2) = 1, IHPL(S3) = 0, and IHPL(Sn) = n, 2 if n , 4. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 110,117 2005 [source]

Random dense bipartite graphs and directed graphs with specified degrees

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009
Catherine Greenhill
Abstract Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t. In particular, we find precise formulae for the probabilities that a given bipartite graph is edge-disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out-degrees s and in-degrees t. In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

Sampling independent sets in the discrete torus,

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2008
David GalvinArticle first published online: 27 MAY 200
Abstract The even discrete torus is the graph TL,d on vertex set {0,,,L , 1}d (with L even) in which two vertices are adjacent if they differ on exactly one coordinate and differ by 1(modL) on that coordinate. The hard-core measure with activity , on TL,d is the probability distribution ,, on the independent sets (sets of vertices spanning no edges) of TL,d in which an independent set I is chosen with probability proportional to ,|I|. This distribution occurs naturally in problems from statistical physics and the study of communication networks. We study Glauber dynamics, a single-site update Markov chain on the set of independent sets of TL,d whose stationary distribution is ,,. We show that for , = ,(d,1/4 log 3/4d) and d sufficiently large the convergence to stationarity is (essentially) exponentially slow in Ld,1. This improves a result of Borgs, Chayes, Frieze, Kim, Tetali, Vigoda, and Vu (Proceedings of the IEEE FOCS (1999), 218,229) 5 who had shown slow mixing of Glauber dynamics for , growing exponentially with d. Our proof, which extends to ,-local chains (chains which alter the state of at most a proportion , of the vertices in each step) for suitable ,, closely follows the conductance argument of Borgs et al., 5 adding to it some combinatorial enumeration methods that are modifications of those used by Galvin and Kahn (Combinatorics, Probability and Computing 13 (2004), 137,164) 12 to show that the hard-core model with parameter , on the integer lattice ,d exhibits phase coexistence for , = ,(d,1/4 log 3/4d). The discrete even torus is a bipartite graph, with partition classes , (consisting of those vertices the sum of whose coordinates is even) and . Our result can be expressed combinatorially as the statement that for each sufficiently large ,, there is a ,(,) > 0 such that if I is an independent set chosen according to ,,, then the probability that ,I ,,|,|I ,, is at most ,(,)Ld is exponentially small in Ld,1. In particular, we obtain the combinatorial result that for all , > 0 the probability that a uniformly chosen independent set from TL,d satisfies ,I ,,|,|I ,,, (.25 - ,)Ld is exponentially small in Ld,1. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2006
David Galvin
Abstract Let , = (V,E) be a finite, d -regular bipartite graph. For any , > 0 let ,, be the probability measure on the independent sets of , in which the set I is chosen with probability proportional to ,|I| (,, is the hard-core measure with activity , on ,). We study the Glauber dynamics, or single-site update Markov chain, whose stationary distribution is ,,. We show that when , is large enough (as a function of d and the expansion of subsets of single-parity of V) then the convergence to stationarity is exponentially slow in |V(,)|. In particular, if , is the d -dimensional hypercube {0,1}d we show that for values of , tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

Semi-random LDPC codes for CDMA communication over non-linear band-limited satellite channels

INTERNATIONAL JOURNAL OF SATELLITE COMMUNICATIONS AND NETWORKING, Issue 4 2006
Mohamed Adnan Landolsi
Abstract This paper considers the application of low-density parity check (LDPC) error correcting codes to code division multiple access (CDMA) systems over satellite links. The adapted LDPC codes are selected from a special class of semi-random (SR) constructions characterized by low encoder complexity, and their performance is optimized by removing short cycles from the code bipartite graphs. Relative performance comparisons with turbo product codes (TPC) for rate 1/2 and short-to-moderate block sizes show some advantage for SR-LDPC, both in terms of bit error rate and complexity requirements. CDMA systems using these SR-LDPC codes and operating over non-linear, band-limited satellite links are analysed and their performance is investigated for a number of signal models and codes parameters. The numerical results show that SR-LDPC codes can offer good capacity improvements in terms of supportable number of users at a given bit error performance. Copyright © 2006 John Wiley & Sons, Ltd. [source]

d -Regular graphs of acyclic chromatic index at least d+2

A structure theorem for graphs with no cycle with a unique chord and its consequences

JOURNAL OF GRAPH THEORY, Issue 1 2010
Nicolas Trotignon
Abstract We give a structural description of the class ,, of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in ,, is either in some simple basic class or has a decomposition. Basic classes are chordless cycles, cliques, bipartite graphs with one side containing only nodes of degree 2 and induced subgraphs of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for ,,, i.e. every graph in ,, can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations, and all graphs built this way are in ,,. This has several consequences: an ,,(nm) -time algorithm to decide whether a graph is in ,,, an ,,(n+ m) -time algorithm that finds a maximum clique of any graph in ,,, and an ,,(nm) -time coloring algorithm for graphs in ,,. We prove that every graph in ,, is either 3-colorable or has a coloring with , colors where , is the size of a largest clique. The problem of finding a maximum stable set for a graph in ,, is known to be NP-hard. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 31,67, 2010 [source]

Forbidden induced bipartite graphs

Weight choosability of graphs

JOURNAL OF GRAPH THEORY, Issue 3 2009
Tomasz Bartnicki
Abstract Suppose the edges of a graph G are assigned 3-element lists of real weights. Is it possible to choose a weight for each edge from its list so that the sums of weights around adjacent vertices were different? We prove that the answer is positive for several classes of graphs, including complete graphs, complete bipartite graphs, and trees (except K2). The argument is algebraic and uses permanents of matrices and Combinatorial Nullstellensatz. We also consider a directed version of the problem. We prove by an elementary argument that for digraphs the answer to the above question is positive even with lists of size two. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 242,256, 2009 [source]

Sufficient conditions for graphs to be ,,-optimal, super-edge-connected, and maximally edge-connected

JOURNAL OF GRAPH THEORY, Issue 3 2005
Angelika Hellwig
Abstract The restricted-edge-connectivity of a graph G, denoted by ,,(G), is defined as the minimum cardinality over all edge-cuts S of G, where G - S contains no isolated vertices. The graph G is called ,,-optimal, if ,,(G),=,,(G), where ,(G) is the minimum edge-degree in G. A graph is super-edge-connected, if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree. In this paper, we present sufficient conditions for arbitrary, triangle-free, and bipartite graphs to be ,,-optimal, as well as conditions depending on the clique number. These conditions imply super-edge-connectivity, if , (G),,,3, and the equality of edge-connectivity and minimum degree. Different examples will show that these conditions are best possible and independent of other results in this area. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 228,246, 2005 [source]

Bi-arc graphs and the complexity of list homomorphisms

JOURNAL OF GRAPH THEORY, Issue 1 2003
Tomas Feder
Abstract Given graphs G, H, and lists L(v) , V(H), v , V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) , V(H) such that uv , E(G) implies f(u)f(v) , E(H), and f(v) , L(v) for all v , V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) , V(H), v , V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP -complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP -complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi-arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi-arc graph, and is NP -complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61,80, 2003 [source]

Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs

JOURNAL OF GRAPH THEORY, Issue 1 2001
F. M. Dong
Abstract Given a graph G and an integer k,,,1, let ,(G,,k) denote the number of k -independent partitions of G. Let ,,,s(p,q) (resp., ,,2,s(p,q)) denote the family of connected (resp., 2-connected) graphs which are obtained from the complete bipartite graph Kp,q by deleting a set of s edges, where p,,,q,,,2. This paper first gives a sharp upper bound for ,(G,3), where G ,,,,,,s(p,q) and 0,,,s,,,(p,,,1)(q,,,1) (resp., G ,,,,,2,s(p,q) and 0,,,s,,,p,+,q,,,4). These bounds are then used to show that if G ,,,,,,s(p,q) (resp., G ,,,,,2,s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ,,,si(p+i,q,i) where max and si,=,s,,,i(p,q+i) (resp., a subset of ,,2,s(p,q), where either 0,,,s,,,q,,,1, or s,,,2q,,,3 and p,,,q,+,4). By applying these results, we show finally that any 2-connected graph obtained from Kp,q by deleting a set of edges that forms a matching of size at most q,,,1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48,77, 2001 [source]

A linear time algorithm for the reverse 1-median problem on a cycle

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2006
Rainer E. Burkard
Abstract This article deals with the reverse 1-median problem on graphs with positive vertex weights. The problem is proved to be strongly NP -hard even in the case of bipartite graphs and not approximable within a constant factor (unless P = NP). Furthermore, a linear time algorithm for the reverse 1-median problem on a cycle with linear cost functions (RMC) is developed. It is also shown that there exists an integral optimal solution of RMC if the input data are integral. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 16-23 2006 [source]

Minimum spanners of butterfly graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2001
Shien-Ching Hwang
Abstract Given a connected graph G, a spanning subgraph G, of G is called a t -spanner if every pair of two adjacent vertices in G has a distance of at most t in G,. A t -spanner of a graph G is minimum if it contains minimum number of edges among all t -spanners of G. Finding minimum spanners for general graphs is rather difficult. Most of previous results were obtained for some particular graphs, for example, butterfly graphs, cube-connected cycles, de Bruijn graphs, Kautz graphs, complete bipartite graphs, and permutation graphs. The butterfly graphs were originally introduced as the underlying graphs of FFT networks which can perform the fast Fourier transform (FFT) very efficiently. In this paper, we successfully construct most of the minimum t -spanners for the k -ary r -dimensional butterfly graphs for 2 , t , 6 and t = 8. © 2001 John Wiley & Sons, Inc. [source]

Random dense bipartite graphs and directed graphs with specified degrees

Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs

Largest planar matching in random bipartite graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2002
Marcos Kiwi
Abstract For a distribution ,, over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions ,,. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where ,, is the uniform distribution over the k -regular bipartite graphs on W and M. For k = o(n1/4), we establish that tends to 2 in probability when n , ,. Convergence in mean is also studied. Furthermore, we show that if each of the n2 possible edges between W and M are chosen independently with probability 0 < p < 1, then L(n)/n tends to a constant ,p in probability and in mean when n , ,. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 162,181, 2002 [source]