Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Tetravalent s-Transitive Graphs of Order 4p 2

Let s be a positive integer. A graph is s -transitive if its automorphism group is transitive on s-arcs but not on (s?+?1)-arcs. Let p be a prime. Zhou (Discrete Math 309:6081?C6086, 2009) classified tetravalent s-transitive graphs of order 4p. In this article a complete classification of tetravalent s-transitive graphs of order 4p ² is given.     

On symmetric graphs of valency five

A graph X, with a subgroup G of the automorphism group of X, is said to be (G,s)-transitive, for some s≥1, if G is transitive on s-arcs but not on (s+1)-arcs, and s-transitive if it is -transitive. Let X be a connected (G,s)-transitive graph, and G_v the stabilizer of a vertex v∈V(X) in G. If X has valency 5 and G_v is solvable, Weiss [R.M. Weiss, An application of p-factorization methods to symmetric graphs, Math. Proc. Camb. Phil. Soc. 85 (1979) 43-48] proved that s≤3, and in this paper we prove that G_v is isomorphic to the cyclic group Z₅, the dihedral group D₁₀ or the dihedral group D₂₀ for s=1, the Frobenius group F₂₀ or F₂₀×Z₂ for s=2, or F₂₀×Z₄ for s=3. Furthermore, it is shown that for a connected 1-transitive Cayley graph of valency 5 on a non-abelian simple group G, the automorphism group of is the semidirect product , where R(G) is the right regular representation of G and .     

Secure domination critical graphs

A secure dominating set X of a graph G is a dominating set with the property that each vertex u∈V_G−X is adjacent to a vertex v∈X such that (X−{v})∪{u} is dominating. The minimum cardinality of such a set is called the secure domination number, denoted by γ_s(G). We are interested in the effect of edge removal on γ_s(G), and characterize γ_s-ER-critical graphs, i.e. graphs for which γ_s(G−e)>γ_s(G) for any edge e of G, bipartite γ_s-ER-critical graphs and γ_s-ER-critical trees.     

Factor-critical property in 3-dominating-critical graphs

A vertex subset S of a graph G is a dominating set if every vertex of G either belongs to S or is adjacent to a vertex of S. The cardinality of a smallest dominating set is called the dominating number of G and is denoted by γ(G). A graph G is said to be γ-vertex-critical if γ(G−v)<γ(G), for every vertex v in G.Let G be a 2-connected K_1,5-free 3-vertex-critical graph of odd order. For any vertex v∈V(G), we show that G−v has a perfect matching (except two graphs), which solves a conjecture posed by Ananchuen and Plummer [N. Ananchuen, M.D. Plummer, Matchings in 3-vertex critical graphs: The odd case, Discrete Math., 307 (2007) 1651-1658].     

