Vertex-Transitive Non-Cayley Graphs with Arbitrarily Large Vertex-Stabilizer

A construction is given for an infinite family {_n} of finite vertex-transitive non-Cayley graphs of fixed valency with the property that the order of the vertex-stabilizer in the smallest vertex-transitive group of automorphisms of _n is a strictly increasing function ofn . For each n the graph is 4-valent and arc-transitive, with automorphism group a symmetric group of large prime degree . The construction uses Sierpinski's gasket to produce generating permutations for the vertex-stabilizer (a large 2-group).     

Graphs with symmetric automorphism group

We investigate the properties of graphs whose automorphism group is the symmetric group. In particular, we characterize graphs on less than 2n points with group S_n, and construct all graphs on n + 3 points with group S_n. Graphs with 2n or more points and group S_n are discussed briefly.     

Proportional graphs

Let S be a finite set of graphs and t a real number, 0 < t < 1. A (deterministic) graph G is (t, 5)-proportional if for every H ∈ S, the number of induced subgraphs of G isomorphic to H equals the expected number of induced copies of H in the random graph G_{n, t} where n = |V(G)|. Let S_k = {all graphs on k vertices}, in particular S₃ = {K₃, P₂, K₂K_t, D₃}. The notion of proportional graphs stems from the study of random graphs (Barbour, Karoński, and Ruciński, J Combinat. Th. Ser. B, 47 , 125-145, 1989; Janson and Nowicki, Prob. Th. Rel. Fields, to appear, Janson, Random Struct. Alg., 1 , 15-37, 1990) where it is shown that (t, S₃)-proportional graphs play a very special role; we thus call them simply t-proportional. However, only a few ½-proportional graphs on 8 vertices were known and it was an open problem whether there are any f-proportional graphs with t ≠ ½ at all. In this paper, we show that there are infinitely many ½-proportional graphs and that there are t-proportional graphs with t≠. Both results are proved constructively. [We are not able to provide the latter construction for all f∈ Q∩(0,1), but the set of ts for which our construction works is dense in (0,1).] To support a conviction that the existence of (t, S₃)-proportional graphs was not quite obvious, we show that there are no (t, S₄)-proportional graphs.     

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.     

Regular graphs of large girth and arbitrary degree

For every integer d≥10, we construct infinite families {G _n } _n∈? of d+1-regular graphs which have a large girth ≥log _d |G _n |, and for d large enough ≥1.33 · log _d |G _n |. These are Cayley graphs on PGL ₂(F _q ) for a special set of d+1 generators whose choice is related to the arithmetic of integral quaternions. These graphs are inspired by the Ramanujan graphs of Lubotzky-Philips-Sarnak and Margulis, with which they coincide when d is a prime. When d is not equal to the power of an odd prime, this improves the previous construction of Imrich in 1984 where he obtained infinite families {I _n } _n∈? of d + 1-regular graphs, realized as Cayley graphs on SL ₂(F _q ), and which are displaying a girth ≥0.48·log _d |I _n |. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families {M _n } _n∈N of 2 ^k +1-regular graphs were shown to have girth ≥2/3·log₂ ^k |M _n |.     

An analogue of group divisible designs for Moore graphs

We study graphs whose adjacency matrix S of order n satisfies the equation S + S² = J ? K + kI, where J is a matrix of order n of all 1's, K is the direct sum on $\text{n}\text{l}$ matrices of order l of all 1's, and I is the identity matrix. Moore graphs are the only solutions to the equation in the case l = 1 for which K = I. In the case k = l we can obtain Moore graphs from a solution S by a bordering process analogous to obtaining (ν, κ, λ)-designs from some group divisible designs. Other parameters are rare. We are able to find one new interesting graph with parameters k = 6, l = 4 on n = 40 vertices. We show that it has a transitive automorphism group isomorphic to C₄ × S₅.     

Some notes on Hermite-Fejer type interpolation

Let S_n(f,x) be the Hermite-Fejér type interpolation satisfying S_n(f,x_k)=f(x_k), S′_n(f,x_k)=0, k=1,2,…,n and S_n(f,y_i)=f(y_i), j=1,2,…,m. For m=0, let H_n(f,x)≔S_n(f,x). This paper investigates relationship between S_n(f,x) and H_n(f,x), as well as, the saturation of S_n(f,x).     

The size of chordal,interval and threshold subgraphs

Given a graphG withn vertices andm edges, how many edges must be in the largest chordal subgraph ofG? Form=n ²/4+1, the answer is 3n/2?1. Form=n ²/3, it is 2n?3. Form=n ²/3+1, it is at least 7n/3?6 and at most 8n/3?4. Similar questions are studied, with less complete results, for threshold graphs, interval graphs, and the stars on edges, triangles, andK ₄'s.     

Direct products of automorphism groups of graphs

In this article we study the product action of the direct product of automorphism groups of graphs. We generalize the results of Watkins [J. Combin Theory 11 (1971), 95–104], Nowitz and Watkins [Monatsh. Math. 76 (1972), 168–171] and W. Imrich [Israel J. Math. 11 (1972), 258–264], and we show that except for an infinite family of groups S_n × S_n, n≥2 and three other groups D₄ × S₂, D₄ × D₄ and S₄ × S₂ × S₂, the direct product of automorphism groups of two graphs is itself the automorphism group of a graph. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 26–36, 2009     

