On graph invariants satisfying the deletion-contraction formula

As a generalization of chromatic polynomials, this paper deals with real-valued mappings ψ on the class of graphs satisfying ψ(G₁) = ψ(G₂) for all pairs G₁, G₂ of isomorphic graphs and ψ(G) = ψ(G − e) − ψ(G/e) for all graphs G and all edges e of G, where the definition of G/e is nonstandard. In particular, new inequalities for chromatic polynomials are presented. © 1996 John Wiley & Sons, Inc.     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

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.     

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     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Proof of a conjecture on game domination

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b‐dimensional cube is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b‐dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line—i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number ψ(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least ?log₂ψ(G)?. In this article, we show that for an interval graph G ?log₂ψ(G)??cub(G)??log₂ψ(G)?+2. It is not clear whether the upper bound of ?log₂ψ(G)?+2 is tight: till now we are unable to find any interval graph with cub(G)>?log₂ψ(G)?. We also show that for an interval graph G, cub(G)??log₂α?, where α is the independence number of G. Therefore, in the special case of ψ(G)=α, cub(G) is exactly ?log₂α₂?. The concept of cubicity can be generalized by considering boxes instead of cubes. A b‐dimensional box is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k‐dimensional boxes. It is clear that box(G)?cub(G). From the above result, it follows that for any graph G, cub(G)?box(G)?log₂α?. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323–333, 2010     

Crossing properties of graph reliability functions

Let G be a graph and p ϵ (0, 1). Let A(G, p) denote the probability that if each edge of G is selected at random with probability p then the resulting spanning subgraph of G is connected. Then A(G, p) is a polynomial in p. We prove that for every integer k ≥ 1 and every k‐tuple (m₁, m₂, … ,m_k) of positive integers there exist infinitely many pairs of graphs G₁ and G₂ of the same size such that the polynomial A(G₁, p) − A(G₂, p) has exactly k roots x₁ < x₂ < ··· < x_k in (0, 1) such that the multiplicity of x_i is m_i. We also prove the same result for the two‐terminal reliability polynomial, defined as the probability that the random subgraph as above includes a path connecting two specified vertices. These results are based on so‐called A‐ and T‐multiplying constructions that are interesting in themselves. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 206–221, 2000     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Divisibility and structure constraints on automorphism groups of almost perfect 1-factorizations of

Let G be a permutation group acting on a set with N elements such that every permutation with more than m fixed points is the identity. It is easy to verify that |G| divides N(N − 1) ··· (N − m). We show that if gcd(|G|, m!) = 1, then |G| divides (N − i)(N − j) for some i and j satisfying 0 ≤ i < j ≤ m. We use this to show that any almost perfect 1-factorization of K_2n has an automorphism group whose cardinality divides (2n − i)(2n − j) for some i and j with 0 ≤ i < j ≤ 2 as long as n is odd. An almost perfect 1-factorization (or APOF) is a 1-factorization in which the union of any three distinct 1-factors is connected. This result contrasts with an example of an APOF on K₁₂ given by Cameron which has PSL(2, ℤ₁₁) as its automorphism group [with cardinality 12(11)(5)]. When n is even and the automorphism group is solvable, we show that either G acts vertex transitively and n is a power of two, or |G| divides 2n − 2^a for some integer a with 2^a dividing 2n, or else |G| divides (2n − i)(2n − j) for some i and j with 0 ≤ i < j ≤ 2. We also give a number of structure results concerning these automorphism groups. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 355–380, 1998     

On vertex-coloring edge-weighting of graphs

A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ _e∋u w(e) for every u ∈ V (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.      

Sequences realizable by maximal k-degenerate graphs

A graph G is called k-degenerate if every subgraph of G has a vertex of degree at most k. A k-degenerate graph G is maximal k-degenerate if for every edge e ? E(G), G + e is not k-degenerate. Necessary and sufficient conditions for the sequence II = (d₁, d₂, ?, d_p) to be a degree sequence of a maximal k-degenerate graph G are presented. © 1995 John Wiley & Sons, Inc.     

On point-halfspace graphs

The following definition is motivated by the study of circle orders and their connections to graphs. A graphs G is called a point-halfspace graph (in R ^k) provided one can assign to each vertex v ? (G) a point p _v R ^k and to each edge e ? E(G) a closed halfspace H_e ? R ^k so that v is incident with e if and only if p _v ? H_e. Let H ^k denote the set of point-halfspace graphs (in R ^k). We give complete forbidden subgraph and structural characterizations of the classes H ^k for every k. Surprisingly, these classes are closed under taking minors and we give forbidden minor characterizations as well. © 1996 John Wiley & Sons, Inc.     

Dependent percolation in two dimensions

For a natural number k, define an oriented site percolation on ℤ² as follows. Let x _i , y _j be independent random variables with values uniformly distributed in {1, …, k}. Declare a site (i, j) ∈ℤ² closed if x _i = y _j , and open otherwise. Peter Winkler conjectured some years ago that if k≥ 4 then with positive probability there is an infinite oriented path starting at the origin, all of whose sites are open. I.e., there is an infinite path P = (i ₀, j ₀)(i ₁, j ₁) · · · such that 0 = i ₀≤i ₁≤· · ·, 0 = j ₀≤j ₁≤· · ·, and each site (i _n , j _n ) is open. Rather surprisingly, this conjecture is still open: in fact, it is not known whether the conjecture holds for any value of k. In this note, we shall prove the weaker result that the corresponding assertion holds in the unoriented case: if k≤ 4 then the probability that there is an infinite path that starts at the origin and consists only of open sites is positive. Furthermore, we shall show that our method can be applied to a wide variety of distributions of (x _i ) and (y _j ). Independently, Peter Winkler [14] has recently proved a variety of similar assertions by different methods. Received: 4 March 1999 / Revised version: 27 September 1999 / Published online: 21 June 2000     

Finite Groups with Conjugacy Classes Number One Greater than Its Same Order Classes Number

ABSTRACT

Let k(G) be the number of conjugacy classes of finite groups G and π _e (G) be the set of the orders of elements in G. Then there exists a non-negative integer k such that k(G) = |π _e (G)| + k. We call such groups to be co(k) groups. This article classifies all finite co(1) groups. They are isomorphic to one of the following groups: A ₅, L ₂(7), S ₅, Z ₃, Z ₄, S ₄, A ₄, D ₁₀, Hol(Z ₅), or Z ₃ ? Z ₄.     

The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,G _k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G ₁), d(e, G ₂),…,d(e, G _k )), where d(e, G _i ) is the distance from e to G _i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K _n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999     

An asymptotically tight bound on the adaptable chromatic number

The adaptable chromatic number of a multigraph G, denoted χ_a(G), is the smallest integer k such that every edge labeling, τ, of G from [k] = {1, 2, …, k} permits a vertex coloring, σ, of G from [k] such that no edge e = uv has τ(e) = σ(u) = σ(v). Hell and Zhu proved that for any multigraph G with maximum degree Δ, the adaptable chromatic number is at most . We strengthen this to the asymptotically best possible bound of for any ?>0. © 2012 Wiley Periodicals, Inc. J Graph Theory     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.