Expanders obtained from affine transformations

A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ _G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ _G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones.     

Almost 2-Homogeneous Graphs and Completely Regular Quadrangles

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ _i  = |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion of Science.     

The embedding of line graphs associated to the zero-divisor graphs of commutative rings

Let R be a commutative ring with identity and denote Γ(R) for its zero-divisor graph. In this paper, we study the minimal embedding of the line graph associated to Γ(R), denoted by L(Γ(R)), into compact surfaces (orientable or non-orientable) and completely classify all finite commutative rings R such that the line graphs associated to their zero-divisor graphs have genera or crosscaps up to two.     

Average bending of convex pleated planes in hyperbolic three-space

If P is a pleated plane in 3-dimensional hyperbolic space H ³ and α a geodesic in its intrinsic metric we define B(P,α), the average bending of P in the direction α. We show that if P is a convex pleated plane embedded in H ³ then B(P,α)≤K for some universal K. Furthermore if P_Γ is a boundary component of the convex hull of a quasi-Fuchsian group Γ then B(P_Γ,α)=B(Γ) almost everywhere, where B(Γ) is a constant times the length of the bending lamination β_Γ of the pleated surface X _Γ=P_Γ/Γ. We use these to prove a number of results about quasi-Fuchsian groups including a universal bound on the Lipschitz constant for the map to infinity and a bound on the length of β_Γ by a constant times the Euler characteristic of X _Γ. Oblatum 10-X-1996 & 23-V-1997     

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

Distinguishing labeling of the actions of almost simple groups

Suppose Γ is a group acting on a set X, written as (Γ,X). An r-labeling f: X→{1,2, ..., r} of X is called distinguishing for (Γ,X) if for all σ∈Γ,σ≠1, there exists an element x∈X such that f(x)≠f(x ^σ ). The distinguishing number d(Γ,X) of (Γ,X) is the minimum r for which there is a distinguishing r-labeling for (Γ,X). If Γ is the automorphism group of a graph G, then d(Γ,V (G)) is denoted by d(G), and is called the distinguishing number of the graph G. The distinguishing set of Γ-actions is defined to be D*(Γ)={d(Γ,X): Γ acts on X}, and the distinguishing set of Γ-graphs is defined to be D(Γ)={d(G): Aut(G)≅Γ}. This paper determines the distinguishing set of Γ-actions and the distinguishing set of Γ-graphs for almost simple groups Γ.     

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

Some remarks on universal graphs

LetΓ be a class of countable graphs, and let ℱ(Γ) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member ofΓ. Furthermore, letTΓ andHΓ denote the class of all subdivisions of graphs inΓ and the class of all graphs contracting to a member ofΓ, respectively. As the main result of this paper it is decided which of the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ),n≦ℵ₀, contain a universal element. In fact, for ℱ(TK ⁴)=ℱ(HK ⁴) a strongly universal graph is constructed, whereas for 5≦n≦ℵ₀ the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ) have no universal elements. Dedicated to Klaus Wagner on his 75^th birthday     

The exact Hausdorff measures for the graph and image of a multidimensional iterated Brownian motion

Let {W(t),t∈R}, {B(t),t∈R } be two independent Brownian motions on R with W(0) = B(0) = 0. In this paper, we shall consider the exact Hausdorff measures for the image and graph sets of the d-dimensional iterated Brownian motion X(t), where X(t) = (Xi(t),... ,Xd(t)) and X1(t),... ,Xd(t) are d independent copies of Y(t) = W(B(t)). In particular, for any Borel set Q (?) (0,∞), the exact Hausdorff measures of the image X(Q) = {X(t) : t∈Q} and the graph GrX(Q) = {(t, X(t)) :t∈Q}are established.     

Expansion Of Product Replacement Graphs

We establish a connection between the expansion coefficient of the product replacement graph Γ_k(G) and the minimal expansion coefficient of a Cayley graph of G with k generators. In particular, we show that the product replacement graphs Γ_k(PSL(2,p)) form an expander family, under assumption that all Cayley graphs of PSL(2,p), with at most k generators are expanders. This gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders [42,52].     

On the outradius of the teichmüller space

