Springer Science and Business Media LLC

Let G = (V, E) be a graph and x, y, z ∈ V be three designated vertices. We give a necessary and sufficient condition for the existence of a rigid two-dimensional framework (G, p), in which x, y, z are collinear. This result extends a classical result of Laman on the existence of a rigid framework on G. Our proof leads to an efficient algorithm which can test whether G satisfies the condition.

Let G be a finite abelian group, written additively, and H a subgroup of G. The subgroup sum graph $$\varGamma _{G,H}$$ is the graph with vertex set G, in which two distinct vertices x and y are joined if $$x+y\in H{\setminus }\{0\}$$ . These graphs form a fairly large class of Cayley sum graphs. Among cases which have been considered previously are the prime sum graphs, in the case where $$H=pG$$ for some prime number p. In this paper we present their structure and a detailed analysis of their properties. We also consider the simpler graph $$\varGamma ^+_{G,H}$$ , which we refer to as the extended subgroup sum graph, in which x and y are joined if $$x+y\in H$$ : the subgroup sum is obtained by removing from this graph the partial matching of edges having the form $$\{x,-x\}$$ when $$2x\ne 0$$ . We study perfectness, clique number and independence number, connectedness, diameter, spectrum, and domination number of these graphs and their complements. We interpret our general results in detail in the prime sum graphs.

A digraph D is supereulerian if D has a spanning eulerian subdigraph. We introduce some sufficient conditions for a digraph D to be supereulerian.

In this paper arithmetic progressions on the integers and the integers modulo n are extended to graphs. A k-term arithmetic progression of a graph G (k-AP) is a list of k distinct vertices such that the distance between consecutive pairs is constant. A rainbow k-AP is a k-AP where each vertex is colored distinctly. This allows for the definition of the anti-van der Waerden number of a graph G, which is the least positive integer r such that every exact r-coloring of G contains a rainbow k-AP. Much of the focus of this paper is on 3-term arithmetic progressions for which general bounds are obtained based on the radius and diameter of a graph. The general bounds are improved for trees and Cartesian products and exact values are determined for some classes of graphs. Longer k-term arithmetic progressions are considered and a connection between the Ramsey number of paths and the anti-van der Waerden number of graphs is established.Please confirm if the inserted city and country name for all affiliations is correct. Amend if necessary.The cities and affiliations are correct.

An edge-colored graph is called rainbow (or heterochromatic) if all its edges have distinct colors. It is known that if an edge-colored connected graph H has minimum color degree at least |H|/2 and has a certain property, then H has a rainbow spanning tree. In this paper, we prove that if an edge-colored connected bipartite graph G has minimum color degree at least |G|/3 and has a certain property, then G has a rainbow spanning tree. We also give a similar sufficient condition for G to have a properly colored spanning tree. Moreover, we show that these minimum color-degree conditions are sharp.

We investigate properties of sparse and tight surface graphs. In particular we derive topological inductive constructions for $$(2,2)$$ -tight surface graphs in the case of the sphere, the plane, the twice punctured sphere and the torus. In the case of the torus we identify all 116 irreducible base graphs and provide a geometric application involving contact graphs of configurations of circular arcs.

The notion of designs in an association scheme is defined algebraically by Delsarte [4]. It is known that his definition of designs has a geometric interpretation for known (P andQ)-polynomial association schemes except three examples. In this paper we give a geometric interpretation of designs in an association scheme of alternating bilinear forms, which is one of the three.