Cubic non-normal Cayley graphs of order 4p2

A Cayley graph $\mathrm{Cay}(G,S)$ on a group $G$ is said to be normal if the right regular representation $R\left(G\right)$ of $G$ is normal in the full automorphism group of $\mathrm{Cay}(G,S)$. In this paper all connected cubic non-normal Cayley graphs of order $4p^2$ are constructed explicitly for each odd prime $p$. It is shown that there are three infinite families of cubic non-normal Cayley graphs of order $4p^2$ with $p$ odd prime. Note that a complete classification of cubic non-Cayley vertex-transitive graphs of order $4p^2$ was given in [K. Kutnar, D. Marus?ic?, C. Zhang, On cubic non-Cayley vertex-transitive graphs, J. Graph Theory 69 (2012) 77–95]. As a result, a classification of cubic vertex-transitive graphs of order $4p^2$ can be deduced.     

Sylow subgraphs in self-complementary vertex transitive graphs

A graph is self-complementary if it is isomorphic to its complement. A graph is vertex transitive if for each choice of vertices u and $v$ there is an automorphism that carries the vertex u to $v$. The number of vertices in a self-complementary vertex-transitive graph must necessarily be congruent to 1 mod 4. However, Muzychuk has shown that if $p^m$ is the largest power of a prime p dividing the order of a self-complementary vertex-transitive graph, then $p^m$ must individually be congruent to 1 mod 4. This is accomplished by establishing the existence of a self-complementary vertex transitive subgraph of order $p^m$, a result reminiscent of the Sylow theorems. This article is a self-contained survey, culminating with a detailed proof of Muzychuk's result.     

On the excess of vertex-transitive graphs of given degree and girth

We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive $k$-regular graphs of girth $g$. Counting cycles to obtain necessary arithmetic conditions on the parameters $(k,g)$, we extend previous results of Biggs, and prove that, for any given excess $e$ and any given degree $k\ge 4$, the asymptotic density of the set of girths $g$ for which there exists a vertex-transitive $(k,g)$-cage with excess not exceeding $e$ is 0.     

On strong graph bundles

We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs $E$, $B$ and $F$ and a projection $p:E\to B$ with fiber $F$ (i.e. $p^{?1}\left(x\right)?F$ for all $x\in V\left(B\right)$) such that the preimage of any edge $xy$ of $B$ is trivial (i.e. $p^{?1}\left(xy\right)?K_2?F$). Here we develop a framework to study which subgraphs $S$ of $B$ have trivial preimages (i.e. $p^{?1}\left(S\right)?S?F$) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.     

Balanced and strongly balanced Pk-designs

Given a graph $G$, a G-decomposition of the complete graph $K_v$ is a set of graphs, all isomorphic to $G$, whose edge sets partition the edge set of $K_v$. A $G$-decomposition of $K_v$ is also called a G-design and the graphs of the partition are said to be the blocks. A $G$-design is said to be balanced if the number of blocks containing any given vertex of $K_v$ is a constant.In this paper the concept of strongly balanced G-design is introduced and strongly balanced path-designs are studied. Furthermore, we determine the spectrum of those path-designs which are balanced, but not strongly balanced.     

A way to construct independence equivalent graphs

Let us denote the independence polynomial of a graph by $I_G\left(x\right)$. If $I_G\left(x\right)=I_H\left(x\right)$ implies that $G?H$ then we say $G$ is independence unique. For graph $G$ and $H$ if $I_G\left(x\right)=I_H\left(x\right)$ but $G$ and $H$ are not isomorphic, then we say $G$ and $H$ are independence equivalent. In [7], Brown and Hoshino gave a way to construct independent equivalent graphs for circulant graphs. In this work we give a way to construct the independence equivalent graphs for general simple graphs and obtain some properties of the independence polynomial of paths and cycles.     

Moplex orderings generated by the LexDFS algorithm