Let Γ be a fuchsian group which preserves the unit disc Δ and hence also its complement Δ^* in the Riemann sphere . The Bers embedding represents the Teichm=:uller space T(Γ) of Γ in the space (B (Δ^*, Γ) of bounded quadratic differentials for Γ in Δ^*. Then, T(Γ) is included in the closed ball centred at the origin of radius 6 inB(Δ^*, Γ) with respect to the norm employed in a paper by Nehari [The Schwarzian derivative and Schlicht functions; Bull. Amer. Math. Soc. 55 (1949), 545–551]. In other words the outradiuso(Γ) ofT(Γ) is not greater than 6. The purpose of this paper is to give a complete characterization of a fuchsian group Γ for which the outradiuso(Γ) ofT(Γ) attains this extremal value 6. The main theorem is: Let Γ be a fuchsian group preserving Δ^*. Then the outradiuso(Γ) of the Teichmüller spaceT(Γ) equals 6 if and only if for any positive numberd, either (i) there exists a hyperbolic disc of radiusd precisely invariant under the trivial subgroup, or (ii) there exists the collar of widthd about the axis of a hyperbolic element of Γ. Dedicated to Professor K?taro Oikawa on his 60th birthday     

Infinite injective transformations whose centralizers have simple structure

For an infinite set X, denote by Γ(X) the semigroup of all injective mappings from X to X under function composition. For α ∈ Γ(X), let C(α) = {β ∈ g/g(X): αβ = βα} be the centralizer of α in Γ(X). The aim of this paper is to determine those elements of Γ(X) whose centralizers have simple structure. We find α ∈ (X) such that various Green's relations in C(α) coincide, characterize α ∈ Γ(X) such that the $ \mathcal{J} $ \mathcal{J} -classes of C(α) form a chain, and describe Green's relations in C(α) for α with so-called finite ray-cycle decomposition. If α is a permutation, we also find the structure of C(α) in terms of direct and wreath products of familiar semigroups.     

Metric properties of the tropical Abel–Jacobi map

Let Γ be a tropical curve (or metric graph), and fix a base point p∈Γ. We define the Jacobian group J(G) of a finite weighted graph G, and show that the Jacobian J(Γ) is canonically isomorphic to the direct limit of J(G) over all weighted graph models G for Γ. This result is useful for reducing certain questions about the Abel–Jacobi map Φ _p :Γ→J(Γ), defined by Mikhalkin and Zharkov, to purely combinatorial questions about weighted graphs. We prove that J(G) is finite if and only if the edges in each 2-connected component of G are commensurable over ℚ. As an application of our direct limit theorem, we derive some local comparison formulas between ρ and \varPhi_p^*(r){\varPhi}_{p}^{*}(\rho) for three different natural “metrics” ρ on J(Γ). One of these formulas implies that Φ _p is a tropical isometry when Γ is 2-edge-connected. Another shows that the canonical measure μ _Zh on a metric graph Γ, defined by S. Zhang, measures lengths on Φ _p (Γ) with respect to the “sup-norm” on J(Γ).     

Non-existence of bipartite graphs of diameter at least 4 and defect 2

The Moore bipartite bound represents an upper bound on the order of a bipartite graph of maximum degree Δ and diameter D. Bipartite graphs of maximum degree Δ, diameter D and order equal to the Moore bipartite bound are called Moore bipartite graphs. Such bipartite graphs exist only if D=2,3,4 and 6, and for D=3,4,6, they have been constructed only for those values of Δ such that Δ−1 is a prime power.     

Closure Operators and Lattice Extensions

For closure operators Γ and Δ on the same set X, we say that Δ is a weak (resp. strong) extension of Γ if Cl(X, Γ) is a complete meet-subsemilattice (resp. complete sublattice) of Cl(X, Δ). This context is used to describe the extensions of a finite lattice that preserve various properties. This revised version was published online in September 2006 with corrections to the Cover Date.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Order of a function on the Bruschlinsky group of a two-dimensional polyhedron

Homotopy classes of mappings of a compact polyhedron X to the circle T form an Abelian group B(X), which is called the Bruschlinsky group and is cananically isomorphic to H ¹ (X; ℤ), Let L be an Abelian group, and let f: B(X) → L be a function. One says that the order of f does not exceed r if for each mapping a: X → T the value f([a]) is ℤ-linearly expressed via the characteristic function I _r (a): (X × T) ^r → ℤ of (Γ _a ) ^r , where Γ _a ⊂ X × T is the graph of a. The (algebraic) degree of f is not greater than r if the finite differences of f of order r + 1 vanish. Conjecturally, the order of f is equal to the algebraic degree of f. The conjecture is proved in the case where dim X ≤ 2. Bibliography: 1 title.     

The Algebra of Flows in Graphs

We define a contravariant functorKfrom the category of finite graphs and graph morphisms to the category of finitely generated graded abelian groups and homomorphisms. For a graphX, an abelian groupB, and a nonnegative integerj, an element of Hom(K^j(X), B) is a coherent family ofB-valued flows on the set of all graphs obtained by contracting some (j − 1)-set of edges ofX; in particular, Hom(K¹(X), ) is the familiar (real) “cycle-space” ofX. We show thatK ^· (X) is torsion-free and that its Poincaré polynomial is the specializationt^{n − k}T_X(1/t, 1 + t) of the Tutte polynomial ofX(hereXhasnvertices andkcomponents). Functoriality ofK ^· induces a functorial coalgebra structure onK ^· (X); dualizing, for any ringBwe obtain a functorialB-algebra structure on Hom(K ^· (X), B). WhenBis commutative we present this algebra as a quotient of a divided power algebra, leading to some interesting inequalities on the coefficients of the above Poincaré polynomial. We also provide a formula for the theta function of the lattice of integer-valued flows inX, and conclude with 10 open problems.