Degree conditions on induced claws

We introduce a closure concept for a superclass of the class of claw-free graphs defined by a degree condition on end vertices of induced claws. We show that the closure of a graph is the line graph of a triangle-free graph, and that the closure operation preserves the length of a longest path and cycle. These results extend the closure concept for claw-free graphs introduced by Ryjá?ek.     

A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence

A graph is Hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is Hamiltonian is known as an NP-complete problem, and no satisfactory characterization for these graphs has been found.In 1976, Bondy and Chvàtal introduced a way to get round the Hamiltonicity problem complexity by using a closure of the graph. This closure is a supergraph of G which is Hamiltonian iff G is. In particular, if the closure is the complete graph, then G is Hamiltonian. Since this seminal work, several closure concepts preserving Hamiltonicity have been introduced. In particular, in 1997, Ryjá?ek defined a closure concept for claw-free graphs based on local completion.Following a different approach, in 1974, Goodman and Hedetniemi gave a sufficient condition for Hamiltonicity based on the existence of a clique covering of the graph. This condition was recently generalized using the notion of Eulerian clique covering. In this context, closure concepts based on local completion are interesting since the closure of a graph contains more simplicial vertices than the graph itself, making the search for a clique covering easier.In this article, we introduce a new closure concept based on local completion which preserves the Hamiltonicity for every graph. Note that, moreover, the closure may be claw free even when the graph is not.     

Concept of a vertex in a matroid and 3-connected graphs

The concept of a matroid vertex is introduced. The vertices of a matroid of a 3-connected graph are in one-to-one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3-connected graphs implies isomorphism. The concept of a vertex of a matroid leads to an equally simple proof of Whitney's theorem on the unique embedding of a 3-connected planar graph in the sphere. It also leads to a number of new facts about 3-connected graphs. Thus, consideration of a vertex in a matroid that is the dual of the matroid of a graph leads to a natural concept of a nonseparating cycle of a graph. Whitney's theorem on cyclic isomorphism can be strengthened (even if the nonseparating cycles of a graph are considered, the theorem is found to work) and a new criterion for planarity of 3-connected graphs is obtained (in terms of nonseparating cycles).     

Non rank 3 strongly regular graphs with the 5-vertex condition

Three new strongly regular graphs on 256, 120, and 135 vertices are described in this paper. They satisfy thet-vertex condition — in the sense of [1] — on the edges and on the nonedges fort=4 but they are not rank 3 graphs. The problem to search for any such graph was discussed on a folklore level several times and was fixed in [2]. Here the graph on 256 vertices satisfies even the 5-vertex condition, and has the graphs on 120 and 135 vertices as its subgraphs. The existence of these graphs was announced in [3] and [4]. [4] contains M. H. Klin's interpretation of the graph on 120 vertices. Further results concerning these graphs were obtained by A. E. Brouwer, cf. [5].     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

Balanced group-labeled graphs

A group-labeled graph is a graph whose vertices and edges have been assigned labels from some abelian group. The weight of a subgraph of a group-labeled graph is the sum of the labels of the vertices and edges in the subgraph. A group-labeled graph is said to be balanced if the weight of every cycle in the graph is zero. We give a characterization of balanced group-labeled graphs that generalizes the known characterizations of balanced signed graphs and consistent marked graphs. We count the number of distinct balanced labellings of a graph by a finite abelian group $\Gamma$ and show that this number depends only on the order of $\Gamma$ and not its structure. We show that all balanced labellings of a graph can be obtained from the all-zero labeling using simple operations. Finally, we give a new constructive characterization of consistent marked graphs and markable graphs, that is, graphs that have a consistent marking with at least one negative vertex.     

Eulerian detachments with local edge-connectivity

For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless.     

Fully gated graphs: Recognition and convex operations

A graph is fully gated when every convex set of vertices is gated. Doignon posed the problem of characterizing fully gated graphs and in particular of deciding whether there is an efficient algorithm for their recognition. While the number of convex sets can be exponential, we establish that it suffices to examine only the convex hulls of pairs of vertices. This yields an elementary polynomial time algorithm for the recognition of fully gated graphs; however, it does not appear to lead to a simple structural characterization. In this direction, we establish that fully gated graphs are closed under a set of ‘convex’ operations, including a new operation which duplicates the vertices of a convex set (under some well-defined restrictions). This in turn establishes that every bipartite graph is an isometric subgraph of a fully gated graph, thereby severely limiting the potential for a characterization based on subgraphs. Finally, a large class of fully gated graphs is obtained using the presence of bipartite dominators, which suggests that simple convex operations cannot suffice to produce all fully gated graphs.     

Two Bounds for the Domination Number of a Graph

Upper and lower bounds are obtained for the domination numberof a graph, by means of a lemma involving the concept of a minimumdominating set of vertices. Although these results are obtainedexplicitly for graphs, there are analogous results in the theoryof directed graphs.     

On betweenness-uniform graphs

The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distanceregular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large n, there are superpolynomially many betweenness-uniform graphs on n vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.