Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets

For every fixed graph H and every fixed 0 < α < 1, we show that if a graph G has the property that all subsets of size αn contain the “correct” number of copies of H one would expect to find in the random graph G(n,p) then G behaves like the random graph G(n,p); that is, it is p-quasi-random in the sense of Chung, Graham, and Wilson [4]. This solves a conjecture raised by Shapira [8] and solves in a strong sense an open problem of Simonovits and Sós [9].     

Circulant Double Coverings of a Circulant Graph of Valency Four

Several isomorphism classes of graph coverings of a graph G have been enumerated by many authors (see [3], [8]–[15]). A covering of G is called circulant if its covering graph is circulant. Recently, the authors [4] enumerated the isomorphism classes of circulant double coverings of a certain kind, called typical, and showed that no double covering of a circulant graph of valency 3 is circulant. In this paper, the isomorphism classes of connected circulant double coverings of a circulant graph of valency 4 are enumerated. As a consequence, it is shown that no double covering of a non-circulant graph G of valency 4 can be circulant if G is vertex-transitive or G has a prime power of vertices. The first author is supported by NSF of China (No. 60473019) and by NKBRPC (2004CB318000), and the second author is supported by Com²MaC-KOSEF (R11-1999-054) in Korea.     

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

On the prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis>) where <Emphasis Type="Italic">p</Emphasis> > 3 is a prime number

Let G be a finite group. We define the prime graph Γ(G) as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p, q are joined by an edge if there is an element in G of order pq. Recently M. Hagie [5] determined finite groups G satisfying Γ(G) = Γ(S), where S is a sporadic simple group. Let p > 3 be a prime number. In this paper we determine finite groups G such that Γ(G) = Γ(PSL(2, p)). As a consequence of our results we prove that if p > 11 is a prime number and p ≢ 1 (mod 12), then PSL(2, p) is uniquely determined by its prime graph and so these groups are characterizable by their prime graph. The third author was supported in part by a grant from IPM (No. 84200024).     

On some examples of duality groups

In [1, 3] it was shown: Theorem A. If G is the fundamental group of a finite graph of λ-dimensional duality groups with |G _o(e) : G _e | < ∞ and |G _τ(e) : G _e | < ∞ for every edge e of the corresponding G-tree, then G is an (λ + 1)-dimensional duality group. Here we use the methods of Brown and Geoghegan in [3] to obtain examples of duality groups under weaker conditions than those of Theorem A. Received: 5 June 2007     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

Graphs isomorphic to their maximum matching graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.     

On the Edge-forwarding Indices of Frobenius Graphs

A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay（K, S） for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as （N, R）, is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π（N） of a network （N, R）, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank（G） ≤ 50.     

The binding number of line graphs and total graphs

D.R. Woodall [7] introduced the concept of the binding number of a graphG, bind (G), and proved that bind(G)≦(|V(G)|−1)/(|V(G)|−ρ(G)). In this paper, some properties of a graph with bind(G)=(|V(G)|−1)/(|V(G)|−ρ(G)) are given, and the binding number of some line graphs and total graphs are determined.     

Complete partitions of graphs

A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition of G. This measure was defined in 1969 by Gupta [19], and is known to be NP-hard to compute for several classes of graphs. We obtain essentially tight lower and upper bounds on the approximability of this problem. We show that there is a randomized polynomial-time algorithm that given a graph G with n vertices, produces a complete partition of size Ω(cp(G)/√lgn). This algorithm can be derandomized. We show that the upper bound is essentially tight: there is a constant C > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph G with n vertices produces a complete partition into at least C·cp(G)/√lgn classes, then NP ⊆ RTime(n ^{O(lg lg n)}). The problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form Θ((lgn) ^c ) for some constant c strictly between 0 and 1. The work reported here is a merger of the results reported in [30] and [21].     

A Note on Range-Restricted Circuit Covers

 Let Cone(G), Int.Cone(G) and Lat(G) be the cone, the integer cone and the lattice of the incidence vectors of the circuits of graph G. A good range is a set ?⊆ℕ such that Cone (G)∩Lat (G)∩?^E⊆Int.Cone(G) for every graph G(V,E). We give a counterexample to a conjecture of Goddyn [1] stating that ℕ\{1} is a good range. Received: November 26, 1997     

