Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds

Let k ≥ 2, be an integer and M be a closed two-manifold with Euler characteristic χ(M) ≤ 0. We prove that each polyhedral map G onM , which has at least (8 k² + 6 k − 6)|χ (M)| vertices, contains a connected subgraph H of order k such that every vertex of this subgraph has, in G, the degree at most 4 k + 4. Moreover, we show that the bound 4k + 4 is best possible. Fabrici and Jendrol’ proved that for the sphere this bound is 10 ifk = 2 and 4 k + 3 if k ≥ 3. We also show that the same holds for the projective plane.     

Looseness of Plane Graphs

A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.     

Greedily Finding a Dense Subgraph

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k²) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

On Light Graphs in 3-Connected Plane Graphs Without Triangular or Quadrangular Faces

 We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P _k , a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m. Received: June 29, 1998 Final version received: April 11, 2000     

Hitting time results for Maker‐Breaker games

We study Maker‐Breaker games played on the edge set of a random graph. Specifically, we analyze the moment a typical random graph process first becomes a Maker's win in a game in which Maker's goal is to build a graph which admits some monotone increasing property \begin{align*}\mathcal{P}\end{align*}. We focus on three natural target properties for Maker's graph, namely being k ‐vertex‐connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the k ‐vertex connectivity game exactly at the time the random graph process first reaches minimum degree 2k; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree 2; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree 4. The latter two statements settle conjectures of Stojakovi? and Szabó. We also prove generalizations of the latter two results; these generalizations partially strengthen some known results in the theory of random graphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Lengths of cycles in halin graphs

A Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree two and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T. We prove that such a graph on n vertices contains cycles of all lengths l, 3 ≤ l n, except, possibly, for one even value m of l. We prove also that if the tree T contains no vertex of degree three then G is pancyclic.     

Edge partitions of optimal 2-plane and 3-plane graphs

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.     

Degree conditions for 2-factors

For any positive integer k, we investigate degree conditions implying that a graph G of order n contains a 2-factor with exactly k components (vertex disjoint cycles). In particular, we prove that for k ≤ (n/4), Ore's classical condition for a graph to be hamiltonian (k = 1) implies that the graph contains a 2-factor with exactly k components. We also obtain a sufficient degree condition for a graph to have k vertex disjoint cycles, at least s of which are 3-cycles and the remaining are 4-cycles for any s ≤ k. © 1997 John Wiley & Sons, Inc.     

The edge reconstruction number of a disconnected graph

The edge reconstruction number of a graph G, RN(G), is the minimum number of edge deleted subgraphs required to determine G up to isomorphism. We prove the following results for a disconnected graph G with at least two nontrivial components. If G has a pair of nontrivial nonisomorphic components then RN(G) ≤ 3. If G has a pair of nontrivial nonisomorphic components, is not a forest, and contains a nontrivial component other than K₃ or K_1,3 then RN(G) ≤ 2. Finally, if all nontrivial components of G are isomorphic to a graph with k edges, then RN(G) ≤ k + 2. The edge reconstruction results in this paper are similar to the vertex reconstruction results stated by Myrvold (“The Ally-Reconstruction Number of a Disconnected Graph,” Ars Combinatoria, Vol. 28 [1989] pp. 123-127), but a significant difference is that the edge reconstruction number of a disconnected graph is often two, while the vertex reconstruction number of a graph is always three or more. © 1995 John Wiley & Sons, Inc.     

Vertex partitions of chordal graphs

A k‐tree is a chordal graph with no (k + 2)‐clique. An ?‐tree‐partition of a graph G is a vertex partition of G into ‘bags,’ such that contracting each bag to a single vertex gives an ?‐tree (after deleting loops and replacing parallel edges by a single edge). We prove that for all k ≥ ? ≥ 0, every k‐tree has an ?‐tree‐partition in which each bag induces a connected ‐tree. An analogous result is proved for oriented k‐trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 167–172, 2006     

An upper bound for the k-domination number of a graph

The k-domination number of a graph G, γk(G), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k, then γk(G) ≤ kp/(k + 1).     

Complexity results for scheduling tasks with discrete starting times

Suppose that n independent tasks are to be scheduled without preemption on a set of identical parallel processors. Each task T_i requires a given execution time τ_i and it may be started for execution on any processor at any of its prescribed starting times s_i1, s_i2, …, s_iki, with k_i ≤ k for some fixed integer k. We first prove that the problem of finding a feasible schedule on a single processor is NP-complete in the strong sense even when τ_i ε {τ, τ′} and k_i ≤ 3 for 1 ≤ i ≤ n. The same problem is, however, shown to be solvable in O(n log n) time, provided s_iki − s_i1 < τ_i for 1 ≤ i ≤ n. We then show that the problem of finding a feasible schedule on an arbitrary number of processors is strongly NP-complete even when τ_i ε {τ, τ′}, k_i = 2 and s_i2 − s_i1 = δ < τ_i for 1 ≤ i ≤ n. Finally a special case with k_i = 2 and s_i2 − s_i1 = 1, 1 ≤ i ≤ n, of the above multiprocessor scheduling problem is shown to be solvable in polynomial time.     

Alternating Hamiltonian cycles

Colour the edges of a complete graph withn vertices in such a way that no vertex is on more thank edges of the same colour. We prove that for everyk there is a constantc _ksuch that ifn>c _kthen there is a Hamiltonian cycle with adjacent edges having different colours. We prove a number of other results in the same vein and mention some unsolved problems.     

On Isomorphisms of Finite Cayley Graphs

A Cayley graph Cay(G,S) of a groupGis called a CI-graph if wheneverTis another subset ofGfor which Cay(G,S) Cay(G,T), there exists an automorphism σ ofGsuch thatS^σ = T. For a positive integerm, the groupGis said to have them-CI property if all Cayley graphs ofGof valencymare CI-graphs; further, ifGhas thek-CI property for allk ≤ m, thenGis called anm-CI-group, and a |G|-CI-groupGis called a CI-group. In this paper, we prove that Ais not a 5-CI-group, that SL(2,5) is not a 6-CI-group, and that all finite 6-CI-groups are soluble. Then we show that a nonabelian simple group has the 4-CI property if and only if it is A₅, and that no nonabelian simple group has the 5-CI property. Also we give nine new examples of CI-groups of small order, which were found to be CI-groups with the assistance of a computer.     

Graph decomposition with applications to subdivisions and path systems modulo k

The existence of a function α(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least α(k) has a decomposition A ∪ B ∪ C such that G(A) has minimum degree at least k, each vertex of A is joined to at least k vertices of B, and no two vertices of B are separated by fewer than k vertices in G(G ∪ C). This is applied to prove the existence of subdivisions of complete bipartite graphs (complete graphs) with prescribed path lengths modulo k in graphs of sufficiently high minimum degree (chromatic number) and path systems with prescribed ends and prescribed lengths modulo k in graphs of sufficiently high connectivity.     

Improved lower bounds on k-independence

A vertex set Y in a (hyper)graph is called k-independent if in the sub(hyper)-graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k-independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán's theorem.     

Connectivity keeping edges in graphs with large minimum degree

The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that G−v is still k-connected. In this paper, we consider a generalization of the above result [G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63–68]. We prove the following result:Suppose G is a k-connected graph with minimum degree at least 3k/2+2. Then G has an edge e such that G−V(e) is still k-connected.The bound on the minimum degree is essentially best possible.     

Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity

In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=K_k(K₁+K_n−k−1), the join of K_k, the complete graph on k vertices, with the disjoint union of K₁ and K_n−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.