Search

A $k$-block in a graph $G$ is a maximal set of at least $k$ vertices no two of which can be separated in $G$ by deleting fewer than $k$ vertices. The block number $\beta(G)$ of $G$ is the maximum integer $k$ for which $G$ contains a $k$-block. We prove a structure theorem for graphs without a $(k+1)$-block, showing that every such graph has a tree-decomposition in which every torso has at most $k$ vertices of degree $2k^2$ or greater. This yields a qualitative duality, since every graph that admits such a decomposition has block number at most $2k^2$. We also study $k$-blocks in graphs from classes of graphs $\mathcal{G}$ that exclude some fixed graph as a topological minor, and prove that every $G \in \mathcal{G}$ satisfies $\beta(G) \leq c\sqrt[3]{|G|}$ for some constant $c = c( \mathcal{G})$. Moreover, we show that every graph of tree-width at least $2k^2$ has a minor containing a $k$-block. This bound is best possible up to a multiplicative constant.

A path in a vertex-colored graph is called a \emph{vertex-monochromatic path} if its internal vertices have the same color. A vertex-coloring of a graph is a \emph{monochromatic vertex-connection coloring} (\emph{MVC-coloring} for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph $G$, the \emph{monochromatic vertex-connection number}, denoted by $mvc(G)$, is defined to be the maximum number of colors used in an \emph{MVC-coloring} of $G$. These concepts of vertex-version are natural generalizations of the colorful monochromatic connectivity of edge-version, introduced by Caro and Yuster. In this paper, we mainly investigate the Erd\H{o}s-Gallai-type problems for the monochromatic vertex-connection number $mvc(G)$ and completely determine the exact value. Moreover, the Nordhaus-Gaddum-type inequality for $mvc(G)$ is also given., Comment: 15 pages

A group valued function on a graph is called balanced if the product of its values along any cycle is equal to the identity element of the group. We compute the number of balanced functions from edges and vertices of a directed graph to a finite group., Comment: arXiv admin note: substantial text overlap with arXiv:1303.5456

An embedding of a graph into $\mathbb{R}^3$ is said to be linear, if any edge of the graph is sent to be a line segment. And we say that an embedding $f$ of a graph $G$ into $\mathbb{R}^3$ is free, if $\pi_1(\mathbb{R}^3-f(G))$ is a free group. It was known that for any complete graph its linear embedding is always free. In this paper we investigate the freeness of linear embeddings considering the number of vertices. It is shown that for any simple connected graph with at most 6 vertices, if its minimal valency is at least 3, then its linear embedding is always free. On the contrary when the number of vertices is much larger than the minimal valency or connectivity, the freeness may not be an intrinsic property of such graphs. In fact we show that for any $n \geq 1$ there are infinitely many connected graphs with minimal valency $n$ which have non-free linear embeddings, and furthermore, that there are infinitely many $n$-connected graphs which have non-free linear embeddings.

In 1995, Brouwer proved that the toughness of a connected $k$-regular graph $G$ is at least $k/\lambda-2$, where $\lambda$ is the maximum absolute value of the non-trivial eigenvalues of $G$. Brouwer conjectured that one can improve this lower bound to $k/\lambda-1$ and that many graphs (especially graphs attaining equality in the Hoffman ratio bound for the independence number) have toughness equal to $k/\lambda$. In this paper, we improve Brouwer's spectral bound when the toughness is small and we determine the exact value of the toughness for many strongly regular graphs attaining equality in the Hoffman ratio bound such as Lattice graphs, Triangular graphs, complements of Triangular graphs and complements of point-graphs of generalized quadrangles. For all these graphs with the exception of the Petersen graph, we confirm Brouwer's intuition by showing that the toughness equals $k/(-\lambda_{min})$, where $\lambda_{min}$ is the smallest eigenvalue of the adjacency matrix of the graph., Comment: 15 pages, 1 figure, accepted to Discrete Applied Mathematics, special issue dedicated to the "Applications of Graph Spectra in Computer Science" Conference, Centre de Recerca Matematica (CRM), Bellaterra, Barcelona, June 16-20, 2012

A dominating set $S$ of a graph $G$ is called locating-dominating, LD-set for short, if every vertex $v$ not in $S$ is uniquely determined by the set of neighbors of $v$ belonging to $S$. Locating-dominating sets of minimum cardinality are called $LD$-codes and the cardinality of an LD-code is the location-domination number $\lambda(G)$. An LD-set $S$ of a graph $G$ is global if it is an LD-set of both $G$ and its complement $\overline{G}$. The global location-domination number $\lambda_g(G)$ is the minimum cardinality of a global LD-set of $G$. In this work, we give some relations between locating-dominating sets and the location-domination number in a graph and its complement., Comment: 15 pages: 2 tables; 8 figures; 20 references

Let $G=(V,E)$ be a supply graph and $H=(V,F)$ a demand graph defined on the same set of vertices. An assignment of capacities to the edges of $G$ and demands to the edges of $H$ is said to satisfy the \emph{cut condition} if for any cut in the graph, the total demand crossing the cut is no more than the total capacity crossing it. The pair $(G,H)$ is called \emph{cut-sufficient} if for any assignment of capacities and demands that satisfy the cut condition, there is a multiflow routing the demands defined on $H$ within the network with capacities defined on $G$. We prove a previous conjecture, which states that when the supply graph $G$ is series-parallel, the pair $(G,H)$ is cut-sufficient if and only if $(G,H)$ does not contain an \emph{odd spindle} as a minor; that is, if it is impossible to contract edges of $G$ and delete edges of $G$ and $H$ so that $G$ becomes the complete bipartite graph $K_{2,p}$, with $p\geq 3$ odd, and $H$ is composed of a cycle connecting the $p$ vertices of degree 2, and an edge connecting the two vertices of degree $p$. We further prove that if the instance is \emph{Eulerian} --- that is, the demands and capacities are integers and the total of demands and capacities incident to each vertex is even --- then the multiflow problem has an integral solution. We provide a polynomial-time algorithm to find an integral solution in this case. In order to prove these results, we formulate properties of tight cuts (cuts for which the cut condition inequality is tight) in cut-sufficient pairs. We believe these properties might be useful in extending our results to planar graphs., Comment: An extended abstract of this paper will be published at the 44th Symposium on Theory of Computing (STOC 2012)

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. Akbari, Cameron, and Khosrovshahi conjectured that the number of vertices of every reduced graph of rank r is at most $m(r)=2^{(r+2)/2}-2$ if r is even and $m(r) = 5\cdot2^{(r-3)/2}-2$ if r is odd. In this article, we prove that if the conjecture is not true, then there would be a counterexample of rank at most $46$. We also show that every reduced graph of rank r has at most $8m(r)+14$ vertices., Comment: Final version, to appear in Combinatorica

Let $G = (V,E)$ be a graph and $k \ge 0$ an integer. A $k$-independent set $S \subseteq V$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. With $\alpha_k(G)$ we denote the maximum cardinality of a $k$-independent set of $G$. We prove that, for a graph $G$ on $n$ vertices and average degree $d$, $\alpha_k(G) \ge \frac{k+1}{\lceil d \rceil + k + 1} n$, improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on k-independence, J. Graph Theory 15 (1991), 99-107]., Comment: 16 pages

