Home About us Contact
|
Home About us Contact | ||
|
|
||
Adjacent Vertices (adjacent + vertex)
Selected AbstractsGraham's pebbling conjecture on products of cyclesJOURNAL OF GRAPH THEORY, Issue 2 2003David S. Herscovici Abstract Chung defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graph is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G×H), f(G)f(H). We prove Graham's conjecture when G is a cycle for a variety of graphs H, including all cycles. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 141,154, 2003 [source] Multi-coloring the Mycielskian of graphsJOURNAL OF GRAPH THEORY, Issue 4 2010Wensong Lin Abstract A k -fold coloring of a graph is a function that assigns to each vertex a set of k colors, so that the color sets assigned to adjacent vertices are disjoint. The kth chromatic number of a graph G, denoted by ,k(G), is the minimum total number of colors used in a k -fold coloring of G. Let µ(G) denote the Mycielskian of G. For any positive integer k, it holds that ,k(G) + 1,,k(µ(G)),,k(G) + k (W. Lin, Disc. Math., 308 (2008), 3565,3573). Although both bounds are attainable, it was proved in (Z. Pan, X. Zhu, Multiple coloring of cone graphs, manuscript, 2006) that if k,2 and ,k(G),3k,2, then the upper bound can be reduced by 1, i.e., ,k(µ(G)),,k(G) + k,1. We conjecture that for any n,3k,1, there is a graph G with ,k(G)=n and ,k(µ(G))=n+ k. This is equivalent to conjecturing that the equality ,k(µ(K(n, k)))=n+k holds for Kneser graphs K(n, k) with n,3k,1. We confirm this conjecture for k=2, 3, or when n is a multiple of k or n,3k2/ln k. Moreover, we determine the values of ,k(µ(C2q+1)) for 1,k,q. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 311,323, 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] On the L(h, k)-labeling of co-comparability graphs and circular-arc graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2009Tiziana Calamoneri Abstract Given two nonnegative integers h and k, an L(h, k)- labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)-labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)-labeling problem is NP-complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co-comparability graphs, its subclass of interval graphs, and circular-arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)-labeling of co-comparability and circular-arc graphs. In particular, we provide the first algorithm to L(h, k)-label co-comparability, interval, and circular-arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously-known ones using a number of colors that is at most twice the optimum. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009 [source] Multigraph augmentation under biconnectivity and general edge-connectivity requirements ,NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2001Toshimasa Ishii Abstract Given an undirected multigraph G = (V, E) and a requirement function r,: () , Z+ (where () is the set of all pairs of vertices and Z+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the local edge-connectivity and vertex-connectivity between every pair x, y , V become at least r,(x, y) and two, respectively. In this paper, we show that the problem can be solved in O(n3(m + n) log(n2/(m + n))) time, where n and m are the numbers of vertices and pairs of adjacent vertices in G, respectively. This time complexity can be improved to O((nm + n2 log n) log n), in the case of the uniform requirement r,(x, y)= ,, for all x, y , V. Furthermore, for the general r,, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed ,,* = max{r,(x, y) | x, y , V}. © 2001 John Wiley & Sons, Inc. [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] | ||||||||||