On the Interval Number of a Triangulated Graph

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices v and w of G are adjacent if and only if some interval for v intersects some interval for w. For triangulated graphs G, we consider the problem of finding a sharp upper bound for the interval number of G in terms of its clique number ω(G). The following partial results are proved. (1) For each triangulated graph G, i(G) ? ?ω(G)/2? + 1, and this is best possible for 2 ? ω(G) ? 6. (2) For each integer m ? 2, there exists a triangulated graph G with ω(G) = m and i(G) > m^1/2.     

On the number of colorings of a snark minus an edge

For a given snark G and a given edge e of G, let ψ(G, e) denote the nonnegative integer such that for a cubic graph conformal to G – {e}, the number of Tait colorings with three given colors is 18 · ψ(G, e). If two snarks G₁ and G₂ are combined in certain well‐known simple ways to form a snark G, there are some connections between ψ (G₁, e₁), ψ (G₂, e₂), and ψ(G, e) for appropriate edges e₁, e₂, and e of G₁, G₂, and G. As a consequence, if j and k are each a nonnegative integer, then there exists a snark G with an edge e such that ψ(G, e) = 2^j · 3^k. © 2005 Wiley Periodicals, Inc.     

On Groups with the Second Largest Value of the Sum of Element Orders

For a finite group G, let ψ(G) denote the sum of element orders of G. It is known that the maximum value of ψ on the set of groups of order n, where n is a positive integer, will occur at the cyclic group ? _n . In this paper, we investigate groups with the second largest value of ψ on the set of groups of the same order.     

Dividing a graph by degrees

For a general graph G and integer k, the paper proves the existence of a decomposition of G into k G subgraphs whose degrees are close to of the corresponding degrees in G and each subgraph has approximately edges. © 1996 John Wiley & Sons, Inc.     

Gallai–Ramsey numbers for cycles

For given graphs G and H and an integer k, the Gallai–Ramsey number is defined to be the minimum integer n such that, in any k coloring of the edges of K_n, there exists a subgraph isomorphic to either a rainbow coloring of G or a monochromatic coloring of H. In this work, we consider Gallai–Ramsey numbers for the case when G=K₃ and H is a cycle of a fixed length.     

On the size of graphs labeled with a condition at distance two

A labeling of graph G with a condition at distance two is an integer labeling of V(G) such that adjacent vertices have labels that differ by at least two, and vertices distance two apart have labels that differ by at least one. The lambda-number of G, λ(G), is the minimum span over all labelings of G with a condition at distance two. Let G(n, k) denote the set of all graphs with order n and lambda-number k. In this paper, we examine the sizes of graphs in G(n, k). We modify Chvàtal's result on non-hamiltonian graphs to obtain a formula for the minimum size of a graph in G(n, k), and we use an algorithmic approach to obtain a formula for the maximum size. Finally, we show that for any integer j between the maximum and minimum sizes there exists a graph with size j in G(n, k). © 1996 John Wiley & Sons, Inc.     

On longest cycles and strongly linking vertex sets

Let G be a simple non-hamiltonian graph, let C be a longest cycle in G, and let p be a positive integer. By considering a special form of connectivity, we obtain a sufficient condition on degrees for the nonexistence of (p - 1)-path-connected components in G - C.     

On Finite Groups and the Small Square Property

Let G be a finite group written multiplicatively and k a positive integer. If X is a non-empty subset of G, write X ² = |xy | x, y X . We say that G has the small square property on k-sets if |X ²| < k ² for any k-element subset X of G. For each group G, there is a unique m = m _G such that G has the small square property on (m + 1)-sets but not on m-sets. In this paper we show that given any positive integer d, there is a finite group G with m _G = d.     

Cycle lengths in graphs with large minimum degree

Our main result is the following theorem. Let k ≥ 2 be an integer, G be a graph of sufficiently large order n, and δ(G) ≥ n/k. Then:

• (i) G contains a cycle of length t for every even integer t ∈ [4, δ(G) + 1].
• (ii) If G is nonbipartite then G contains a cycle of length t for every odd integer t ∈ [2k ? 1, δ(G) + 1], unless k ≥ 6 and G belongs to a known exceptional class.