Let $G$ be a graph with vertex set $V$. A moplex of $G$ is both a clique and a module whose neighborhood is a minimal separator in $G$ or empty. A moplex ordering of $G$ is an ordered partition $(X_1,X_2,?,X_k)$ of $V$ for some integer $k$ into moplexes which are defined in the successive transitory elimination graphs, i.e., for $1?i?k?1$, $X_i$ is a moplex of the graph $G_i$ induced by ${\cup }_{j=i}^k{X}_j$ and $X_k$ induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on $G$ belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on $G$ defines a moplex ordering of $G$, which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques.     

Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs

Consider two graphs $G$ and $H$. Let $H^k\left[G\right]$ be the lexicographic product of $H^k$ and $G$, where $H^k$ is the lexicographic product of the graph $H$ by itself $k$ times. In this paper, we determine the spectrum of $H^k\left[G\right]$ and $H^k$ when $G$ and $H$ are regular and the Laplacian spectrum of $H^k\left[G\right]$ and $H^k$ for $G$ and $H$ arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10¹⁰⁰ ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers.     

Diameter bounds and recursive properties of Full-Flag Johnson graphs

The Johnson graphs $J(n,k)$ are a well-known family of combinatorial graphs whose applications and generalizations have been studied extensively in the literature. In this paper, we present a new variant of the family of Johnson graphs, the Full-Flag Johnson graphs, and discuss their combinatorial properties. We show that the Full-Flag Johnson graphs are Cayley graphs on $S_n$ generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. We prove a tight $\Theta (n^2∕k^2)$ bound for the diameter of the Full-Flag Johnson graph FJ$(n,k)$ and establish recursive relations between FJ$(n,k)$ and the lower-order Full-Flag Johnson graphs FJ$(n?1,k)$ and FJ$(n?1,k?1)$. We apply this recursive structure to partially compute the spectrum of permutahedra.     

New concepts of regular and (highly) irregular vague graphs with applications

In this paper, some types of vague graphs are introdaced such as $d_m$-regular, $t{d}_m$-regular, $m$-highly irregular and $m$-highly totally irregular vague graphs are introduced and some properties of them are discussed. Comparative study between $d_m$-regular ($m$-highly irregular) vague graph and $t{d}_m$-regular ($m$-highly totally irregular) vague graph are done. In addition, $d_m$-regularity and $m$-highly irregularity on some vague graphs, which underlying crisp graphs are a cycle or a path is also studied. Finally, some applications of regular vague graphs are given for demonstration of fullerene molecules, road transport network and wireless multihop networks.     

Zero-one k-law

In this article we study asymptotical behavior of the probabilities of some properties of Erd?s–Rényi random graphs $G(N,p)$. We consider the first-order properties and the probabilities $p=N^{?\alpha }$ for rational $\alpha$. The zero-one law in ordinary sense for these graphs doesn’t hold. We weakened the law by considering the formulas with quantifier depth bounded by a fixed number. To prove our results we used theorems on estimates for the number of extensions of small subgraphs in the random graph. Such an approach was first used by Spencer and Shelah in 1988. We also used our recent results from this area.     

Local uniformization and arc spaces

Let X be a variety over a perfect field k and let $X_{\infty }$ be its space of arcs. Given a closed subset Z of X, let $X_{\infty }^Z$ denote the subscheme of $X_{\infty }$ consisting of all arcs centered at some point of Z. We prove that Local Uniformization implies that $X_{\infty }^Z$ has a finite number of irreducible components for each closed subset Z of X. In particular, Local Uniformization implies that $X_{\infty }^{\mathit{Sing}X}$ has a finite number of irreducible components.     

Locality of connective constants

The connective constant $\mu \left(G\right)$ of a quasi-transitive graph $G$ is the exponential growth rate of the number of self-avoiding walks from a given origin. We prove a locality theorem for connective constants, namely, that the connective constants of two graphs are close in value whenever the graphs agree on a large ball around the origin (and a further condition is satisfied). The proof is based on a generalized bridge decomposition of self-avoiding walks, which is valid subject to the assumption that the underlying graph is quasi-transitive and possesses a so-called unimodular graph height function.