Degree Sum Conditions for Cyclability in Bipartite Graphs

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d _G (v) be the degree of a vertex v in a graph G. For G[X, Y] and ${S \subseteq V(G),}$ we define ${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$ . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ _1,1(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| ≥ |Y| and ${S \subseteq V(G)}$ such that σ _1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or ${|S \cap X| > |Y|}$ and there exists a cycle containing Y. This degree sum condition is sharp.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

Every 4-Connected Line Graph of a Planar Graph is Hamiltonian

Let G be a graph withE(G) $#x2260;ø. The line graph of G, written L(G) hasE(G) as its vertex set, where two vertices are adjacent in L(G) if and only if the corresponding edges are adjacent inG. Thomassen conjectured that all 4-connected line graphs are hamiltonian [2]. We show that this conjecture holds for planar graphs.     

Eccentric sequences and eccentric sets in graphs

By a graph we mean a finite undirected connected graph of order p, p ? 2, with no loops or multiple edges. A finite non-decreasing sequence S: s₁, s₂, …, s_p, p ? 2, of positive integers is an eccentric sequence if there exists a graph G with vertex set V(G) = {v₁, v₂, …, v_p} such that for each i, 1 ? i ? p, s, is the eccentricity of v₁. A set S is an eccentric set if there exists a graph G such that the eccentricity ρ(v₁) is in S for every v₁ ? V(G), and every element of S is the eccentricity of some vertex in G. In this note we characterize eccentric sets, and we find the minimum order among all graphs whose eccentric set is a given set, to obtain a new necessary condition for a sequence to be eccentric. We also present some properties of graphs having preassigned eccentric sequences.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

Relations between (κ, τ)-regular sets and star complements

Let G be a finite graph with an eigenvalue µ of multiplicity m. A set X of m vertices in G is called a star set for µ in G if µ is not an eigenvalue of the star complement G\X which is the subgraph of G induced by vertices not in X. A vertex subset of a graph is (κ, τ)-regular if it induces a κ-regular subgraph and every vertex not in the subset has τ neighbors in it. We investigate the graphs having a (κ, τ)-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.     

Degree Distance of Unicyclic Graphs with Given Matching Number

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as ${D'(G) = \sum_{\{u, v\}\subseteq V(G)} (d_G(u) + d_G (v))\, d(u,v)}$ , where d _G (u) is the degree of vertex u, d(u, v) denotes the distance between u and v, and the summation goes over all pairs of vertices in G. In this paper, we characterize n-vertex unicyclic graphs with given matching number and minimal degree distance.     

On regular graphs,V

Let Γ₃ be an infinite regular tree of valence 3. There exist subgroups B of Aut (Γ₃) which are 5-regular on Γ₃, i.e., sharply transitive on the set of 5-arcs of Γ₃. We prove that any two such subgroups are conjugate in Aut (Γ₃). The pair (Γ₃, B) is a universal 5-regular action in the sense that if (G, A) is a pair consisting of a cubical graph G and a 5-regular subgroup A of automorphisms of G then (G, A) can be “covered” by (Γ₃, B) in a certain natural way.     

Tetravalent Edge-transitive Cayley Graphs of PGL （2, p）

t Let F = Cay（G, S）, R（G） be the right regular representation of G. The graph Г is called normal with respect to G, if R（G） is normal in the full automorphism group Aut（F） of F. Г is called a bi-normal with respect to G if R（G） is not normal in Aut（Г）, but R（G） contains a subgroup of index 2 which is normal in Aut（F）. In this paper, we prove that connected tetravalent edge-transitive Cayley graphs on PGL（2,p） are either normal or bi-normal when p ≠ 11 is a prime.     

Super s-restricted edge-connectivity of vertex-transitive graphs

Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k5 and girth g5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.     

On geodetic sets formed by boundary vertices

Let G be a finite simple connected graph. A vertex v is a boundary vertex of G if there exists a vertex u such that no neighbor of v is further away from u than v. We obtain a number of properties involving different types of boundary vertices: peripheral, contour and eccentric vertices. Before showing that one of the main results in [G. Chartrand, D. Erwin, G.L. Johns, P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003) 25-34] does not hold for one of the cases, we establish a realization theorem that not only corrects the mentioned wrong statement but also improves it.Given S⊆V(G), its geodetic closure I[S] is the set of all vertices lying on some shortest path joining two vertices of S. We prove that the boundary vertex set ∂(G) of any graph G is geodetic, that is, I[∂(G)]=V(G). A vertex v belongs to the contour Ct(G) of G if no neighbor of v has an eccentricity greater than v. We present some sufficient conditions to guarantee the geodeticity of either the contour Ct(G) or its geodetic closure I[Ct(G)].     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

A Classification of Graphs Whose Subdivision Graph is Locally Distance Transitive

The subdivision graph S(Σ) of a connected graph Σ is constructed by adding a vertex in the middle of each edge. In a previous paper written with Cheryl E. Praeger, we characterised the graphs Σ such that S(Σ) is locally (G, s)-distance transitive for s ≤ 2 diam(Σ) ? 1 and some G?≤ Aut(Σ). In this paper, we solve the remaining cases by classifying all the graphs Σ such that S(Σ) is locally (G, s)-distance transitive for some s?≥ 2 diam(Σ) and some G?≤ Aut(Σ). As a corollary, we get a classification of all the graphs whose subdivision graph is locally distance transitive.     

On intransitive graph-restrictive permutation groups

Let Γ be a finite connected G-vertex-transitive graph and let v be a vertex of Γ. If the permutation group induced by the action of the vertex-stabiliser G _v on the neighbourhood Γ(v) is permutation isomorphic to L, then (Γ,G) is said to be locally L. A permutation group L is graph-restrictive if there exists a constant c(L) such that, for every locally L pair (Γ,G) and a vertex v of Γ, the inequality |G _v |≤c(L) holds. We show that an intransitive group is graph-restrictive if and only if it is semiregular.