A set S is independent in a graph G if no two vertices from S are adjacent. By core(G) we mean the intersection of all maximum independent sets. The independence number alpha(G) is the cardinality of a maximum independent set, while mu(G) is the size of a maximum matching in G. A connected graph having only one cycle, say C, is a unicyclic graph. In this paper we prove that if G is a unicyclic graph of order n and n-1 = alpha(G) + mu(G), then core(G) coincides with the union of cores of all trees in G-C., Comment: 8 pages, 5 figures

Let $G$ be a graph each component of which has order at least 3, and let $G$ have order $n$, size $m$, total domination number $\gamma_t$ and maximum degree $\Delta(G)$. Let $\Delta = 3$ if $\Delta(G) = 2$ and $\Delta = \Delta (G)$ if $\Delta(G) \ge 3$. It is known [J. Graph Theory 49 (2005), 285--290; J. Graph Theory 54 (2007), 350--353] that $m \le \Delta (n- \gamma_t)$. In this paper we characterize the extremal graphs $G$ satisfying $m = \Delta (n- \gamma_t)$., Comment: 15 pages

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G), Revised preprint with an extra section on an approximation algorithm. arXiv admin note: text overlap with arXiv:1101.5747

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of H. A famous result of Chv\'atal, R\"{o}dl, Szemer\'edi and Trotter states that there exists a constant c(\Delta) such that r(H) \leq c(\Delta) n for every graph H with n vertices and maximum degree \Delta. The important open question is to determine the constant c(\Delta). The best results, both due to Graham, R\"{o}dl and Ruci\'nski, state that there are constants c and c' such that 2^{c' \Delta} \leq c(\Delta) \leq 2^{c \Delta \log^2 \Delta}. We improve this upper bound, showing that there is a constant c for which c(\Delta) \leq 2^{c \Delta \log \Delta}. The induced Ramsey number r_{ind}(H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd\H{o}s conjectured the existence of a constant c such that, for any graph H on n vertices, r_{ind}(H) \leq 2^{c n}. We move a step closer to proving this conjecture, showing that r_{ind} (H) \leq 2^{c n \log n}. This improves upon an earlier result of Kohayakawa, Pr\"{o}mel and R\"{o}dl by a factor of \log n in the exponent., Comment: 18 pages

Quasi-random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi-randomness of graphs. Let $k \ge 2$ be a fixed integer, $\alpha_1,...,\alpha_k$ be positive reals satisfying $\sum_{i} \alpha_i = 1$ and $(\alpha_1,..., \alpha_k) \neq (1/k,...,1/k)$, and $G$ be a graph on $n$ vertices. If for every partition of the vertices of $G$ into sets $V_1,..., V_k$ of size $\alpha_1 n,..., \alpha_k n$, the number of complete graphs on $k$ vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi-random. However, the method of quasi-random hypergraphs they used did not provide enough information to resolve the case $(1/k,..., 1/k)$ for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi-random. Janson also posed the same question in his study of quasi-randomness under the framework of graph limits. In this paper, we positively answer their question., Comment: 20 pages, 1 figures

We associate a graph $\mathcal{N}_{G}$ with a group $G$ (called the non-nilpotent graph of $G$) as follows: take $G$ as the vertex set and two vertices are adjacent if they generate a non-nilpotent subgroup. In this paper we study the graph theoretical properties of $\mathcal{N}_{G}$ and its induced subgraph on $G\backslash nil(G)$, where $nil(G)=\{x\in G | < x,y> \text{is nilpotent for all} y\in G\}$. For any finite group $G$, we prove that $\mathcal{N}_G$ has either $|Z^*(G)|$ or $|Z^*(G)|+1$ connected components, where $Z^*(G)$ is the hypercenter of $G$. We give a new characterization for finite nilpotent groups in terms of the non-nilpotent graph. In fact we prove that a finite group $G$ is nilpotent if and only if the set of vertex degrees of $\mathcal{N}_G$ has at most two elements., to appear in Communications in Algebra

A sparsifier of a graph is a sparse graph that approximates it. A spectral sparsifier is one that approximates it spectrally, which means that their Laplacian matrices have similar quadratic forms. We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. In particular, we prove that for every $\epsilon \in (0,1)$ and every undirected, weighted graph $G = (V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\lceil (n-1)/\epsilon^2\rceil$ edges such that for every $x \in \R^{V}$, $ (1-\epsilon)^2 \cdot x^T L_G x \leq x^{T} L_{H} x \leq (1+\epsilon)^2 \cdot x^{T} L_{G} x$, where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$, respectively. We give an elementary deterministic polynomial time algorithm for constructing $H$. This result is a special case of a significantly more general theorem which provides sparse approximations of general positive semidefinite matrices: given any real matrix $B_{n\times m}$...

A unit cube in $k$ dimensions ($k$-cube) is defined as the the Cartesian product $R_1\times R_2\times...\times R_k$ where $R_i$(for $1\leq i\leq k$) is a closed interval of the form $[a_i,a_i+1]$ on the real line. A graph $G$ on $n$ nodes is said to be representable as the intersection of $k$-cubes (cube representation in $k$ dimensions) if each vertex of $G$ can be mapped to a $k$-cube such that two vertices are adjacent in $G$ if and only if their corresponding $k$-cubes have a non-empty intersection. The \emph{cubicity} of $G$ denoted as $\cubi(G)$ is the minimum $k$ for which $G$ can be represented as the intersection of $k$-cubes. We give an $O(bw\cdot n)$ algorithm to compute the cube representation of a general graph $G$ in $bw+1$ dimensions given a bandwidth ordering of the vertices of $G$, where $bw$ is the \emph{bandwidth} of $G$. As a consequence, we get $O(\Delta)$ upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and co-comparability graphs which have $O(\Delta)$ bandwidth. Thus we have: 1) $\cubi(G)\leq 3\Delta-1$, if $G$ is an AT-free graph. 2) $\cubi(G)\leq 2\Delta+1$, if $G$ is a circular-arc graph. 3) $\cubi(G)\leq 2\Delta$, if $G$ is a co-comparability graph. Also for these graph classes, there are constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with $O(\Delta)$ width. We can thus generate the cube representation of such graphs in $O(\Delta)$ dimensions in polynomial time., Comment: 9 pages, 0 figures

