Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

The isomorphism classes of the generalized Petersen graphs

In earlier work involving cycles in Generalized Petersen Graphs, we noticed some unexpected instances of P(m,k)≅P(m,l). In this article, all such instances are characterized. A formula is presented for the number of isomorphism classes of P(m,k).     

Switching classes of directed graphs

By analogy with Seidel switching classes of graphs, and two-graphs, this paper develops a theory of switching classes of directed graphs. The elements of the theory are these: there is a one-to-one correspondence among switching classes of directed graphs, two-digraphs, and cyclic triple covers of the complete digraph. If G is a group of automorphisms of a switching class of digraphs, there is a cohomological invariant γ which vanishes if and only if some digraph in the switching class is fixed by G. If G is cyclic then γ ≠ 0 if and only if all orbits on vertices have size divisible by 3 and a certain sum (defined in Theorem 3.5) is nonzero. There is a second cohomological invariant β which vanishes if and only if G can be realized as a group of automorphisms of the cyclic triple cover associated with the switching class. If G is cyclic, then β ≠ 0 if and only if G has a subgroup of order 3 for which γ ≠ 0. There is a formula for the number of isomorphism types of two-digraphs on n vertices which is a sum over the symmetric group S_n of a simple function of the cycle structure of its elements. Finally, the only elements of S_n which fix a digraph in every switching class of digraphs they fix are those elements containing a cycle whose length is not divisible by 3.     

Some classes of perfectly orderable graphs

In 1981, Chvátal defined the class of perfectly orderable graphs. This class of perfect graphs contains the comparability graphs and the triangulated graphs. In this paper, we introduce four classes of perfectly orderable graphs, including natural generalizations of the comparability and triangulated graphs. We provide recognition algorithms for these four classes. We also discuss how to solve the clique, clique cover, coloring, and stable set problems for these classes.     

Coloring some classes of mixed graphs

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [x_i,x_j], c(x_i)≠c(x_j) and for every arc (x_p,x_q), c(x_p)<c(x_q). We will analyse the complexity status of this problem for some special classes of graphs.     

k-Bounded classes of dominant-independent perfect graphs

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi(k) = {G : α(H) − i(H) ≤ k for every H ∈ ISub(G)}; αγ(k) = {G : α(H) − γ(H) ≤ k for every H ∈ ISub(G)}; and iγ(k) = {G : i(H) − γ(H) ≤ k for every H ∈ ISub(G)}, where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a finite forbidden induced subgraph characterization for αi(k) and αγ(k) for any k ≥ 0. We conjecture that iγ(k) also has such a characterization. Up to the present, it is known only for iγ(0) (domination perfect graphs [Zverovich & Zverovich, J Graph Theory 20 (1995), 375–395]). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 303–310, 1999     

On classes of minimal circular-imperfect graphs

Circular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ(G)?ω(G)+1.The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs.At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

Some globally determined classes of graphs

For a class of graphs we say that it is globally determined if any two nonisomorphic graphs from that class have nonisomorphic globals. We will prove that the class of so called CCB graphs and the class of finite forests are globally determined.     

Some results on strongly regular graphs from unions of cyclotomic classes

In this paper, we construct some families of strongly regular graphs on finite fields by using unions of cyclotomic classes and index 2 Gauss sums. New infinite families of strongly regular graphs are found.     

The isomorphism problem for classes of graphs closed under contraction

We consider the isomorphism problem for graphs in classes which, together with any graph, contain its connected induced subgraphs and graphs obtained by successive identifications of endpoints of edges. The main result is to establish sufficient conditions for the existence of a polynomial time algorithm testing graphs of such classes for isomorphism. It is shown that classes failing to satisfy these conditions are isomorphism-complete.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 147–177, 1988.     

Labelings of two classes of plane graphs

The paper describes magic labelings of type (1,1,1) for two classes of graphs, which are obtained by a combination of vertex, edge and face labelings.     

Coloring graphs of various maximum degree from random lists

Let G = G(n) be a graph on n vertices with maximum degree Δ =Δ (n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k‐subsets of a color set of size . Such a list assignment is called a random ‐list assignment. In this paper, we are interested in determining the asymptotic probability (as n →∞) of the existence of a proper coloring φ of G, such that for every vertex v of G, a so‐called L‐coloring. We give various lower bounds on σ, in terms of n, k, and Δ, which ensures that with probability tending to 1 as n →∞ there is an L‐coloring of G. In particular, we show, for all fixed k and growing n, that if and , then the probability that G has an L‐coloring tends to 1 as . If and , then the same conclusion holds provided that . We also give related results for other bounds on Δ, when k is constant or a strictly increasing function of n.