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]

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree δ, the rainbow connection number is upper bounded by 3 n/(δ + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432-437), improving the previously best known bound of 20 n/δ (J Graph Theory 63 (2010), 185-191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3 n/(δ + 1) − 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree δ. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc( G), is upper bounded by Γ c( G) + 2, where Γ c( G) is the connected domination number of G. Bounds of the form diameter( G)⩽ rc( G)⩽ diameter( G) + c, 1⩽ c⩽4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc( G)⩽3· radius( G). In most of these cases, we also demonstrate the tightness of the bounds. [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: In this paper, we study the relationship between the Asymmetric Traveling Salesman Problem (ATSP) and the Cycle Cover Problem in terms of the strength of the triangle inequality on the edge costs in the given complete directed graph instance, . The strength of the triangle inequality is captured by parametrizing the triangle inequality as follows. A complete directed graph with a cost function is said to satisfy the -parametrized triangle inequality if for all distinct . Then the graph is called a -triangular graph. For any -triangular graph , for , we show that , where and are the costs of an optimum Hamiltonian cycle and an optimum cycle cover respectively. In addition, we observe that there exists an infinite family of -triangular graphs for each valid which demonstrates the near-tightness (up to a factor of ) of the above bound. For , the ratio can become unbounded. The upper bound is shown constructively and can also be viewed as an approximation algorithm for ATSP with parametrized triangle inequality. We also consider the following problem: in a -triangular graph, does there exist a function such that is bounded above by ? (Here and are the costs of the maximum cost and minimum cost edges respectively.) We show that when , . This upper bound is sharp in the sense that there exist -triangular graphs with . Moreover, for , no such function exists. [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]

Abstract: A d-dimensional box is a Cartesian product of d closed intervals on the real line. The boxicity of a graph is the minimum dimension d such that it is representable as the intersection graph of d-dimensional boxes. We give a short constructive proof that every graph with maximum degree D has boxicity at most . We also conjecture that the best upper bound is linear in D. [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 can be represented as 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 integer such that can be represented as the intersection graph of a collection of -cubes. The threshold dimension of a graph is the smallest integer such that can be covered by threshold spanning subgraphs of . In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on vertices with a factor of for any unless . From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on vertices with factor for any unless . In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is -complete to determine whether a given split graph has boxicity at most 3. [ABSTRACT FROM AUTHOR]