Let G be a graph with n vertices, and let k be an integer dividing n. G is said to be strongly k-colorable if for every partition of V(G) into disjoint sets V_1 \cup ... \cup V_r, all of size exactly k, there exists a proper vertex k-coloring of G with each color appearing exactly once in each V_i. In the case when k does not divide n, G is defined to be strongly k-colorable if the graph obtained by adding k \lceil n/k \rceil - n isolated vertices is strongly k-colorable. The strong chromatic number of G is the minimum k for which G is strongly k-colorable. In this paper, we study the behavior of this parameter for the random graph G(n, p). In the dense case when p >> n^{-1/3}, we prove that the strong chromatic number is a.s. concentrated on one value \Delta+1, where \Delta is the maximum degree of the graph. We also obtain several weaker results for sparse random graphs., Comment: 16 pages

We study a point process describing the asymptotic behavior of sizes of the largest components of the random graph G(n,p) in the critical window p=n^{-1}+lambda n^{-4/3}. In particular, we show that this point process has a surprising rigidity. Fluctuations in the large values will be balanced by opposite fluctuations in the small values such that the sum of the values larger than a small epsilon is almost constant., Comment: 25 pages

A simple graph $G$ is \textit{k-ordered} (respectively, \textit{k-ordered hamiltonian}), if for any sequence of $k$ distinct vertices $v_1, ..., v_k$ of $G$ there exists a cycle (respectively, hamiltonian cycle) in $G$ containing these $k$ vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than $K_4$ and $K_{3, 3}$. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph $G$ on more than 6 vertices is square free, and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after $K_4$ and $K_{3, 3}$ that is 3-regular 4-ordered hamiltonian is the Heawood graph, and we exhibit forbidden subgraphs for 3-regular 4-ordered hamiltonian graphs on more than 10 vertices. Finally, we construct an infinite family of 3-regular 4-ordered graphs., Comment: 15 pages, 10 figures