Search

A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph G is the rainbow connection number of G , denoted by rc (G). A simple way to rainbow-connect a graph G is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of G. This proves that rc (G) ≤ | V (G) | − 1. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of t (G) − 1 for rc (G) , where t (G) is the number of vertices in the largest induced tree of G ? The answer turns out to be negative, as there are counter-examples that show that even c ⋅ t (G) is not an upper bound for rc (G) for any given constant c. In this work we show that if we consider the forest number f (G) , the number of vertices in a maximum induced forest of G , instead of t (G) , then surprisingly we do get an upper bound. More specifically, we prove that rc (G) ≤ f (G) + 2. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound. [ABSTRACT FROM AUTHOR]

Abstract: A -dimensional box is the Cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as is the minimum integer such that is the intersection graph of a collection of -dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if is a Halin graph that is not isomorphic to , then . In fact, we prove the stronger result that if is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless is isomorphic to (in which case its boxicity is 1). [Copyright &y& Elsevier]

Abstract: An axis-parallel -dimensional box is a Cartesian product where each (for ) is a closed interval of the form on the real line. The boxicity of any graph , is the minimum positive integer such that G can be represented as the intersection graph of axis-parallel -dimensional boxes. A -dimensional cube is a Cartesian product , where each (for ) is a closed interval of the form on the real line. When the boxes are restricted to be axis-parallel cubes in -dimension, the minimum dimension required to represent the graph is called the cubicity of the graph (denoted by ). In this paper we prove that , where is the number of vertices in the graph. We also show that this upper bound is tight. Some immediate consequences of the above result are listed below: [1.] Planar graphs have cubicity at most . [2.] Outer planar graphs have cubicity at most . [3.] Any graph of treewidth has cubicity at most . Thus, chordal graphs have cubicity at most and circular arc graphs have cubicity at most , where is the clique number. The above upper bounds are tight, but for small constant factors. [Copyright &y& Elsevier]

Abstract: A -dimensional box is the cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as , is the minimum integer such that is the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the cartesian product where each is a closed interval on the real line of the form . The cubicity of , denoted as , is the minimum such that is the intersection graph of a collection of -cubes. In this paper we show that and , where is the cardinality of a minimum vertex cover of and is the number of vertices of . We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph , and , where is the number of vertices of , and these bounds are tight. We show that if is a bipartite graph then and this bound is tight. We also show that if is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , , then , where is the chromatic number of . [Copyright &y& Elsevier]

Abstract: Let be a finite, simple and undirected graph. For , let be the edge boundary of . Given an integer , , let the edge isoperimetric value of at be defined as . The edge isoperimetric peak of is defined as . Let denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete -ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete -ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth (denoted as ), and where , are constants. For a complete -ary tree of depth (denoted as ) and where is a constant, we show that and where , are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete -ary tree. Let be a finite, connected and rooted tree — the root being the vertex . Define a weight function where the weight of a vertex is the number of its successors (including itself) and let the weight index be defined as the number of distinct weights in the tree, i.e . For a positive integer , let . We show that . [Copyright &y& Elsevier]

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 such that there is an acyclic edge coloring using colors and it is denoted by . From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors. [Copyright &y& Elsevier]

Abstract: The notion of the carvingwidth of a graph was introduced by Seymour and Thomas [Call routing and the ratcatcher, Combinatorica 14 (1994) 217–241]. In this note, we show that the carvingwidth of a d-dimensional hypercube equals . [Copyright &y& Elsevier]

Abstract: The d-dimensional hypercube, , is the graph on vertices, which correspond to the d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by ) generalizes the notion of hypercubes: The vertices correspond to the d-vectors where the components are from the set , and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the and the . [Copyright &y& Elsevier]

Abstract: An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-) cycles. The acyclic chromatic index of a graph is the minimum number such that there is an acyclic edge coloring using colors and is denoted by . Let denote the maximum degree of a vertex in a graph . A complete bipartite graph with vertices on each side is denoted by . Alon, McDiarmid and Reed observed that for every prime . In this paper we prove that when is prime. Basavaraju, Chandran and Kummini proved that when is odd, which combined with our result implies that when is an odd prime. Moreover we show that if we remove any edge from , the resulting graph is acyclically -edge-colorable. [Copyright &y& Elsevier]