Semi-hyper-connected vertex transitive graphs

A graph G is said to be semi-hyper-connected if the removal of every minimum cut of G creates exactly two connected components. In this paper, we characterize semi-hyper-connected vertex transitive graphs, in particular Cayley graphs.     

Semiregular automorphisms of cubic vertex transitive graphs

It is shown that for a connected cubic graph , a vertex transitive group contains a large semiregular subgroup. This confirms a conjecture of Cameron and Sheehan (2001).

     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales

The Alon–Roichman theorem states that for every ε> 0 there is a constant c(ε), such that the Cayley graph of a finite group G with respect to c(ε)log ∣G∣ elements of G, chosen independently and uniformly at random, has expected second largest eigenvalue less than ε. In particular, such a graph is an expander with high probability. Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a new proof of the result, improving the bounds even further. When considered for a general group G, our bounds are in a sense best possible. We also give a generalization of the Alon–Roichman theorem to random coset graphs. Our proof uses a Hoeffding‐type result for operator valued random variables, which we believe can be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On super 2-restricted and 3-restricted edge-connected vertex transitive graphs

Let $G=(V\left(G\right),E\left(G\right))$ be a simple connected graph and $F?E\left(G\right)$. An edge set $F$ is an $m$-restricted edge cut if $G?F$ is disconnected and each component of $G?F$ contains at least $m$ vertices. Let ${\lambda }^{\left(m\right)}\left(G\right)$ be the minimum size of all $m$-restricted edge cuts and ${\xi }_m\left(G\right)=min\{\left|\omega \left(U\right)\right|:\left|U\right|=m\text{ and }G\left[U\right]\text{ is connected}\}$, where $\omega \left(U\right)$ is the set of edges with exactly one end vertex in $U$ and $G\left[U\right]$ is the subgraph of $G$ induced by $U$. A graph $G$ is optimal-${\lambda }^{\left(m\right)}$ if ${\lambda }^{\left(m\right)}\left(G\right)={\xi }_m\left(G\right)$. An optimal-${\lambda }^{\left(m\right)}$ graph is called super $m$-restricted edge-connected if every minimum $m$-restricted edge cut is $\omega \left(U\right)$ for some vertex set $U$ with $\left|U\right|=m$ and $G\left[U\right]$ being connected. In this note, we give a characterization of super 2-restricted edge-connected vertex transitive graphs and obtain a sharp sufficient condition for an optimal-${\lambda }^{\left(3\right)}$ vertex transitive graph to be super 3-restricted edge-connected. In particular, a complete characterization for an optimal-${\lambda }^{\left(2\right)}$ minimal Cayley graph to be super 2-restricted edge-connected is obtained.     

Equienergetic self-complementary graphs

In this paper equienergetic self-complementary graphs on p vertices for every p = 4k, k ⩾ 2 and p = 24t + 1, t ⩾ 3 are constructed.     

Triangles in self-complementary graphs

It is shown that the number of triangles in a self-complementary graph with N vertices is at least $\text{N(N ? 2)(N ? 4)}\text{48}$ if N ≡ 0 (mod 4) and at least $\text{N(N ? 1)(N ? 5)}\text{48}$ if N ≡ 1 (mod 4), and that this minimum number can be achieved.     

Cycles in self-complementary graphs

Let G be a self-complementary graph of order p ≥ 8. It is shown that for every integer l, 3 ≤ l ≤ p ? 2, G has an l-cycle. Further, if G is hamiltonian, then G is pancyclic.     

On separable self-complementary graphs

In this paper, we describe the structure of separable self-complementary graphs.     

On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.     

On regular self-complementary graphs

A regular self-complementary graph is presented which has no complementing permutation consisting solely of cycles of length four. This answers one of Kotzig's questions.     

On self-complementary vertex-transitive graphs

In this paper we study the problem of determining positive integers n for which there exist self-complementary vertex-transitive graphs of order n. The main aim of this paper is to prove that, for distinct primes p, q, there exist self-complementary vertex-transitive graphs of order pq if and only if p, q Scz.tbnd;1 (mod 4). This provides negative answers to a long-standing open question proposed by Zelinka (1979) and a recent open question proposed by Froncek, Rosa Siran (1996).     

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.