Search

In this work, we give the sharp upper bound for the number of cliques in graphs with bounded odd circumferences. This generalized Turán-type result is an extension of the celebrated Erdős and Gallai theorem and a strengthening of Luo's recent result. The same bound for graphs with bounded even circumferences is a trivial application of the theorem of Li and Ning. [ABSTRACT FROM AUTHOR]

The planar Turán number ex P (n , C k) is the maximum number of edges in an n-vertex planar graph not containing a cycle of length k. Let k ≥ 11 and c, d be constants. Cranston et al., and independently Lan and Song showed that ex P (n , C k) ≥ 3 n - 6 - c n / k holds for large n. Moreover, Cranston et al. conjectured that ex P (n , C k) ≤ 3 n - 6 - d n / k log 2 3 when n is large. In this note, we prove that ex P (n , C k) ≥ 3 n - 6 - 6 · 3 log 2 3 n / k log 2 3 holds for every k ≥ 7 . This implies that the conjecture of Cranston et al. is essentially best possible. [ABSTRACT FROM AUTHOR]

Let H be a set of graphs. The planar Turán number, e x P (n , H) , is the maximum number of edges in an n-vertex planar graph which does not contain any member of H as a subgraph. When H = { H } has only one element, we usually write e x P (n , H) instead. The study of extremal planar graphs was initiated by Dowden (J Graph Theory 83(3):213–230, 2016). He obtained sharp upper bounds for both e x P (n , C 5) and e x P (n , K 4) . Later on, sharp upper bounds were proved for e x P (n , C 6) and e x P (n , C 7) . In this paper, we show that e x P (n , { K 4 , C 5 }) ≤ 15 7 (n - 2) and e x P (n , { K 4 , C 6 }) ≤ 7 3 (n - 2) . We also give constructions which show the bounds are sharp for infinitely many n. [ABSTRACT FROM AUTHOR]

Hakimi and Schmeichel determined a sharp lower bound for the number of cycles of length 4 in a maximal planar graph with n vertices, n ≥ 5 . It has been shown that the bound is sharp for n = 5 , 12 and n ≥ 14 vertices. However, the authors only conjectured the minimum number of cycles of length 4 for maximal planar graphs with the remaining small vertex numbers. In this note, we confirm their conjecture. [ABSTRACT FROM AUTHOR]

Let pr (K n , G) be the maximum number of colors in an edge-coloring of K n with no properly colored copy of G. For a family F of graphs, let ex (n , F) be the maximum number of edges in a graph G on n vertices which does not contain any graphs in F as subgraphs. In this paper, we show that pr (K n , G) - ex (n , G ′) = o (n 2) , where G ′ = { G - M : M is a matching of G } . Furthermore, we determine the value of pr (K n , P l) for sufficiently large n and the exact value of pr (K n , G) , where G is C 5 , C 6 and K 4 - , respectively. Also, we give an upper bound and a lower bound of pr (K n , K 2 , 3) . [ABSTRACT FROM AUTHOR]

The Wiener index of a connected graph is the sum of the distances between all pairs of vertices in the graph. It was conjectured that the Wiener index of an n-vertex maximal planar graph is at most ⌊ 1 18 (n 3 + 3 n 2) ⌋ . We prove this conjecture and determine the unique n-vertex maximal planar graph attaining this maximum, for every n ≥ 10 . [ABSTRACT FROM AUTHOR]

Let G be a graph, and and of size at least k. An important result on graph connectivity due to Perfect states that, if v and S are k-linked, then a (k−1)-link between a vertex v and S can be extended to a k-link between v and S such that the endvertices of the (k−1)-link are also the endvertices of the k-link. We begin by proving a generalization of Perfect's result by showing that, if two disjoint sets S1 and S2 are k-linked, then a t-link (t1 and S2 can be extended to a k-link between S1 and S2 such that the endvertices of the t-link are preserved in the k-link. Next, we are able to use these results to show that a 3-connected claw-free graph always has a cycle passing through any given five vertices, but avoiding any other one specified vertex. We also show that this result is sharp by exhibiting an infinite family of 3-connected claw-free graphs in which there is no cycle containing a certain set of six vertices but avoiding a seventh specified vertex. A direct corollary of our main result shows that a 3-connected claw-free graph has a topological wheel minor Wk with k ≤ 5 if and only if it has a vertex of degree at least k. Finally, we also show that a graph polyhedrally embedded in a surface always has a cycle passing through any given three vertices, but avoiding any other specified vertex. The result is best possible in the sense that the polyhedral embedding assumption is necessary, and there are infinitely many graphs polyhedrally embedded in surfaces having no cycle containing a certain set of four vertices but avoiding a fifth specified vertex. [ABSTRACT FROM AUTHOR]