Edge Colouring of K2n with Spanning Star-Forests Receiving Distinct Colours

 Let S _ni be a star of size n _i and let S=S _n1∪…∪S _nk≠S _2n−3∪S ₁ or S ₂∪S ₂ be a spanning star-forest of the complete graph K _2n. We prove that K _2n has a proper (2n−1)-edge-colouring such that all the edges of S receive distinct colours. This result is very useful in the study of total-colourings of graphs. Received: March 8, 1995 / Revised: May 16, 1997     

Enumeration of Almost-Convex Polygons on the Square Lattice

We classify self-avoiding polygons on the square lattice according to a concavity measure, m, where 2m is the difference between the number of steps in the polygon and the perimeter of the minimal rectangle bounding the polygon. We generate series expansions for the perimeter generating functions S_m(x) for polygons of concavity m. We analyze the series S_m(x) for m = 0 to 3. If N_m,n denotes the number of polygons of perimeter 2n and concavity m, with m = o(n^1/2), we prove that N_m,n ? 2^2n?m?7n^m+1/m!, and that the radius of convergence of the series counting all polygons with m = o(n) is equal to 1/4. Our numerical data leads us to conjecture that in fact for m = o(n^1/2), a result confirmed for m = 0 and 1.     

Estimate for index of hypersurfaces in spheres with null higher order mean curvature

In a recent paper (Barros, Sousa in: Kodai Math. J. 2009) the authors proved that closed oriented non-totally geodesic minimal hypersurfaces of the Euclidean unit sphere have index of stability greater than or equal to n + 3 with equality occurring at only Clifford tori provided their second fundamental forms A satisfy the pinching: |A|² ≥ n. The natural generalization for this pinching is ?(r + 2)S _r+2 ≥ (n ? r)S _r  > 0. Under this condition we shall extend such result for closed oriented hypersurface Σ ⁿ of the Euclidean unit sphere ${\mathbb{S}^{n+1}}$ with null S _r+1 mean curvature by showing that the index of r-stability, ${Ind_{\Sigma^n}^{r}}$ , also satisfies ${Ind_{\Sigma^n}^{r}\ge n+3}$ . Instead of the previous hypothesis if we consider ${\frac{S_{r+2}}{{S_r}}}$ constant we have the same conclusion. Moreover, we shall prove that, up to Clifford tori, closed oriented hypersurfaces ${\Sigma^{n}\subset \mathbb{S}^{n+1}}$ with S _r+1 = 0 and S _r+2 < 0 have index of r-stability greater than or equal to 2n + 5.     

Laplacian coefficients of trees with given number of leaves or vertices of degree two

Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient c_n-2 is equal to the Wiener index of G, while c_n-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the isomorphisms and automorphism groups of circulants

Denote byC _n(S) the circulant graph (or digraph). LetM be a minimal generating element subset ofZ _n, the cyclic group of integers modulon, and In this paper, we discuss the problems about the automorphism group and isomorphisms ofC _n(S). When M S , we determine the automorphism group ofC _n(S) and prove that for any T if and only ifT = S, where is an integer relatively prime ton. The automorphism groups and isomorphisms of some other types of circulant graphs (or digraphs) are also considered. In the last section of this paper, we give a relation between the isomorphisms and the automorphism groups of circulants.     

Laplacian integral graphs in S(a, b)

Let G_n,m be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of G_n,m constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of a,b∈N/2. Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b).     

Upper bounds for ramsey numbers R(3, 3, ⋖, 3) and Schur numbers

In this paper we show that for n ≥ 4, R(3, 3, ⋖, 3) < + 1. Consequently, a new bound for Schur numbers is also given. Also, for even n ≥ 6, the Schur number S_n is bounded by S_n < - n + 2. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 119–122, 1997     

A certain estimate for the rate of convergence in the central limit theorem with respect to balls in the finite-dimensional space

+ Let X₁, X₂, ... be independent, identically distributed random variables (r.v.) with values in the space R^k. One assumes that these r.v. have zero mean and covariance operator equal to the identity. We denote by P the distribution of the r.v. X₁, by P_n the distribution of the r.v. (X₁+ ...+X_n)n^–1/2, and by the standard normal law. One investigates the problem of the estimation of the quantity where S_r(a)=S_r = are balls in R^k.Translated from Veroyatnostnye Raspredeleniya i Matematicheskaya Statistika, pp. 421–435, 1986.In conclusion, I use this opportunity to express my gratitude to V. M. Zolotarev for his constant interest in this paper.     

The existence of non-degenerate functions on a compact differentiablem-manifoldM

Summary Let M be a compact differentiable m-manifold of class C^m in E_n, n=2m+1. Let x=(x₁, ..., x_n) represent a point in E_n. The union of the direction c on the direction sphere S_n−1 in E_n such that the scalar product c · x defines a non-degenerate fonction on M is an open subset of S_n−1 whose complement θ has a Lebesgue measure zero on S_n−1. When M is non-compact θ can be everywhere dense on S_n−1, but still has Lebesgue measure zero. To Giovanni Sansone on his 70^th birth day.     

The cyclic structure of random permutations

Letα _r denote the number of cycles of length r in a random permutation, taking its values with equal probability from among the set S_n of all permutations of length n. In this paper we study the limiting behavior of linear combinations of random permutationsα ₁, ...,α _r having the form $$\zeta _{n, r} = c_{r1^{a_1 } } + ... + c_{rr} a_r $$ in the case when n, r→∞. We shall show that the class of limit distributions forξ _n,r as n, r→∞ and r In r/h→0 coincides with the class of unbounded divisible distributions. For the random variables η_n, r=α ₁+2α ₂+... rα _r, equal to the number of elements in the permutation contained in cycles of length not exceeding r, we find' limit distributions of the form r In r/n→0 and r=γ ⁿ, 0<γ<1.