Cubic graphs with crossing number two

It is proved that every cubic graph with crossing number at least two contains a subdivision of one of eight graphs.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

A characterization of graphs of competition number m

In this note we give a characterization of graphs with competition number less than or equal to m. We also give an alternate proof of a theorem characterizing competition graphs.     

Threshold tolerance graphs

In this paper, we introduce a class of graphs that generalize threshold graphs by introducing threshold tolerances. Several characterizations of these graphs are presented, one of which leads to a polynomial-time recognition algorithm. It is also shown that the complements of these graphs contain interval graphs and threshold graphs, and are contained in the subclass of chordal graphs called strongly chordal graphs, and in the class of interval tolerance graphs.     

Some graphs with chromatic number three

A question of P. Erdös is solved by showing that certain graphs have chromatic number at most three. The proof proceeds by showing a conjecture of Erdös and Bollobás holds, namely, that under certain circumstances, a graph which contains an odd circuit must contain an odd circuit with diagonal.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

Sweeping graphs with large clique number

Searching a network for intruders is an interesting and often difficult problem. Sweeping (or edge searching) is one such search model, in which intruders may exist anywhere along an edge. It was conjectured that graphs exist for which the connected sweep number is strictly less than the monotonic connected sweep number. We prove that this is true, and the difference can be arbitrarily large. We also show that the clique number is a lower bound on the sweep number.     

The distinguishing chromatic number of Cartesian products of two complete graphs

A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.     

Extremal graphs with prescribed covering number

We show that any connected graph with ? edges and covering number β satisfies the inequality ? ≥ 2β ? 1. The graphs for which equality holds are characterized.     

Dense graphs with small clique number

We consider the structure of K_r‐free graphs with large minimum degree, and show that such graphs with minimum degree δ>(2r ? 5)n/(2r ? 3) are homomorphic to the join K_{r ? 3}∨H, where H is a triangle‐free graph. In particular this allows us to generalize results from triangle‐free graphs and show that K_r‐free graphs with such a minimum degree have chromatic number at most r +1. We also consider the minimum‐degree thresholds for related properties. Copyright © 2010 John Wiley & Sons, Ltd. 66:319‐331, 2011     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

A note on acyclic domination number in graphs of diameter two

A subset S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γ_a(G), is called the acyclic domination number of G. Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151-165] introduced the concept of acyclic domination and posed the following open problem: if δ(G) is the minimum degree of G, is γ_a(G)?δ(G) for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive k, there is a graph G with diameter two such that γ_a(G)-δ(G)?k.     

A characterization of two classes of strongly regular graphs

The half dual polar graphsD _4,4(q) and the alternating forms graphsAlt(4,q) are characterized among strongly regular graphs with classical parameters via the geometric structures of polar spaces and affine polar spaces of rank 4, respectively.