Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

EQUIVARIANT SELF EQUIVALENCES OF PRINCIPAL FIBRE BUNDLES

Let E be a compact Lie group, G a closed subgroup of E, and H a closed normal sub-group of G. For principal fibre bundle (E,p, E,/G;G) tmd (E/H,p‘,E/G;G/H), the relation between auta(E) (resp. autce (E)) and autG/H(E/H) (resp. autGe/H(E/H)) is investigated by using bundle map theory and transformation group theory. It will enable us to compute the group JG(E) (resp. SG(E)) while the group J G/u(E/H) is known.     

Tight products and graph expansion

In this article, we study a new product of graphs called tight product. A graph H is said to be a tight product of two (undirected multi) graphs G₁ and G₂, if V(H) = V(G₁) × V(G₂) and both projection maps V(H)→V(G₁) and V(H)→V(G₂) are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is NP‐hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class‐1 (2k+ 1)‐regular graphs. We also obtain a new model of random d‐regular graphs whose second eigenvalue is almost surely at most O(d^3/4). This construction resembles random graph lifts, but requires fewer random bits. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Independent sets in tensor graph powers

The tensor product of two graphs, G and H, has a vertex set V(G) × V(H) and an edge between (u,v) and (u′,v′) iff both u u′ ∈ E(G) and v v′ ∈ E(H). Let A(G) denote the limit of the independence ratios of tensor powers of G, lim, α(Gⁿ)/|V(Gⁿ)|. This parameter was introduced in [Brown, Nowakowski, Rall, SIAM J Discrete Math 9 ( 5 ), 290–300], where it was shown that A(G) is lower bounded by the vertex expansion ratio of independent sets of G. In this article we study the relation between these parameters further, and ask whether they are in fact equal. We present several families of graphs where equality holds, and discuss the effect the above question has on various open problems related to tensor graph products. © 2006 Wiley Periodicals, Inc. J Graph Theory     

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.     

Polar actions on Hilbert space

An isometricH-action on a Riemannian manifoldX is calledpolar if there exists a closed submanifoldS ofX that meets everyH-orbit and always meets orbits orthogonally (S is called a section). LetG be a compact Lie group equipped with a biinvariant metric,H a closed subgroup ofG ×G, and letH act onG isometrically by (h ₁,h ₂) ·x = h ₁ xh ₂ ⁻¹ · LetP(G, H) denote the group ofH ¹-pathsg: [0, 1] →G such that (g(0),g (1)) ∈H, and letP(G, H) act on the Hilbert spaceV = H ⁰([0, 1], g) isometrically byg * u = gug ⁻¹ −g′g ⁻¹. We prove that if the action ofH onG is polar with a flat section then the action ofP(G, H) onV is polar. Principal orbits of polar actions onV are isoparametric submanifolds ofV and are infinite-dimensional generalized real or complex flag manifolds. We also note that the adjoint actions of affine Kac-Moody groups and the isotropy action corresponding to an involution of an affine Kac-Moody group are special examples ofP(G, H)-actions for suitable choice ofH andG. Work supported partially by NSF Grant DMS 8903237 and by The Max-Planck-Institut für Mathematik in Bonn.     

Decomposing large graphs with small graphs of high density

It is shown that for every positive integer h, and for every ϵ > 0, there are graphs H = )V_H E_H) with at least h vertices and with density at least 0.5 - ϵ with the following property: If G = (V_G, E_G) is any graph with minimum degree at least (1 + o(1)) and |E_H| divides |E_G|, then G has an H-decomposition. This result extends the results of [R. M. Wilson, Cong Numer XV (1925), 647–659] [T. Gustavsson, Ph.D. Thesis, U. Stockholm, 1991] [R. Yuster, Random Struc Algorith, 12 (1998), 237–251]. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 27–40, 1999     

A partition approach to Vizing's conjecture

