Vertex pancyclic graphs

Let G be a graph of order n. A graph G is called pancyclic if it contains a cycle of length k for every 3kn, and it is called vertex pancyclic if every vertex is contained in a cycle of length k for every 3kn. In this paper, we shall present different sufficient conditions for graphs to be vertex pancyclic.     

Semi-hyper-connected edge transitive graphs

A graph G is said to be hyper-connected if the removal of every minimum cut creates exactly two connected components, one of which is an isolated vertex. In this paper, we first generalize the concept of hyper-connected graphs to that of semi-hyper-connected graphs: a graph G is called semi-hyper-connected if the removal of every minimum cut of G creates exactly two components. Then we characterize semi-hyper-connected edge transitive graphs.     

Super-connected edge transitive graphs

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C_n(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected.     

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.     

Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.     

Locally s-distance transitive graphs and pairwise transitive designs

The study of locally s-distance transitive graphs initiated by the authors in previous work, identified that graphs with a star quotient are of particular interest. This paper shows that the study of locally s-distance transitive graphs with a star quotient is equivalent to the study of a particular family of designs with strong symmetry properties that we call nicely affine and pairwise transitive. We show that a group acting regularly on the points of such a design must be abelian and give general construction for this case.     

Vertex pancyclicity in quasi-claw-free graphs

A graph G is called quasi-claw-free if for any two vertices x and y with distance two there exists a vertex u∈N(x)∩N(y) such that N[u]⊆N[x]∪N[y]. This concept is a natural extension of the classical claw-free graphs. In this paper, we present two sufficient conditions for vertex pancyclicity in quasi-claw-free graphs, namely, quasilocally connected and almost locally connected graphs. Our results include some well-known results on claw-free graphs as special cases. We also give an affirmative answer to a problem proposed by Ainouche.     

Vertex reconstruction in Cayley graphs

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex x from its r-neighbors, that are, vertices at distance at most r from x, consists of finding the minimum restrictions on the number of r-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group and the hyperoctahedral group (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.     

Vertex degrees of planar graphs

Let G be a planar graph having n vertices with vertex degrees d₁, d₂,…,d_n. It is shown that $\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{d}{}_{\mathrm{i}}{}^2\text{≤ 2n}{}^2\text{+ O(n)}$. The main term in this upper bound is best possible.     

Vertex partitions of r-edge-colored graphs

Let G be an edge-colored graph.The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G.In the authors' previous work,it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P=NP.In this paper the authors show that for any fixed integer r≥5,if the edges of a graph G are colored by r colors,called an r-edge-colored graph,the problem remains NP-complete.Similar result holds for the monochromatic path(cycle)partition problem.Therefore,to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

A note on infinite transitive graphs

In [4] Jung and Watkins proved that for a connected infinite graph X either κ_∞(X) = ∞ holds or X is a strip, if Aut(X) contains a transitive abelian subgroup G. Here we prove the same result under weaker assumptions.     

Decomposing oriented graphs into transitive tournaments

For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then and there are tournaments for which f(G)>n²/3000. For general G we prove that f(G)?⌊n²/3⌋ and this is tight. Some related parameters are also considered.     

On transitive decompositions of disconnected graphs

We investigate transitive decompositions of disconnected graphs, and show that these behave very differently from a related class of algebraic graph decompositions, known as homogeneous factorisations. We conclude that although the study of homogeneous factorisations admits a natural reduction to those cases where the graph is connected, the study of transitive decompositions does not.     

On transitive one-factorizations of arc-transitive graphs

It is shown that transitive 1-factorizations of arc-transitive graphs exist if and only if certain factorizations of their automorphism groups exist. This relation provides a method for constructing and characterizing transitive 1-factorizations for certain classes of arc-transitive graphs. Then a characterization is given of 2-arc-transitive graphs which have transitive 1-factorizations. In this characterization, some 2-arc transitive graphs and their transitive 1-factorizations are constructed.     

On cyclic edge-connectivity of transitive graphs

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G. In this paper, we first prove that for any cyclically separable graph G, , where ω(X) is the number of edges with one end in X and the other end in V(G)?X. A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected k-regular vertex-transitive graph with k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal.     

Quasiconformality of the injective mappings transforming spheres to quasispheres

We prove that every injective mapping of a domain \(D \subset \overline {{\mathbb{R}^n}} \) transforming spheres Σ ? D to K-quasispheres (the images of spheres under K-quasiconformal automorphisms of \(\overline {{\mathbb{R}^n}} \)) is K′-quasiconformal with K′ depending only on K and tending to 1 as K → 1. This is a quasiconformal analog of the classical Carathéodory Theorem on the Möbius property of an injective mapping of a domain D ? Rⁿ which sends spheres to spheres.