Search

A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we investigate the proper connection number of the complement of a graph G according to some constraints of G itself. Also, we characterize the graphs on n vertices that have proper connection number n-2. Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if G and G¯ are both connected, then 4≤pc(G)+pc(G¯)≤n, and the upper bound holds if and only if G or G¯ is the n-vertex tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Maxd-Clique and Maxd-Club: A d-clique in a graph G=(V,E) is a subset S⊆V of vertices such that for every pair of vertices u,v∈S, the distance between u and v is at most d in G. A d-club in a graph G=(V,E) is a subset S′⊆V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Maxd-Clique (Maxd-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Since Max 1-Clique and Max 1-Club are identical to Max Clique, the inapproximabilty for Max Clique shown by Zuckerman in 2007 is transferred to them. Namely, Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n1-ε for any ε>0 unless P=NP. Also, in 2002, Marinc˘ek and Mohar showed that it is NP-hard to approximate Maxd-Club to within a factor of n1/3-ε for any ε>0 and any fixed d≥2. In this paper, we strengthen the hardness result; we prove that, for any ε>0 and any fixed d≥2, it is NP-hard to approximate Maxd-Club to within a factor of n1/2-ε. Then, we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for any integer d≥2. By using the similar ideas, we show the O(n1/2)-approximation algorithm for Maxd-Clique for any d≥2. This is the best possible in polynomial time unless P=NP, as we can prove the Ω(n1/2-ε)-inapproximability. [ABSTRACT FROM AUTHOR]

Let colg(G) be the game coloring number of a given graph G. Define the game coloring number of a family of graphs H as colg(H):=max{colg(G):G∈H}. Let Pk be the family of planar graphs of girth at least k. We show that colg(P7)≤5. This result extends a result about the game coloring number by Wang and Zhang [10] (colg(P8)≤5). We also show that these bounds are sharp by constructing a graph G where G∈Pk for each k≤8 such that colg(G)=5. As a consequence, colg(Pk)=5 for k=7,8. [ABSTRACT FROM AUTHOR]

A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove Behzad-Vizing conjecture for product graphs. In particular, we obtain the tight bound for certain classes of graphs. [ABSTRACT FROM AUTHOR]

A fullerene graph is a 3-connected cubic plane graph whose all faces are bounded by 5- or 6-cycles. In this paper, we show that a matching M of a fullerene graph can be extended to a perfect matching if the following hold: (i) three faces around each vertex in $$\{x,y:xy\in M\}$$ are bounded by 6-cycles and (ii) the edges in M lie at distance at least 13 pairwise. [ABSTRACT FROM AUTHOR]

The shortest augmenting path (Sap) algorithm is one of the most classical approaches to the maximum matching and maximum flow problems, e.g., using it Edmonds and Karp (J. ACM 19(2), 248-264 1972) have shown the first strongly polynomial time algorithm for the maximum flow problem. Quite astonishingly, although it has been studied for many years already, this approach is far from being fully understood. This is exemplified by the online bipartite matching problem. In this problem a bipartite graph G = (W ⊎ B, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. After arrival of this vertex we augment the current matching by using shortest augmenting path. It was conjectured by Chaudhuri et al. (INFOCOM'09) that the total length of all augmenting paths found by Sap is O(nlogn)O(nlog n) . However, no better bound than O(n2)O(n2) is known even for trees. In this paper we prove an O(nlog2n)O(nlog2 n) upper bound for the total length of augmenting paths for trees. [ABSTRACT FROM AUTHOR]

We consider distance queries in vertex-labeled planar graphs. For any fixed 0 < ϵ ≤ 1/2 we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex u and a label λ return a (1 + ϵ)-approximation of the distance from u to its closest vertex with label λ. For a directed planar graph with n vertices, such that the ratio of the largest to smallest arc length is bounded by N, the preprocessing time is O(ϵ-2 n lg3 n lg(n N)), the data structure size is O(ϵ-1 n lg(n N)), and the query time is O(lg lg n lg lg(n N) + ϵ-1). We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect. [ABSTRACT FROM AUTHOR]

The class of 2K2-free graphs and its various subclasses have been studied in a variety of contexts. In this paper, we are concerned with the colouring of (P3∪P2)-free graphs, a super class of 2K2-free graphs. We derive a O(ω3) upper bound for the chromatic number of (P3∪P2)-free graphs, and sharper bounds for (P3∪P2, diamond)-free graphs and for (2K2, diamond)-free graphs, where ω denotes the clique number. The last two classes are perfect if ω≥5 and ≥4 respectively. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be an isolate-free graph. For some α with 0<α≤1, a subset S of V is said to be an α-dominating set if for all v∈V\S,|N(v)∩S|≥α|N(v)|. The size of a smallest such S is called the α-domination number and is denoted by γα(G). A set S⊆V is said to be an α-rate dominating set of G if for any vertex v∈V, |N[v]∩X|≥α|N(v)|. The minimum cardinality of an α-rate dominating set of G is called the α-rate domination numberγ×α(G). The set of distinct values of γα(G) as α runs over (0, 1] is called the α-domination spectrum of a graph G, i.e., Spα(G)={γα(G):α∈(0,1]}. In this paper, we study some properties of Spα(G) and show that γα(G) changes its value only at rational points as α runs over (0, 1]. Using this result, we characterize some values of α such that γα(G)≤nα, where n is the number of vertices in G, holds. Finally, we present some improved probabilistic upper bounds of α-domination number and α-rate domination number of a graph G. [ABSTRACT FROM AUTHOR]

A t-tone k-coloring of a graph G=(V,E) is a function f:V→[k]t such that |f(u)∩f(v)| for all distinct vertices u and v. The t-tone chromatic number of G, denoted τt(G), is the smallest positive integer k such that G has a t-tone k-coloring. The Wiener index W(G) of a connected graph G is the sum of the distances of all pairs of vertices of G. In this paper, we prove that τt(G)≥t|V|-W(G)+|V|2 for a connected graph G and obtain a characterization when the equality holds. As a result, for each graph G (not necessarily connected), we obtain a formula for the t-tone chromatic number of G when t is sufficiently large. [ABSTRACT FROM AUTHOR]

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on four vertices (not necessarily induced) is bi-colored. The star chromatic number of G, denoted by χs(G), is the minimum number of colors needed to star color G. Similar to the notion of χ-boundedness in graphs, we say that a hereditary class of graphs G is χs-bounded if, for some integer valued function f, χs(G)≤f(ω(G)) for every G∈G, where ω(G) is the maximum number of vertices that are pairwise adjacent in G. We show that some classes of perfect graphs, some classes of (P5,C4)-free graphs, and some classes of K1,3-free graphs are χs-bounded. We also give examples in most of the cases to show that the bounds are tight. [ABSTRACT FROM AUTHOR]

We revisit the classical problem of computing the contour tree of a scalar field $$f:\mathbb {M}\rightarrow \mathbb {R}$$ , where $$\mathbb {M}$$ is a triangulation of a ball in $$\mathbb {R}^d$$ . The contour tree is a fundamental topological structure that tracks the evolution of level sets of f and has numerous applications in data analysis and visualization. All existing algorithms begin with a global sort of at least all critical values of f, which can require (roughly) $$\Omega (n\log n)$$ time, where n is the number of vertices of the mesh. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. (We assume that the Morse degree of the function f at any point is at most 3.) If C denotes the set of critical points in $$\mathbb {M}$$ , the running time is roughly $$O(N+\sum _{v \in C} \log \ell _v)$$ , where $$\ell _v$$ is the depth of v in the contour tree and N is the total complexity of $$\mathbb {M}$$ . This matches all existing upper bounds, but is a significant asymptotic improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes that are either adjacent in $$\mathbb {M}$$ or in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm. Our algorithm requires several novel ideas: partitioning $$\mathbb {M}$$ in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. [ABSTRACT FROM AUTHOR]

We consider the contact process on finite and connected graphs and study the behavior of the extinction time, that is, the amount of time that it takes for the infection to disappear in the process started from full occupancy. We prove, without any restriction on the graph G, that if the infection rate $$\lambda $$ is larger than the critical rate of the one-dimensional process, then the extinction time grows faster than $$\exp \{|G|/(\log |G|)^\kappa \}$$ for any constant $$\kappa > 1$$ , where | G| denotes the number of vertices of G. Also for general graphs, we show that the extinction time divided by its expectation converges in distribution, as the number of vertices tends to infinity, to the exponential distribution with parameter 1. These results complement earlier work of Mountford, Mourrat, Valesin and Yao, in which only graphs of bounded degrees were considered, and the extinction time was shown to grow exponentially in n; here we also provide a simpler proof of this fact. [ABSTRACT FROM AUTHOR]

Let $$G = (V, E)$$ be a simple graph with vertex set V and edge set E. A mixed Roman dominating function (MRDF) of G is a function $$f: V\cup E\rightarrow \{0,1,2\}$$ satisfying the condition every element $$x\in V\cup E$$ for which $$f(x)= 0$$ is adjacent or incident to at least one element $$y\in V\cup E$$ for which $$f(y) = 2$$ . The weight of a MRDF f is $$\omega (f)=\sum _{x\in V\cup E}f(x)$$ . The mixed Roman domination number of G is the minimum weight of a mixed Roman dominating function of G. In this paper, we initiate the study of the mixed Roman domination number and we present bounds for this parameter. We characterize the graphs attaining an upper bound and the graphs having small mixed Roman domination numbers. [ABSTRACT FROM AUTHOR]

In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called c-OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show that for each k ≥ 3 there is a class of CNFs of treewidth k for which the equivalent c-OBDDs are of size Ω( n ). Moreover, this lower bound holds if c-OBDDs are non-deterministic and semantic. Our second result uses the above lower bound to separate the above model from sentential decision diagrams (SDDs). In order to obtain the lower bound, we use a structural graph parameter called matching width. Our third result shows that matching width and pathwidth are linearly related. [ABSTRACT FROM AUTHOR]

In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. Very few precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P . Given a 3-polytope P, denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P by h( P). Jendrol' and Madaras in 1996 showed that if a polytope P in P is allowed to have a 5-vertex adjacent to four 5-vertices (called a minor (5, 5, 5, 5,∞)- star), then h( P) can be arbitrarily large. For each P in P with neither vertices of the degree from 6 to 8 nor minor (5, 5, 5, 5,∞)-star, it follows from Lebesgue's Theorem that h( P ) ≤ 17. We prove in particular that every such polytope P satisfies h( P ) ≤ 12, and this bound is sharp. This result is best possible in the sense that if vertices of one of degrees in {6, 7, 8} are allowed but those of the other two forbidden, then the height of minor 5-stars in P under the absence of minor (5, 5, 5, 5,∞)- stars can reach 15, 17, or 14, respectively. [ABSTRACT FROM AUTHOR]

We study the distributed low tree-depth decomposition problem for graphs restricted to a bounded expansion class. Low tree-depth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a linear-time model checking algorithm for graphs in a bounded expansion class. Recall that bounded expansion classes cover classes of graphs of bounded degree, of planar graphs, of graphs of bounded genus, of graphs of bounded treewidth, of graphs that exclude a fixed minor, and many other graphs. There is a sequential algorithm to compute low tree-depth decomposition (with bounded number of colors) in linear time. In this paper, we give the first efficient distributed algorithm for this problem. As it is usual for a symmetry breaking problem, we consider a synchronous model, and as we are interested in a deterministic algorithm, we use the usual assumption that each vertex has a distinct identity number. We consider the distributed message-passing $$\mathcal {CONGEST}_\mathrm{BC}$$ model, in which messages have logarithmic length and only local broadcast are allowed. In this model, we present a logarithmic time distributed algorithm for computing a low tree-depth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low tree-depth decomposition linear time algorithm are used as a core procedure in several non-trivial linear time algorithms. We believe that, similarly, low tree-depth decomposition could be at the heart of several non-trivial logarithmic time algorithms. [ABSTRACT FROM AUTHOR]

We call an edge colouring of a graph $$G$$ a rainbow colouring if every pair of vertices is joined by a rainbow path, i.e., a path where no two edges have the same colour. The minimum number of colours required for a rainbow colouring of the edges of $$G$$ is called the rainbow connection number (or rainbow connectivity) $${\mathrm {rc}}(G)$$ of $$G$$ . We investigate sharp thresholds in the Erdős-Rényi random graph for the property ' $${\mathrm {rc}}(G)\le r$$ ' where $$r$$ is a fixed integer. It is known that for $$r=2$$ , rainbow connection number $$2$$ and diameter $$2$$ happen essentially at the same time in random graphs. For $$r \ge 3$$ , we conjecture that this is not the case, propose an alternative threshold, and prove that this is an upper bound for the threshold for rainbow connection number $$r$$ . [ABSTRACT FROM AUTHOR]

For an integer $$\ell $$ at least three, we prove that every Hamiltonian $$P_\ell $$ -free graph $$G$$ on $$n>\ell $$ vertices has cycles of at least $$\frac{2}{\ell }n-1$$ different lengths. For small values of $$\ell $$ , we can improve the bound as follows. If $$4\le \ell \le 7$$ , then $$G$$ has cycles of at least $$\frac{1}{2}n-1$$ different lengths, and if $$\ell $$ is $$4$$ or $$5$$ and $$n$$ is odd, then $$G$$ has cycles of at least $$n-\ell +2$$ different lengths. [ABSTRACT FROM AUTHOR]

A hop dominating set of a graph G is a set D of vertices of G if for every vertex of V (G) \ D, there exists u ∈ D such that d(u, v) = 2. The hop domination number of a graph G, denoted by γh(G), is the minimum cardinality of a hop dominating set of G. We prove that for every tree T of order n with l leaves and s support vertices we have (n − l − s + 4)/3 ≤ γh(G) ≤ n/2, and characterize the trees attaining each of the bounds. [ABSTRACT FROM AUTHOR]

Let $$\fancyscript{T}_{n,\gamma }$$ be the collection of all $$n$$ -vertex trees with domination number $$\gamma $$ . In this paper, the first-, second- and third-smallest Laplacian permanents of trees in $$\fancyscript{T}_{n,\gamma }$$ are determined, respectively. Moreover, the corresponding extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

By generalizing the path method, we show that nonlinear spectral gaps of a finite connected graph are uniformly bounded from below by a positive constant which is independent of the target metric space. We apply our result to an $$r$$ -ball $$T_{d,r}$$ in the $$d$$ -regular tree, and observe that the asymptotic behavior of nonlinear spectral gaps of $$T_{d,r}$$ as $$r\rightarrow \infty $$ does not depend on the target metric space, which is in contrast to the case of a sequence of expanders. We also apply our result to the $$n$$ -dimensional Hamming cube $$H_n$$ and obtain an estimate of its nonlinear spectral gap with respect to an arbitrary metric space, which is asymptotically sharp as $$n\rightarrow \infty $$ . [ABSTRACT FROM AUTHOR]

For a graph $$X$$ with at most one isolated vertex and without isolated edges, a product-irregular labeling $$\omega :E(X)\rightarrow \{1,2,\ldots ,s\}$$ , first defined by Anholcer in 2009, is a labeling of the edges of $$X$$ such that for any two distinct vertices $$u$$ and $$v$$ of $$X$$ the product of labels of the edges incident with $$u$$ is different from the product of labels of the edges incident with $$v$$ . The minimal $$s$$ for which there exist a product irregular labeling is called the product irregularity strength of $$X$$ and is denoted by $$ps(X)$$ . In this paper it is proved that $$ps(X)\le |V(X)|-1$$ for any graph $$X$$ with more than $$3$$ vertices. Moreover, the connection between the product irregularity strength and the multidimensional multiplication table problem is given, which is especially expressed in the case of the complete multipartite graphs. [ABSTRACT FROM AUTHOR]

For every $$k \in {\mathbb {N}}_0$$ , we consider graphs in which for any induced subgraph, $$\Delta \le \omega - 1 + k$$ holds, where $$\Delta $$ is the maximum degree and $$\omega $$ is the maximum clique number of the subgraph. We give a finite forbidden induced subgraph characterization for every $$k$$ . As an application, we find some results on the chromatic number $$\chi $$ of a graph. B. Reed stated the conjecture that for every graph, $$\chi \le \lceil \frac{\Delta + \omega + 1 }{2}\rceil $$ holds. Since this inequality is fulfilled by graphs in which $$\Delta \le \omega + 2$$ holds, our results provide a hereditary graph class for which the conjecture holds. [ABSTRACT FROM AUTHOR]

The mirror (or bipartite complement) $${{\mathrm{mir}}}(B)$$ of a bipartite graph $$B=(X,Y,E)$$ has the same color classes $$X$$ and $$Y$$ as $$B$$ , and two vertices $$x \in X$$ and $$y \in Y$$ are adjacent in $${{\mathrm{mir}}}(B)$$ if and only if $$xy \notin E$$ . A bipartite graph is chordal bipartite if none of its induced subgraphs is a chordless cycle with at least six vertices. In this paper, we deal with chordal bipartite graphs whose mirror is chordal bipartite as well; we call these graphs auto-chordal bipartite graphs ( ACB graphs for short). We characterize ACB graphs, show that ACB graphs have unbounded bipartite Dilworth number, and we characterize ACB graphs with bipartite Dilworth number $$k$$ . [ABSTRACT FROM AUTHOR]

A facial parity edge-coloring of a $$2$$ -edge-connected plane graph is such an edge-coloring in which no two face-adjacent edges receive the same color and in addition, for each face $$f$$ and each color $$c$$ either no edge or an odd number of edges incident with $$f$$ is colored with $$c$$ . Let $$\chi _p^\prime (G)$$ denote the minimum number of colors used in such a coloring of $$G$$ . In this paper we prove that $$\chi _p^\prime (G)\le 9$$ for any $$2$$ -edge-connected outerplane graph $$G$$ with one exception. Moreover, we show that this bound is tight. [ABSTRACT FROM AUTHOR]

The famous 1-2-3 conjecture due to Karoński, Łuczak and Thomason states that the edges of any nice graph (without a component isomorphic to $$K_{2}$$ ) may be weighted from the set {1,2,3} so that the vertices are properly coloured by the sums of their incident edge weights. Bartnicki, Grytczuk and Niwcyk introduced its list version. Assign to each edge $$e\in E(G)$$ a list of $$k$$ real numbers, say $$L(e)$$ , and choose a weight $$w(e)\in L(e)$$ for each $$e \in E(G)$$ . The resulting function $$w: E(G)\rightarrow \bigcup _{e\in E(G)}L(e)$$ is called an edge $$k$$ -list-weighting. Given a graph $$G$$ , the smallest $$k$$ such that any assignment of lists of size $$k$$ to $$E(G)$$ permits an edge $$k$$ -list-weighting which is a vertex coloring by sums is denoted by $$ch^{e}_{\Sigma }(G)$$ and called the edge weight choosability of $$G$$ . Bartnicki, Grytczuk and Niwcyk conjectured that if $$G$$ is a nice graph, then $$ch^{e}_{\Sigma }(G)\le 3$$ . There is no known constant $$K$$ such that $$ch^{e}_{\Sigma }(G) \le K$$ for any nice graph $$G$$ . Fu et al. proved that for a nice graph $$G$$ with maximum degree $$\Delta (G)$$ , $$ch^{e}_{\Sigma }(G)\le \lceil \frac{3\Delta (G)}{2}\rceil $$ . In this paper, we improve this bound to $$\lceil \frac{4\Delta (G)+8}{3}\rceil $$ . [ABSTRACT FROM AUTHOR]

Let $$P$$ be a set of $$n$$ points in the plane. A geometric graph $$G$$ on $$P$$ is said to be locally Gabriel if for every edge $$(u,v)$$ in $$G$$ , the Euclidean disk with the segment joining $$u$$ and $$v$$ as diameter does not contain any points of $$P$$ that are neighbors of $$u$$ or $$v$$ in $$G$$ . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any $$n$$ , there exists LGG with $$\Omega (n^{5/4})$$ edges. This improves upon the previous best bound of $$\Omega (n^{1+\frac{1}{\log \log n}})$$ . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any $$n$$ point set, there exists an independent set of size $$\Omega (\sqrt{n}\log n)$$ . [ABSTRACT FROM AUTHOR]

Let $$P$$ be a set of $$n$$ points in the plane in general position. A subset $$H$$ of $$P$$ consisting of $$k$$ elements that are the vertices of a convex polygon is called a $$k$$ -hole of $$P$$ , if there is no element of $$P$$ in the interior of its convex hull. A set $$B$$ of points in the plane blocks the $$k$$ -holes of $$P$$ if any $$k$$ -hole of $$P$$ contains at least one element of $$B$$ in the interior of its convex hull. In this paper we establish upper and lower bounds on the sizes of $$k$$ -hole blocking sets, with emphasis in the case $$k=5$$ . [ABSTRACT FROM AUTHOR]

Let $$k$$ be an integer with $$k \ge 2$$ . In terms of the toughness of a graph, Win gave a sufficient condition for the existence of a spanning $$k$$ -tree, that is, a spanning tree in which the maximum degree is at most $$k$$ . For a spanning tree $$T$$ of a graph $$G$$ , we define the total excess $$\mathrm{te}(T,k)$$ of $$T$$ from $$k$$ as $$\mathrm{te}(T,k) := \sum _{v \in V(T)} \max \{d_T(v)-k, 0\}$$ , where $$V(T)$$ is the vertex set of $$T$$ and $$d_T(v)$$ is the degree of a vertex $$v$$ in $$T$$ . Enomoto, Ohnishi and Ota extended Win's result by giving a condition that guarantees the existence of a spanning tree $$T$$ with a bounded total excess. Here we further extend the result as follows. Let $$\omega (G)$$ be the number of components of a graph $$G$$ . Let $$k_1,k_2, \ldots ,k_p$$ be $$p$$ integers with $$k_1 \ge k_2 \ge \cdots \ge k_p \ge 2$$ , let $$t_1,t_2, \ldots ,t_p$$ be $$p$$ nonnegative integers, and let $$G$$ be a connected graph. If $$G$$ satisfies that $$\omega (G-S) \le (k_i - 2)|S| + 2 +t_i$$ for every $$1 \le i \le p$$ and every $$S \subset V(G)$$ , then $$G$$ has a spanning tree $$T$$ such that $$\mathrm{te}(T,k_i) \le t_i$$ for every $$1 \le i \le p$$ . [ABSTRACT FROM AUTHOR]

This paper deals with extremal problems concerning colorings of partial Steiner systems. We establish a new sufficient condition for r-colorability of a hypergraph from some class of such systems in terms of maximum vertex degree. Moreover, as a corollary we obtain a new lower bound for the threshold probability for r-colorability of a random hypergraph in a binomial model. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is rainbow connected if every pair of vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number rc( G) of G is defined to be the minimum integer t such that there exists an edge-coloring of G with t colors that makes G rainbow connected. For a graph G without any cut vertex, i.e., a 2-connected graph, of order n, it was proved that $${rc(G)\leq\lceil\frac{n}{2} \rceil}$$ and the bound is tight. In this paper, we prove that for a connected graph G of order n with at least one cut vertex, $${rc(G) \leq\frac{n+r-1} 2}$$ , where r is the number of blocks of G with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound $${\lfloor(2n-2)/3\rfloor}$$ for the rainbow connection number of a bridgeless (2-edge-connected) graph of order n. [ABSTRACT FROM AUTHOR]

For a graph G, we denote by δ( G) the minimum degree of G. A graph G is said to be claw-free if G has no induced subgraph isomorphic to K. In this article, we prove that every claw-free graph G with minimum degree at least 4 has a 2-factor in which each cycle contains at least $${\big\lceil\frac{\delta(G) - 1}{2}\big\rceil}$$ vertices and every 2-connected claw-free graph G with minimum degree at least 3 has a 2-factor in which each cycle contains at least δ( G) vertices. For the case where G is 2-connected, the lower bound on the length of a cycle is best possible. [ABSTRACT FROM AUTHOR]

Given n points in the plane, a covering path is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least n/2 segments, and n−1 straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of n points in the plane admits a (possibly self-crossing) covering path consisting of n/2+ O( n/log n) straight line segments. If the path is required to be noncrossing, we prove that (1− ε) n straight line segments suffice for a small constant ε>0, and we exhibit n-element point sets that require at least 5 n/9− O(1) segments in every such path. Further, the analogous question for noncrossing covering trees is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for n points in the plane requires Ω( nlog n) time in the worst case. [ABSTRACT FROM AUTHOR]

Is it proves that every connected graph with s vertices of degree 1 and 3 anf t vertices of degree at least 4 has a spanning tree with at least $ \frac{1}{3}t + \frac{1}{4}s + \frac{3}{2} $ leaves. Infinite series of grpahs showing that our bound is tight are given. [ABSTRACT FROM AUTHOR]

Let G be a graph that can be drawn on a plane in such a way that any edge intersects at most one other edge. It is proved that the chromatic number of G does not exceed 7. The bound $ \chi (G)\leq \frac{{9+\sqrt{17+64g }}}{2} $ is also proved for a graph G that can be drawn on a surface of genus g ( g ≥ 1) in such a way that any edge intersects at most one other edge. Bibliography: 8 titles. [ABSTRACT FROM AUTHOR]

Let G be a bipartite graph without loops and multiple edges on v ≥ 4 vertices, which can be drawn on a plane in such a way that any edge intersects at most one other edge. It is proved that such a graph has at most 3 v - 8 edges for even v ≠ 6 and at most 3 v - 9 edges for odd v and for v = 6. For all v ≥ 4, examples showing that these bounds are tight are constructed. At the end of the paper, it is discussed a question about drawings of complete bipartite graphs on a plane such that any edge intersects at most one other edge. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]

It is proved that every connected graph with s vertices of degree 3 and t vertices of degree at least 4 has a spanning tree with $ \frac{2}{5}t+\frac{1}{5}s+\alpha $ leaves, where $ \alpha \geq \frac{8}{5} $. Moreover, α ≥ 2 for all graphs, except for three exclusions. All exclusions are regular graphs of degree 4, and they are explicitly described in the paper. An infinite series of graphs containing only vertices of degree 3 and 4, for which the maximal number of leaves in a spanning tree is equal to $ \frac{2}{5}t+\frac{1}{5}s+2 $, is presented. Therefore it is proved that the bound is tight. Bibliography: 12 titles. [ABSTRACT FROM AUTHOR]

A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, $${\mathcal{H}(G)}$$ , of a graph G has V( G) as its set of vertices and the maximal cliques of G as its hyperedges. A vertex-colouring of $${\mathcal{H}(G)}$$ is a clique-colouring of G. Determining the clique-chromatic number, the least number of colours for which a graph G admits a clique-colouring, is known to be NP-hard. In this work, we establish that the clique-chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colours. For odd-seq circulant graphs, we show that their clique-chromatic number is at most four, and determine the cases when it is equal to two. Similar bounds for the chromatic number of these graphs are also obtained. [ABSTRACT FROM AUTHOR]

A signed k-submatching of a graph G is a function f : E( G) → {−1,1} satisfying f ( E( v)) ≤ 1 for at least k vertices $${v \in V(G)}$$. The maximum of the values of f ( E( G)), taken over all signed k-submatchings f, is called the signed k-submatching number and is denoted by $${\beta_S^{k}(G)}$$. In this paper, sharp bounds on $${\beta_S^{k}(G)}$$ for general graphs are presented. Exact values of $${\beta_S^{k}(G)}$$ for several classes of graphs are found. [ABSTRACT FROM AUTHOR]

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O( n). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O( n log n), where every intermediate triangulation has maximum degree at most k + 4. [ABSTRACT FROM AUTHOR]

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ( G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in claw-free graphs. Specifically, we show that γ( G) ≤ (3 n − 1)/5 if G is a connected claw-free graph of order n with minimum degree at least three and that this bound is sharp. [ABSTRACT FROM AUTHOR]

A simple topological graph$$T=(V(T), E(T))$$ T = ( V ( T ) , E ( T ) ) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs $$G$$ G and $$H$$ H are isomorphic if $$H$$ H can be obtained from $$G$$ G by a homeomorphism of the sphere, and weakly isomorphic if $$G$$ G and $$H$$ H have the same set of pairs of crossing edges. We generalize results of Pach and Tóth and the author’s previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph $$G$$ G with $$n$$ n vertices, $$m$$ m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize $$G$$ G is at most $$2^{O(n^2\log (m/n))}$$ 2 O ( n 2 log ( m / n ) ) , and at most $$2^{O(mn^{1/2}\log n)}$$ 2 O ( m n 1 / 2 log n ) if $$m\le n^{3/2}$$ m ≤ n 3 / 2 . As a consequence we obtain a new upper bound $$2^{O(n^{3/2}\log n)}$$ 2 O ( n 3 / 2 log n ) on the number of intersection graphs of $$n$$ n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with $$n$$ n vertices to $$2^{n^2\cdot \alpha (n)^{O(1)}}$$ 2 n 2 · α ( n ) O ( 1 ) , using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize $$G$$ G is at most $$2^{m^2+O(mn)}$$ 2 m 2 + O ( m n ) and at least $$2^{\Omega (m^2)}$$ 2 Ω ( m 2 ) for graphs with $$m>(6+\varepsilon )n$$ m > ( 6 + ε ) n . [ABSTRACT FROM AUTHOR]

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted by rc( G), is the minimum number of colors that are needed to make G rainbow connected. In this paper we give a Nordhaus-Gaddum-type result for the rainbow connection number. We prove that if G and $${\overline{G}}$$ are both connected, then $${4\leq rc(G)+rc(\overline{G})\leq n+2}$$. Examples are given to show that the upper bound is sharp for n ≥ 4, and the lower bound is sharp for n ≥ 8. Sharp lower bounds are also given for n = 4, 5, 6, 7, respectively. [ABSTRACT FROM AUTHOR]

The classic lower bounds δ + 1 (Dirac), 2 δ (Dirac) and 3 δ − 3 (Voss and Zuluaga) for the circumference (the order of a longest cycle C in a graph G) are based on the minimum degree δ and some G\ C structures, combined with some additional connectivity conditions. A natural problem arises to find an analogous bound in a general form ( i + 1)( δ − i + 1) with i = 0, 1, . . . , δ, including the bounds δ + 1, 2 δ and 3 δ − 3 as special cases. In this paper we present two tight lower bounds for the circumference just of the form ( i + 1)( δ − i + 1) for each $${i\in\{0,\ldots,\delta\}}$$ based entirely on appropriate G\ C structures, actually escaping any other additional conditions: in each graph G, (i) $${|C|\geq(\overline{p}+1)(\delta-\overline{p}+1)}$$ and (ii) $${|C|\geq(\overline{c}+1)(\delta-\overline{c}+1),}$$ where $${\overline{p}}$$ and $${\overline{c}}$$ denote the orders of a longest path and a longest cycle in G\ C, respectively. [ABSTRACT FROM AUTHOR]

Multi-coloring on the path is a model for frequency assignment in linear cellular networks. Two models have been studied in previous papers: calls may either have finite or infinite duration. For hexagonal networks, a variation of the models where limited frequency reassignment is allowed has also been studied. We add the concept of frequency reassignment to the models of linear cellular networks and close these problems by giving matching upper and lower bounds in all cases. We prove that no randomized algorithm can have a better competitive ratio than the best deterministic algorithms. In addition, we give an exact characterization of the natural greedy algorithms for these problems. All of the above results are with regard to competitive analysis. Taking steps towards a more fine-grained analysis, we consider the case of finite calls and no frequency reassignment and prove that, even though randomization cannot bring the competitive ratio down to one, it seems that the greedy algorithm is expected optimal on uniform random request sequences. We prove this for small paths and indicate it experimentally for larger graphs. [ABSTRACT FROM AUTHOR]

A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V ( G) − S is also adjacent to a vertex in V ( G) − S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G - E has no isolated vertex and the total restrained domination number of G - E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph. [ABSTRACT FROM AUTHOR]

An upper bound on the saturation number for graphs as well as associated extremal graphs was given by (Kászonyi and Tuza in J. Graph Theory, 10:203-210, ). A minor improvement of that result, which was implied in their paper, will be stated. Using this result, a series of exact saturation numbers and associated extremal graphs will be proved for the nearly complete graphs K − E( L), where L is a graph of order at most 4. [ABSTRACT FROM AUTHOR]

We prove that the crossing number of a graph decays in a 'continuous fashion' in the following sense. For any ε > 0 there is a δ > 0 such that for a sufficiently large n, every graph G with n vertices and m ≥ n edges, has a subgraph G′ of at most (1 − δ) m edges and crossing number at least (1 − ε)CR( G). This generalizes the result of J. Fox and Cs. Tóth. [ABSTRACT FROM AUTHOR]

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let $${c_{\infty}(G)}$$ denote the number of cops needed to capture the robber in a graph G in this variant. We characterize graphs G with c( G) = 1, and give an $${O( \mid V(G)\mid^2)}$$ algorithm for their detection. We prove a lower bound for c of expander graphs, and use it to prove three things. The first is that if $${np \geq 4.2 {\rm log}n}$$ then the random graph $${G= \mathcal{G}(n, p)}$$ asymptotically almost surely has $${\eta_{1}/p \leq \eta_{2}{\rm log}(np)/p}$$ , for suitable positive constants $${\eta_{1}}$$ and $${\eta_{2}}$$ . The second is that a fixed-degree random regular graph G with n vertices asymptotically almost surely has $${c_{\infty}(G) = \Theta(n)}$$ . The third is that if G is a Cartesian product of m paths, then $${n/4km^2 \leq c_{\infty}(G) \leq n/k}$$ , where $${n = \mid V(G)\mid}$$ and k is the number of vertices of the longest path. [ABSTRACT FROM AUTHOR]