In 1963, Vizing [Vichysl.Sistemy 9 (1963), 30–43] conjectured that γ(G × H) ≥ γ(G)γ(H), where G × H denotes the cartesian product of graphs, and γ(G) is the domination number. In this paper we define the extraction number x(G) and we prove that P₂(G) ≤ x(G), and γ(G × H) ≥ x(G)γ(H), where P₂(G) is the 2-packing number of G. Though the equality x(G) = γ(G) is proven to hold in several classes of graphs, we construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: γ(G × H) ≥ γ(G)P₂(H) + P₂(G)(γ(H) − P₂(H)). © 1996 John Wiley & Sons, Inc.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

Graph norms and Sidorenko’s conjecture

Let H and G be two finite graphs. Define h _H (G) to be the number of homomorphisms from H to G. The function h _H (·) extends in a natural way to a function from the set of symmetric matrices to ℝ such that for A _G , the adjacency matrix of a graph G, we have h _H (A _G ) = h _H (G). Let m be the number of edges of H. It is easy to see that when H is the cycle of length 2n, then h _H (·)^1/m is the 2n-th Schatten-von Neumann norm. We investigate a question of Lovász that asks for a characterization of graphs H for which the function h _H (·)^1/m is a norm.     

Hall parameters of complete and complete bipartite graphs

Given a graph G, for each υ ∈V(G) let L(υ) be a list assignment to G. The well‐known choice number c(G) is the least integer j such that if |L(υ)| ≥j for all υ ∈V(G), then G has a proper vertex colouring ? with ?(υ) ∈ L (υ) (?υ ∈V(G)). The Hall number h(G) is like the choice number, except that an extra non‐triviality condition, called Hall's condition, has to be satisfied by the list assignment. The edge‐analogue of the Hall number is called the Hall index, h′(G), and the total analogue is called the total Hall number, h″(G), of G. If the stock of colours from which L(υ) is selected is restricted to a set of size k, then the analogous numbers are called k‐restricted, or restricted, Hall parameters, and are denoted by h_k(G), h′_k(G) and h″_k(G). Our main object in this article is to determine, or closely bound, h′(K), h″(K_n), h′(K_m,n) and h′_k(K_m,n). We also answer some hitherto unresolved questions about Hall parameters. We show in particular that there are examples of graphs G with h′(G)?h′(G ? e)>1. We show that there are examples of graphs G and induced subgraphs H with h_k(G)<h_k(H) [this phenomenon cannot occur with unrestricted Hall numbers]. We also give an example of a graph G and an integer k such that h_k(G)<χ(G)<h(G). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 208–237, 2002     

A generalization of perfect graphs—i-perfect graphs

