A note on the valence of certain means

Given two functionsf(z),g(z) in the (usual) classS, we can form the new functions (arithmetric and geometric mean functions) F(itz)=∝(itf)(itz)+β(itg)(itz) and G(itz)=(itz)(f(itz)/(itz))(su∝)(g(itz)/(itz))(suβ), whereα, β ∈ (0, 1) andα+β=1. This paper determines the maximum valence of the functionsF andG.     

Crossing numbers of graph embedding pairs on closed surfaces

We shall prove that any two graphs G₁ and G₂ can be embedded together on a closed surface of genus g with at most 4g · β(G₁) · β(G₂) crossing points on their edges if they are embeddable on the surface, where β(G) stands for the Betti number of G, and show several observations on crossings of graph embedding pairs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 8–23, 2001     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

2‐ and 3‐factors of graphs on surfaces

It has been conjectured that any 5‐connected graph embedded in a surface Σ with sufficiently large face‐width is hamiltonian. This conjecture was verified by Yu for the triangulation case, but it is still open in general. The conjecture is not true for 4‐connected graphs. In this article, we shall study the existence of 2‐ and 3‐factors in a graph embedded in a surface Σ. A hamiltonian cycle is a special case of a 2‐factor. Thus, it is quite natural to consider the existence of these factors. We give an evidence to the conjecture in a sense of the existence of a 2‐factor. In fact, we only need the 4‐connectivity with minimum degree at least 5. In addition, our face‐width condition is not huge. Specifically, we prove the following two results. Let G be a graph embedded in a surface Σ of Euler genus g.

• (1) If G is 4‐connected and minimum degree of G is at least 5, and furthermore, face‐width of G is at least 4g?12, then G has a 2‐factor.
• (2) If G is 5‐connected and face‐width of G is at least max{44g?117, 5}, then G has a 3‐factor.

The connectivity condition for both results are best possible. In addition, the face‐width conditions are necessary too. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 67:306‐315, 2011     

The road-colouring problem

LetG be a finite directed graph which is irreducible and aperiodic. Assume each vertex ofG leads to at least two other vertices, and assumeG has a cycle of prime length which is a proper subset ofG. Then there exist two functionsr:G →G andb:G →G such that ifr(x)=y andb(x)=z thenx →y andx →z inG andy ≠z and such that some composition ofr’s andb’s is a constant function. This work was supported in part by the Natural Sciences and Engineering Research Council of Canada. I am grateful to Cornell University whose kind hospitality I enjoyed while working on this problem.     

Balanced and 1-balanced graph constructions

There are several density functions for graphs which have found use in various applications. In this paper, we examine two of them, the first being given by b(G)=|E(G)|/|V(G)|, and the other being given by g(G)=|E(G)|/(|V(G)|−ω(G)), where ω(G) denotes the number of components of G. Graphs for which b(H)≤b(G) for all subgraphs H of G are called balanced graphs, and graphs for which g(H)≤g(G) for all subgraphs H of G are called 1-balanced graphs (also sometimes called strongly balanced or uniformly dense in the literature). Although the functions b and g are very similar, they distinguish classes of graphs sufficiently differently that b(G) is useful in studying random graphs, g(G) has been useful in designing networks with reduced vulnerability to attack and in studying the World Wide Web, and a similar function is useful in the study of rigidity. First we give a new characterization of balanced graphs. Then we introduce a graph construction which generalizes the Cartesian product of graphs to produce what we call a generalized Cartesian product. We show that generalized Cartesian product derived from a tree and 1-balanced graphs are 1-balanced, and we use this to prove that the generalized Cartesian products derived from 1-balanced graphs are 1-balanced.     

Some results on R 2-edge-connectivity of even regular graphs

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials

Lovász and Schrijver (SIAM J. Optim. 1:166–190, 1991) have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most α(G) steps, where α(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre (SIAM J. Optim. 11:796–817, 2001; Lecture Notes in Computer Science, Springer, Berlin Heidelberg New York, pp 293–303, 2001) and by de Klerk and Pasechnik (SIAM J. Optim. 12:875–892), which are based on relaxing nonnegativity of a polynomial by requiring the existence of a sum of squares decomposition. The hierarchy of Lasserre is known to converge in α(G) steps as it refines the hierarchy of Lovász and Schrijver, and de Klerk and Pasechnik conjecture that their hierarchy also finds the stability number after α(G) steps. We prove this conjecture for graphs with stability number at most 8 and we show that the hierarchy of Lasserre refines the hierarchy of de Klerk and Pasechnik.      

K‐linked graphs with girth condition

Recently, Mader [ 7 ] proved that every 2k‐connected graph with girth g(G) sufficiently large is k‐linked. We show here that g(G ≥ 11 will do unless k = 4,5. If k = 4,5, then g(G) ≥ 19 will do. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 48–50, 2004     

Cyclic orthogonal double covers of 4-regular circulant graphs

An orthogonal double cover (ODC) of a graph H is a collection G={G_v:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members G_u and G_v in G, |E(G_u)∩E(G_v)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs.     

Local linear operators and multicontour solutions of homogeneous coupled map lattices

Theorems are proved establishing a relationship between the spectra of the linear operators of the formA+Ωg _iB_ig_i ⁻¹ andA+B _i, whereg _i∈G, andG is a group acting by linear isometric operators. It is assumed that the closed operatorsA andB _i possess the following property: ‖B _iA⁻¹gB_jA⁻¹‖→0 asd(e,g)→∞. Hered is a left-invariant metric onG ande is the unit ofG. Moreover, the operatorA is invariant with respect to the action of the groupG. These theorems are applied to the proof of the existence of multicontour solutions of dynamical systems on lattices. Translated fromMatematicheskie Zametki, Vol. 65, No. 1, pp. 37–47, January, 1999.     

Character formulae for classical groups

We give formulae relating the value X_λ (g) of an irreducible character of a classical group G to entries of powers of the matrix g ε G. This yields a far-reaching generalization of a result of J.L. Cisneros-Molina concerning the GL ₂ case [1]. Partially supported by OTKA grants T 042769 and T 046365     

A note on transformations of edge colorings of bipartite graphs

The author and A. Mirumian proved the following theorem: Let G be a bipartite graph with maximum degree Δ and let t,n be integers, tnΔ. Then it is possible to obtain, from one proper edge t-coloring of G, any proper edge n-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the intermediate colorings are also proper. In this note we show that if t>Δ then we can transform f to g using only transformations of 2-colored subgraphs. We also correct the algorithm suggested in [A.S. Asratian, Short solution of Kotzig's problem for bipartite graphs, J. Combin. Theory Ser. B 74 (1998) 160–168] for transformation of f to g in the case when t=n=Δ and G is regular.     

Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000     

Extending colorings of locally planar graphs

Suppose G is a graph embedded in S_g with width (also known as edge width) at least 264(2^g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G. We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on S_g with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

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     

Strict Dead-End Elements in Free Soluble Groups

Let G be a group generated by a finite set A. An element g ∈ G is a strict dead end of depth k (with respect to A) if |g|>|ga ₁|>|ga ₁ a ₂|>···>|ga ₁ a ₂… a _k | for any a ₁, a ₂,…, a _k  ∈ A ^±1 such that the word a ₁ a ₂… a _k is freely irreducible. (Here |g| is the distance from g to the identity in the Cayley graph of G.) We show that in finitely generated free soluble groups of degree d ≥ 2 there exist strict dead elements of depth k = k(d), which grows exponentially with respect to d.     

Unitary units in modular group algebras

Letp be a prime,K a field of characteristicp, G a locally finitep-group,KG the group algebra, andV the group of the units ofKG with augmentation 1. The anti-automorphismg→g ⁻¹ ofG extends linearly toKG; this extension leavesV setwise invariant, and its restriction toV followed byv→v ⁻¹ gives an automorphism ofV. The elements ofV fixed by this automorphism are calledunitary; they form a subgroup. Our first theorem describes theK andG for which this subgroup is normal inV. For each elementg inG, let denote the sum (inKG) of the distinct powers ofg. The elements 1+(g-1) withh,hεG are thebicyclic units ofKG. Our second theorem describes theK andG for which all bicyclic units are unitary. Research partly supported by the Hungarian National Foundation for Scientific Research grant no. T4265. The second author is indebted to the ‘Universitas’ Foundation and the Lajos Kossuth University of Debrecen, Hungary, for warm hospitality and generous support during the period when this work began. This article was processed by the authors using the Springer-Verlag T_EX mamath macro package 1990.     

Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.