Home About us Contact
|
Home About us Contact | ||
|
|
||
Complete Bipartite Graphs (complete + bipartite_graph)
Selected Abstractsd -Regular graphs of acyclic chromatic index at least d+2JOURNAL OF GRAPH THEORY, Issue 3 2010Manu 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] Weight choosability of graphsJOURNAL OF GRAPH THEORY, Issue 3 2009Tomasz 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] Minimum spanners of butterfly graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2001Shien-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] | ||||||||||