Let i be a positive integer. We generalize the chromatic number _X(G) of G and the clique number o(G) of G as follows: The i-chromatic number of G, denoted by _X(G), is the least number k for which G has a vertex partition V₁, V₂,…, V_k such that the clique number of the subgraph induced by each V_j, 1 ≤ j ≤ k, is at most i. The i-clique number, denoted by o_i(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly _X1(G) = _X(G) and o₁(G) = o(G). An induced subgraph G′ of G is an i-transversal iff o(G′) = i and o(G − G′) = o(G) − i. We generalize the notion of perfect graphs as follows: (1) A graph G is i-perfect iff _Xi(H) = o_i(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transversable iff either o(G) ≤ i or every induced subgraph H of G with o(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1-perfect graphs and perfectly 1-transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i ≥ 2. We also show that all planar graphs are i-perfect for every i ≥ 2 and perfectly i-transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle-free graphs are 2-perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i-perfect graphs and the recognition of perfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.     

Hamilton cycles and closed trails in iterated line graphs

Let G be an undirected connected graph that is not a path. We define h(G) (respectively, s(G)) to be the least integer m such that the iterated line graph L^m(G) has a Hamiltonian cycle (respectively, a spanning closed trail). To obtain upper bounds on h(G) and s(G), we characterize the least integer m such that L^m(G) has a connected subgraph H, in which each edge of H is in a 3-cycle and V(H) contains all vertices of degree not 2 in L^m(G). We characterize the graphs G such that h(G) — 1 (respectively, s(G)) is greater than the radius of G.     

On Group Chromatic Number of Graphs

Let G be a graph and A an Abelian group. Denote by F(G, A) the set of all functions from E(G) to A. Denote by D an orientation of E(G). For f ∈ F(G,A), an (A,f)-coloring of G under the orientation D is a function c : V(G)↦A such that for every directed edge uv from u to v, c(u)−c(v) ≠ f(uv). G is A-colorable under the orientation D if for any function f ∈ F(G, A), G has an (A, f)-coloring. It is known that A-colorability is independent of the choice of the orientation. The group chromatic number of a graph G is defined to be the least positive integer m for which G is A-colorable for any Abelian group A of order ≥m, and is denoted by χ_g(G). In this note we will prove the following results. (1) Let H₁ and H₂ be two subgraphs of G such that V(H₁)∩V(H₂)=∅ and V(H₁)∪V(H₂)=V(G). Then χ_g(G)≤min{max{χ_g(H₁), max_v∈V(H2)deg(v,G)+1},max{χ_g(H₂), max_u∈V(H1) deg (u, G) + 1}}. We also show that this bound is best possible. (2) If G is a simple graph without a K_3,3-minor, then χ_g(G)≤5.     

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).     

OD-Characterization of Some Projective Special Linear Groups Over the Binary Field and Their Automorphism Groups

The Gruenberg–Kegel graph GK(G) = (V _G , E _G ) of a finite group G is a simple graph with vertex set V _G  = π(G), the set of all primes dividing the order of G, and such that two distinct vertices p and q are joined by an edge, {p, q} ∈ E _G , if G contains an element of order pq. The degree deg _G (p) of a vertex p ∈ V _G is the number of edges incident to p. In the case when π(G) = {p ₁, p ₂,…, p _h } with p ₁ < p ₂ < … <p _h , we consider the h-tuple D(G) = (deg _G (p ₁), deg _G (p ₂),…, deg _G (p _h )), which is called the degree pattern of G. The group G is called k-fold OD-characterizable if there exist exactly k non-isomorphic groups H satisfying condition (|H|, D(H)) = (|G|, D(G)). Especially, a 1-fold OD-characterizable group is simply called OD-characterizable. In this paper, we prove that the simple groups L ₁₀(2) and L ₁₁(2) are OD-characterizable. It is also shown that automorphism groups Aut(L _p (2)) and Aut(L _p+1(2)), where 2 ^p  ? 1 is a Mersenne prime, are OD-characterizable. Finally, a list of finite (simple) groups which are presently known to be k-fold OD-characterizable, for certain values of k, is presented.     

On the geodetic number of permutation graphs

A vertex set S in a graph G is a geodetic set if every vertex of G lies on some u?v geodesic of G, where u,v∈S. The geodetic number g(G) of G is the minimum cardinality over all geodetic sets of G. Let G ₁ and G ₂ be disjoint copies of a graph G, and let σ:V(G ₁)→V(G ₂) be a bijection. Then, a permutation graph G _σ =(V,E) has the vertex set V=V(G ₁)∪V(G ₂) and the edge set E=E(G ₁)∪E(G ₂)∪{uv∣v=σ(u)}. For any connected graph G of order n≥3, we prove the sharp bounds 2≤g(G _σ )≤2n?(1+△(G)), where △(G) denotes the maximum degree of G. We give examples showing that neither is there a function h ₁ such that g(G)<h ₁(g(G _σ )) for all pairs (G,σ), nor is there a function h ₂ such that h ₂(g(G))>g(G _σ ) for all pairs (G,σ). Further, we characterize permutation graphs G _σ satisfying g(G _σ )=2|V(G)|?(1+△(G)) when G is a cycle, a tree, or a complete k-partite graph.     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

A New Class of Generalized Thompson's Groups and Their Normal Subgroups

For a given group G and a homomorphism ?: G → G × G, we construct groups ?_?(G), 𝒯_?(G), and 𝒱_?(G) that blend Thompson's groups F, T, and V with G, respectively. Furthermore, we describe the lattice of normal subgroups of the groups ?_Δ(G), where Δ: G → G × G is the diagonal homomorphism, Δ(g) = (g, g).