© 2006 Wiley Periodicals, Inc. J Graph Theory 52: 157–170, 2006     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

The Ramsey property for graphs with forbidden complete subgraphs

The following theorem is proved: Let G be a finite graph with cl(G) = m, where cl(G) is the maximum size of a clique in G. Then for any integer r ≥ 1, there is a finite graph H, also with cl(H) = m, such that if the edges of H are r-colored in any way, then H contains an induced subgraph G′ isomorphic to G with all its edges the same color.     

Decomposition of Graphs into (g, f)-Factors

Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg _G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results. Revised: June 11, 1998     

First Hitting Times for Some Random Walks on Finite Groups

We consider a random walk on a finite group G based on a generating set that is a union of conjugacy classes. Let the nonnegative integer valued random variable T denote the first time the walk arrives at the identity element of G, if the starting point of the walk is uniformly distributed on G. Under suitable hypotheses, we show that the distribution function F of T is almost exponential, and we give an error term.     

Some Algebraic Methods for Calculating the Number of Colorings of a Graph

With an arbitrary graph G having n vertices and m edges, and with an arbitrary natural number p, we associate in a natural way a polynomial R(x ₁,...,x _n) with integer coefficients such that the number of colorings of the vertices of the graph G in p colors is equal to p ^m-n R(0,...,0). Also with an arbitrary maximal planar graph G, we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph G in 3 colors can be calculated in several ways via the coefficients of each of these polynomials. Bibliography: 2 titles.     

The Conjugacy Class Number k(G): A Different Perspective

For a finite group G, let m(G) denote the least positive integer such that the union of any m(G) distinct nontrivial conjugacy classes of G together with the identity of G is a subgroup of G. We prove that m(G) = k(G) ?1 for all m(G) ≥2.     

Non-traceability of large connected claw-free graphs

Let G be a connected claw-free graph on n vertices. Let ς₃(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς₃(G) ≥ n − 3 then G is traceable or else G is one of graphs G_n each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K₃. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς₃(G) ≥ n − k, n > ν(k) and G is non-traceable, then G is a factor of a graph G_n. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς₃(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998     

Randomness friendly graphs

We consider the two problems from extremal graph theory: 1. Given integer N, real p ϵ (0, 1) and a graph G, what is the minimum number of copies of G a graph H with N vertices and pN²/2 edges can contain? 2. Given an integer N and a graph G, what is the minimum number of copies of G an N-vertex graph H and its complement H¯ can contain altogether? In each of the problems, we say that G is “randomness friendly” if the number of its copies is nearly minimal when H is the random graph. We investigate how the two classes of graphs are related: the graphs which are “randomness friendly” in Problem 1 and those of Problem 2. In the latter problem, we discover new families of graphs which are “randomness friendly.” © 1996 John Wiley & Sons, Inc.     

Exotic n-universal graphs

An n-universal graph is a graph that contains as an induced subgraph a copy of every graph on n vertices. It is shown that for each positive integer n > 1 there exists an n-universal graph G on 4ⁿ - 1 vertices such that G is a (v, k, λ)-graph, and both G and its complement G¯ are 1-transitive in the sense of W. T. Tutte and are of diameter 2. The automorphism group of G is a transitive rank 3 permutation group, i.e., it acts transitively on (1) the vertices of G, (2) the ordered pairs uv of adjacent vertices of G, and (3) the ordered pairs xy of nonadjacent vertices of G.     

On Engel Elements of a Group Relative to Certain Subgroup

An element g in a group G is called a left Engel element of G, if for each x ∈ G, there is a positive integer n = n(g, x) such that [x, _n g] = 1. In this article, we will study a generalization of the left Engel elements and its connections with the generalized Hirsch–Plotkin and Baer radical.     

Some results on the achromatic number

Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ (T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ϵ > 0, we show that there is an integer N₀ = N₀(d, ϵ) such that if G is a graph with maximum degree at most d, and m ≥ N₀ edges, then (1 - ϵ)q(m) ≤ ψ (G) ≤ q(m). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 129–136, 1997