A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number π opt is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. The optimal pebbling number of the square grid graph P n □ P m was investigated in several papers (Bunde et al. in J Graph Theory 57(3):215–238, 2008; Xue and Yerger in Graphs Combin 32(3):1229–1247, 2016; Győri et al. in Period Polytech Electr Eng Comput Sci 61(2):217–223 2017). In this paper, we present a new method using some recent ideas to give a lower bound on π opt . We apply this technique to prove that π opt (P n □ P m) ≥ 2 13 n m . Our method also gives a new proof for π opt (P n) = π opt (C n) = 2 n 3 . [ABSTRACT FROM AUTHOR]

We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bound on the minimum number of point guards required to cover the gallery in terms of the minimum number of vertical mobile guards and the minimum number of horizontal mobile guards required to cover the gallery. Furthermore, we show that the latter two numbers can be computed in linear time. [ABSTRACT FROM AUTHOR]

We prove the quarter of a century old conjecture that every K -free graph with n vertices and [ n /4]+ m edges contains m pairwise edge-disjoint triangles. [ABSTRACT FROM AUTHOR]

We give upper bounds for the size of 3-uniform hypergraphs avoiding a given odd cycle using the definition of a cycle due to Berge. In particular, we show that a 3-uniform hypergraph containing no cycle of length 2 k+1 has less than 4 k n+ O( n) edges. Constructions show that these bounds are best possible (up to constant factor) for k=1,2,3, 5. [ABSTRACT FROM AUTHOR]

Let G1⊗ G2 be the strong product of a k-extendable graph G1 and an l-extendable graph G2, and X an arbitrary set of vertices of G1⊗ G2 with cardinality 2[( k+1)( l+1)/2]. We show that G1⊗ G2− X contains a perfect matching. It implies that G1⊗ G2 is [( k+1)( l+1)/2]-extendable, whereas the Cartesian product of G1 and G2 is only ( k+ l+1)-extendable. As in the case of the Cartesian product, the proof is based on a lemma on the product of a k-extendable graph G and K2. We prove that G⊗ K2 is ( k+1)-extendable, and, a bit surprisingly, it even remains ( k+1)-extendable if we add edges to it. [ABSTRACT FROM AUTHOR]

Abstract. Two extremal-type versions of the connectivity augmentation problem are investigated. Using ear-decomposition theorems we prove that (i) every 2-connected graph on n vertices can be made 4-connected by adding at most n new edges, and (ii) every 3-connected and 3-regular graph on n is greater than or equal to 8 vertices can be made 4-connected by adding n/2 new edges. [ABSTRACT FROM AUTHOR]

In this paper, we prove that any graph of n vertices and t( n)+ m edges, where t( n) is the Turán number, contains (1− o(1) m edge disjoint K'sif m= o( n). Furthermore, we determine the maximum m such that every graph of n vertices and t( n)+ m edges contains m edge disjoint K's if n is sufficiently large. [ABSTRACT FROM AUTHOR]

The problem is the following: How many questions are necessary in the worst case to determine whether a point X in the n-dimensional Euclidean space R belongs to the n-dimensional unit cube Q , where we are allowed to ask which halfspaces of ( n−1)-dimensional hyperplanes contain the point X? It is known that ⌌3 n/2⌍ questions are sufficient. We prove here that cn questions are necessary, where c≈1.2938 is the solution of the equation x log x−( x−1) log ( x−1)=1. [ABSTRACT FROM AUTHOR]

It was proved ([5], [6]) that if G is an n-vertex-connected graph then for any vertex sequence v , ..., v ≠ V( G) and for any sequence of positive integers k , ..., k such that k +...+ k =| V( G)|, there exists an n-partition of V( G) such that this partition separates the vertices v , ..., v( n), and the class of the partition containing v induces a connected subgraph consisting of k vertices, for i=1, 2, ..., n. Now fix the integers k , ..., k . In this paper we study what can we say about the vertex-connectivity of G if there exists such a partition of V( G) for any sequence of vertices v , ..., v ≠ V( G). We find some interesting cases when the existence of such partitions implies the n-vertex-connectivity of G, in the other cases we give sharp lower bounds for the vertex-connectivity of G. [ABSTRACT FROM AUTHOR]