On Connected [g,f +1]-Factors in Graphs

Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G), and g and f two positive integral functions from V (G) to Z⁺-{1} such that g(v) ≤ f(v) ≤ d_G(v) for all v ∈V (G), where d_G(v) is the degree of the vertex v. It is shown that every graph G, including both a [g,f]-factor and a hamiltonian path, contains a connected [g,f +1]-factor. This result also extends Kano’s conjecture concerning the existence of connected [k,k+1]-factors in graphs. * The work of this author was supported by NSFC of China under Grant No. 10271065, No. 60373025. † The work of these authors was also supported in part by the US Department of Energy’s Genomes to Life program (http://doegenomestolife.org/) under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org) and by National Science Foundation (NSF/DBI-0354771,NSF/ITR-IIS-0407204).     

AVDTC Numbers of Generalized Halin Graphs with Maximum Degree at Least 6

In a paper by Zhang and Chen et al.（see [11]）, a conjecture was made concerning the minimum number of colors Xat（G） required in a proper total-coloring of G so that any two adjacent vertices have different color sets, where the color set of a vertex v is the set composed of the color of v and the colors incident to v. We find the exact values of Xat（G） and thus verify the conjecture when G is a Generalized Halin graph with maximum degree at least 6, A generalized Halin graph is a 2-connected plane graph G such that removing all the edges of the boundary of the exterior face of G （the degrees of the vertices in the boundary of exterior face of G are all three） gives a tree.     

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only:

On the Neighbour-Distinguishing Index of a Graph

A proper edge colouring of a graph G is neighbour-distinguishing provided that it distinguishes adjacent vertices by sets of colours of their incident edges. It is proved that for any planar bipartite graph G with Δ(G)≥12 there is a neighbour-distinguishing edge colouring of G using at most Δ(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Minimally Non-Preperfect Graphs of Small Maximum Degree

 A graph G is called preperfect if each induced subgraph G ^′⊆G of order at least 2 has two vertices x, y such that either all maximum cliques of G ^′ containing x contain y, or all maximum independent sets of G ^′ containing y contain x, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199–208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: (i) A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. (ii) If a graph G is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if G is bipartite, 3-edge-connected, regular of degree d for some d≥3, and contains no 3-edge-connected d ^′-regular subgraph for any 3≤d ^′<d. Received: March 4, 1998 Final version received: August 14, 1999     

Total Colorings Of Degenerate Graphs

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.     

The co-degrees of irreducible characters

LetG be a finite group. The co-degree of an irreducible character χ ofG is defined to be the number |G|/χ(1). The set of all prime divisors of all the co-degrees of the nonlinear irreducible characters ofG is denoted by Σ(G). First we show that Σ(G)=π(G) (the set of all prime divisors of |G|) unlessG is nilpotent-by-abelian. Then we make Σ(G) a graph by adjoining two elements of Σ(G) if and only if their product divides a co-degree of some nonlinear character ofG. We show that the graph Σ(G) is connected and has diameter at most 2. Additional information on the graph is given. These results are analogs to theorems obtained for the graph corresponding to the character degrees (by Manz, Staszewski, Willems and Wolf) and for the graph corresponding to the class sizes (by Bertram, Herzog and Mann). Finally, we investigate groups with some restriction on the co-degrees. Among other results we show that ifG has a co-degree which is ap-power for some primep, then the corresponding character is monomial andO _p (G)≠1. Also we describe groups in which each co-degree of a nonlinear character is divisible by at most two primes. These results generalize results of Chillag and Herzog. Other results are proved as well. The paper was written during this author’s visit at the Technion and the University of Tel Aviv. He would like to thank the departments of mathematics at the Technion and the University of Tel Aviv for their hospitality and support.     

Zero-Sum Flows in Regular Graphs

For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)²-flow. Finally, the existence of k-flows for small graphs is investigated.