A Structure Theorem for Strong Immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices.     

Tetravalent vertex‐transitive graphs of order 4p

A graph is vertex‐transitive if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc.     

Online Ramsey games for more than two colors

Consider the following one‐player game played on an initially empty graph with n vertices. At each stage a randomly selected new edge is added and the player must immediately color the edge with one of r available colors. Her objective is to color as many edges as possible without creating a monochromatic copy of a fixed graph F. We use container and sparse regularity techniques to prove a tight upper bound on the typical duration of this game with an arbitrary, but fixed, number of colors for a family of 2‐balanced graphs. The bound confirms a conjecture of Marciniszyn, Spöhel and Steger and yields the first tight result for online graph avoidance games with more than two colors. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 464–492, 2017     

Cycles through ten vertices in 3-connected cubic graphs

It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore, we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under which it has a cycle through four chosen vertices and two edges. We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices each map to a distinct vertex of the Petersen graph.     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

Graphs with constant link and small degree or order

The graph G has constant link L if for each vertex x of G the graph induced by G on the vertices adjacent to x is isomorphic to L. For each graph L on 6 or fewer vertices we decide whether or not there exists a graph G with constant link L. From this we are able to list all graphs on 11 or fewer vertices which have constant link.     

Proper path‐factors and interval edge‐coloring of (3,4)‐biregular bigraphs

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)‐biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)‐biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3‐valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph. © 2009 Wiley Periodicals, Inc. J Graph Theory     

Medians of arbitrary graphs

For each vertex u in a connected graph H, the distance of u is the sum of the distances from u to each of the vertices v of H. A vertex of minimum distance in H is called a median vertex. It is shown that for any graph G there exists a graph H for which the subgraph of H induced by the median vertices is isomorphic to G.     

Random Graph Coverings I: General Theory and Graph Connectivity

In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number. Received June 21, 1999/Revised November 16, 2000 RID="*" ID="*" Work supported in part by grants from the Israel Academy of Aciences and the Binational Israel-US Science Foundation.     

A lower bound for groupies in graphs

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contain at least one groupie, the graph K_n − e contains just 2 groupie vertices for n ≥ 2. In this paper we derive a lower bound for the number of groupies which shows, in particular, that any graph with 2 or more vertices must contain at least 2 groupies. © 1996 John Wiley & Sons, Inc.     

Maximum pebbling number of graphs of diameter three

Given a configuration of pebbles on the vertices of a graph G, a pebbling move consists of taking two pebbles off some vertex v and putting one of them back on a vertex adjacent to v. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves that would place at least one pebble on v. The pebbling number of a graph G is the smallest integer m such that G is pebbleable for every configuration of m pebbles on G. We prove that the pebbling number of a graph of diameter 3 on n vertices is no more than (3/2)n + O(1), and, by explicit construction, that the bound is sharp. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Stratification and domination in graphs II

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class.) We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v. In this paper we investigate the F-domination number when (i) F is a 2-stratified path P₃ on three vertices rooted at a blue vertex which is a vertex of degree 1 in the P₃ and is adjacent to a blue vertex and with the remaining vertex colored red, and (ii) F is a 2-stratified K₃ rooted at a blue vertex and with exactly one red vertex.     

Partitioning the Vertices of a Graph into Two Total Dominating Sets

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every selfcomplementary graph with minimum degree at least two has such a partition.     

Maximum Orbit Weights in the σ-game and Lit-only σ-game on Grids and Graphs

Let G be a graph in which each vertex can be in one of two states: on or off. In the σ-game, when you “push” a vertex v you change the state of all of its neighbors, while in the σ⁺-game you change the state of v as well. Given a starting configuration of on vertices, the object of both games is to reduce it, by a sequence of pushes, to the smallest possible number of on vertices. We show that any starting configuration in a graph with no isolated vertices can, by a sequence of pushes, be reduced to at most half on, and we characterize those graphs for which you cannot do better. The proofs use techniques from coding theory. In the lit-only versions of these two games, you can only push vertices which are on. We obtain some results on the minimum number of on vertices one can obtain in grid graphs in the regular and lit-only versions of both games.     

The Diameter of a Scale-Free Random Graph

We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabási and Albert [3], as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabási, Albert and Jeong [1,5] and heuristic arguments given by Newman, Strogatz and Watts [23] suggest that after n steps the resulting graph should have diameter approximately logn. We show that while this holds for m=1, for m2 the diameter is asymptotically log n/log logn.* Research supported in part by NSF grant no. DSM9971788     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

A survey of stratified domination in graphs

A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.     

On connection between the switching separability of a graph and its subgraphs

A graph of order n ≥ 4 is called switching separable if its modulo-2 sum with some complete bipartite graph on the same set of vertices is divided into two mutually independent subgraphs, each having at least two vertices. We prove the following: If removing any one or two vertices of a graph always results in a switching separable subgraph then the graph itself is switching separable. On the other hand, for each odd order greater than 4, there is a graph that is not switching separable, but removing a vertex always results in a switching separable subgraph. We show some connection with similar facts on the separability of Boolean functions and the reducibility of n-ary quasigroups.     

Analysis of a game of graph solitaire

Let G be a simple undirected graph. To each vertex assign one of two colours say red or blue. A solitaire game is played on G as follows. A move consists of selecting a blue vertex, inverting the colours of its neighbours and then deleting the chosen vertex and all edges incident upon it. The goal is to delete all the vertices. The question of finding a winning strategy in the case when G is a simple cycle was proposed in the problems section of the American Mathematical Monthly. In this article some general results on winning colour configurations are derived and the game is analysed for certain other graph classes.     

All Arbitrarily Fixed Generalized Banana Trees Are Graceful

Consider a set of caterpillars, having equal and fixed diameter, in which one of the penultimate vertices is of arbitrary degree and all the other internal vertices including the other penultimate vertex are of fixed even degree. Merge an end-vertex adjacent to the penultimate vertex of fixed even degree of each of such caterpillars together. The rooted tree thus obtained is called Arbitrarily Fixed Generalized Banana Tree. In this paper we prove that all arbitrarily fixed generalized banana trees are graceful. This would imply that “all banana trees are graceful” and “all generalized banana trees are graceful” as corollaries.