On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

How to make a triangulation of polytopal

We introduce a numerical isomorphism invariant for any triangulation of . Although its definition is purely topological (inspired by the bridge number of knots), reflects the geometric properties of . Specifically, if is polytopal or shellable, then is ``small' in the sense that we obtain a linear upper bound for in the number of tetrahedra of . Conversely, if is ``small', then is ``almost' polytopal, since we show how to transform into a polytopal triangulation by local subdivisions. The minimal number of local subdivisions needed to transform into a polytopal triangulation is at least . Using our previous results [The size of triangulations supporting a given link, Geometry & Topology 5 (2001), 369-398], we obtain a general upper bound for exponential in . We prove here by explicit constructions that there is no general subexponential upper bound for in . Thus, we obtain triangulations that are ``very far' from being polytopal. Our results yield a recognition algorithm for that is conceptually simpler, although somewhat slower, than the famous Rubinstein-Thompson algorithm.

     

Free Wreath Product by the Quantum Permutation Group

Let A be a compact quantum group, let nN ^* and let A _aut(X _n ) be the quantum permutation group on n letters. A free wreath product construction A*_w A _aut(X _n ) is introduced. This construction provides new examples of quantum groups, and is useful to describe the quantum automorphism group of the n-times disjoint union of a finite connected graph.     

On the Characterizability of the Automorphism Groups of Sporadic Simple Groups by Their Element Orders

For G a finite group, π _e (G) denotes the set of orders of elements in G. If Ω is a subset of the set of natural numbers, h(Ω) stands for the number of isomorphism classes of finite groups with the same set Ω of element orders. We say that G is k-distinguishable if h(π _e (G)) = k < ∞, otherwise G is called non-distinguishable. Usually, a 1-distinguishable group is called a characterizable group. It is shown that if M is a sporadic simple group different from M ₁₂, M ₂₂, J ₂, He, Suz, M ^c L and O′N, then Aut(M) is characterizable by its element orders. It is also proved that if M is isomorphic to M ₁₂, M ₂₂, He, Suz or O′N, then h(π _e (Aut(M))) ∈¸ {1,∞}.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

The girth of a 4-homogeneous bipartite graph

In this paper, it is proved that the girth of a 4-homogeneous bipartite graph with valency greater than 2 is at most 12.     

Graph Automorphisms and Cells of Lattices

In this paper we apply the notion of cell of a lattice for dealing with graph automorphisms of lattices (in connection with a problem proposed by G. Birkhoff).     

Bound on <Emphasis Type="Italic">m</Emphasis>-restricted Edge Connectivity

An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restrict edge connectivity λm is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let θ(X) denote the number of edges with one end in X and the other not in X and ξm=min{θ(X) ;X is a connected vertex-induced subgraph of order m}.It is proved in this paper that if G has girth at least m/2 2,then λm≤ξm.The upper bound of λm is sharp.     

1-Homogeneous Graphs with Cocktail Party μ-Graphs

Let be a graph with diameter d 2. Recall is 1-homogeneous (in the sense of Nomura) whenever for every edge xy of the distance partition{{z V() | (z, y) = i, (x, z) = j} | 0 i, j d}is equitable and its parameters do not depend on the edge xy. Let be 1-homogeneous. Then is distance-regular and also locally strongly regular with parameters (v,k,,), where v = k, k = a ₁, (v – k – 1) = k(k – 1 – ) and c ₂ + 1, since a -graph is a regular graph with valency . If c ₂ = + 1 and c ₂ 1, then is a Terwilliger graph, i.e., all the -graphs of are complete. In [11] we classified the Terwilliger 1-homogeneous graphs with c ₂ 2 and obtained that there are only three such examples. In this article we consider the case c ₂ = + 2 3, i.e., the case when the -graphs of are the Cocktail Party graphs, and obtain that either = 0, = 2 or is one of the following graphs: (i) a Johnson graph J(2m, m) with m 2, (ii) a folded Johnson graph J¯(4m, 2m) with m 3, (iii) a halved m-cube with m 4, (iv) a folded halved (2m)-cube with m 5, (v) a Cocktail Party graph K _{m × 2} with m 3, (vi) the Schläfli graph, (vii) the Gosset graph.     

Some Bipartite Ramsey Numbers

Consider a complete bipartite graph K(s, s) with p = 2s points. Let each line of the graph have either red or blue colour. The smallest number p of points such that K(s, s) always contains red K(m, n) or blue K(m, n) is called bipartite Ramsey number denoted by rb(K(m, n), K(m, n)). In this paper, we show that