Graphs with eigenvalues at least −2

The family of minimal forbidden graphs for the set of graphs with all eigenvalues at least ?2 is described. It is shown that each minimal forbidden graph has at most 10 vertices and the bound is the best possible.     

A Note on Group Choosability of Graphs with Girth at least 4

In this paper we show that the group choice number of a graph without K ₅-minor or K _3,3-minor with girth at least 4 (resp. 6) is at most 4 (resp. 3) and we conclude that these results hold for the group chromatic number, the choice number and the chromatic number.     

On 3-regular graphs having crossing number at least 2

We give a planar proof of the fact that if G is a 3-regular graph minimal with respect to having crossing number at least 2, then the crossing number of G is 2.     

Graphs with cycles having adjacent lines different colors

If the lines of the complete graph on p≥6 points are colored so no point is on more than two lines of the same color, then for 3≤n≤p there is a cycle of length n with adjacent lines different colors.     

Graphs with Hamiltonian cycles having adjacent lines different colors

Let G be a complete graph K_p (or a complete bipartite graph K_m,m) with its lines colored so that no point is on more than k lines of the same color. If p ≥ 17k (or m ≥ 25k) then G has a cycle of every possible size with adjacent lines different colors.     

Polyhedral sets having a least element

For a fixedm × n matrixA, we consider the family of polyhedral setsX _b ={x|Ax b}, b R ^m , and prove a theorem characterizing, in terms ofA, the circumstances under which every nonemptyX _b has a least element. In the special case whereA contains all the rows of ann × n identity matrix, the conditions are equivalent toA ^T being Leontief. Among the corollaries of our theorem, we show the linear complementarity problem always has a unique solution which is at the same time a least element of the corresponding polyhedron if and only if its matrix is square, Leontief, and has positive diagonals.This research was supported by the National Science Foundation under Grants GK-18339 and GP-25738, by the Office of Naval Research under Contracts N00014-67-A-0112-0050 (NR-042-264) and N00014-67-A-0112-0011, and by the IBM Corporation. Part of the second author's contribution to this paper was made while he was on sabbatical leave in 1968–9 as a consultant to the IBM Research Center. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

The tricriterion shortest path problem with at least two bottleneck objective functions

The focus of this paper is on the tricriterion shortest path problem where two objective functions are of the bottleneck type, for example MinMax or MaxMin. The third objective function may be of the same kind or we may consider, for example, MinSum or MaxProd. Let p(n) be the complexity of a classical single objective algorithm responsible for this third function, where n is the number of nodes and m be the number of arcs of the graph. An O(m²p(n)) algorithm is presented that can generate the minimal complete set of Pareto-optimal solutions. Finding the maximal complete set is also possible. Optimality proofs are given and extensions for several special cases are presented. Computational experience for a set of randomly generated problems is reported.     

Directed cycles with chords

Using a variation of Thomassen's admissible triples technique, we give an alternative proof that every strongly 2‐arc‐connected directed graph with two or more vertices contains a directed cycle that has at least two chords, while at the same time establishing a more general result. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:17–28, 1999     

Graphs with given odd sets and the least number of vertices

This note presents a solution to the following problem posed by Chen, Schelp, and Šoltés: find a simple graph with the least number of vertices for which only the degrees of the vertices that appear an odd number of times are given. © 1997 John Wiley & Sons, Inc.     

Exceptional Dehn fillings on hyperbolic 3-manifolds with at least two boundary components

We estimate the number of exceptional slopes for hyperbolic 3-manifolds with a torus boundary component and at least one other boundary component.     

Graphs with vertex rainbow connection number two

An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.     

Graphs with at most one crossing

The crossing number of a graph $G$ is the least number of crossings over all possible drawings of $G$. We present a structural characterization of graphs with crossing number one.     

Graphs with Branchwidth at Most Three

In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition.     

Flat projective planes with 2-dimensional collineation group fixing at least two lines and more than two points

All flat projective planes whose collineation group contains a 2-dimensional subgroup fixing at least two lines and more than two points are classified. Furthermore, all isomorphism types of such planes are determined. This completes the classification of all flat projective planes admitting a 2-dimensional collineation group.     

Graphs of diameter two with no 4-circuits

We characterize the simple finite graphs with diameter two and no 4-circuits by showing that every such graph falls into one of three well-defined classes.     

Graphs for which the least eigenvalue is minimal, I

Let G be a connected graph whose least eigenvalue λ(G) is minimal among the connected graphs of prescribed order and size. We show first that either G is complete or λ(G) is a simple eigenvalue. In the latter case, the sign pattern of a corresponding eigenvector determines a partition of the vertex set, and we study the structure of G in terms of this partition. We find that G is either bipartite or the join of two graphs of a simple form.