Strong Transitivity and Graph Maps

Katsuya Yokoi

Displaying similar documents to “Strong Transitivity and Graph Maps”

Hexavalent $(G, s)$ -transitive graphs

Song-Tao Guo, Xiao-Hui Hua, Yan-Tao Li (2013)

Czechoslovak Mathematical Journal

Similarity:

Let $X$ be a finite simple undirected graph with a subgroup $G$ of the full automorphism group $Aut (X)$ . Then $X$ is said to be $(G, s)$ -transitive for a positive integer $s$ , if $G$ is transitive on $s$ -arcs but not on $(s + 1)$ -arcs, and $s$ -transitive if it is $(Aut (X), s)$ -transitive. Let $G_{v}$ be a stabilizer of a vertex $v \in V (X)$ in $G$ . Up to now, the structures of vertex stabilizers $G_{v}$ of cubic, tetravalent or pentavalent $(G, s)$ -transitive graphs are known. Thus, in this paper, we give the structure of the vertex stabilizers $G_{v}$ of connected hexavalent...

Arc-transitive and s-regular Cayley graphs of valency five on Abelian groups

Mehdi Alaeiyan (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a finite group, and let $1_{G} \notin S \subseteq G$ . A Cayley di-graph Γ = Cay(G,S) of G relative to S is a di-graph with a vertex set G such that, for x,y ∈ G, the pair (x,y) is an arc if and only if $y x^{- 1} \in S$ . Further, if $S = S^{- 1} : = s^{- 1} | s \in S$ , then Γ is undirected. Γ is conected if and only if G = ⟨s⟩. A Cayley (di)graph Γ = Cay(G,S) is called normal if the right regular representation of G is a normal subgroup of the automorphism group of Γ. A graph Γ is said to be arc-transitive, if Aut(Γ) is transitive on an arc set. Also,...

On Lee's conjecture and some results

Lixia Fan, Zhihe Liang (2009)

Discussiones Mathematicae Graph Theory

Similarity:

S.M. Lee proposed the conjecture: for any n > 1 and any permutation f in S(n), the permutation graph P(Pₙ,f) is graceful. For any integer n > 1 and permutation f in S(n), we discuss the gracefulness of the permutation graph P(Pₙ,f) if $f = \prod_{k = 0}^{l - 1} (m + 2 k, m + 2 k + 1)$ , and $\prod_{k = 0}^{l - 1} (m + 4 k, m + 4 k + 2) (m + 4 k + 1, m + 4 k + 3)$ for any positive integers m and l.

Iterated neighborhood graphs

Martin Sonntag, Hanns-Martin Teichert (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V, E_{N})$ where $E_{N}$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^{k} (G) : = N (N (. . . N (G)))$ of G. In particular we investigate conditions for G and k such that $N^{k} (G)$ becomes a complete graph.

A Ramsey-style extension of a theorem of Erdős and Hajnal

Peter Komjáth (2001)

Fundamenta Mathematicae

Similarity:

If n, t are natural numbers, μ is an infinite cardinal, G is an n-chromatic graph of cardinality at most μ, then there is a graph X with $X \to (G) ¹_{μ}$ , |X| = μ⁺, such that every subgraph of X of cardinality < t is n-colorable.

Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

Ewa Drgas-Burchardt (2009)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^{a}$ denote a class of all such properties. In the paper, we consider H-reducible over $L^{a}$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

On infinite uniquely partitionable graphs and graph properties of finite character

Jozef Bucko, Peter Mihók (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property is of finite character if a graph G has a property if and only if every finite induced subgraph of G has a property . Let ₁,₂,...,ₙ be graph properties of finite character, a graph G is said to be (uniquely) (₁, ₂, ...,ₙ)-partitionable if there is an (exactly one) partition V₁, V₂, ..., Vₙ of V(G) such that $G [V_{i}] \in_{i}$ for i = 1,2,...,n. Let us denote by ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ the class...

Remarks on partially square graphs, hamiltonicity and circumference

Hamamache Kheddouci (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In the case where G is a claw-free graph, G* is equal to G². We define $σ ° ₜ = m i n \sum_{x \in S} d_{G} (x) : S i s a n i n d e p e n d e n t s e t i n G * a n d | S | = t$ . We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

On $k$ -strong distance in strong digraphs

Ping Zhang (2002)

Mathematica Bohemica

Similarity:

For a nonempty set $S$ of vertices in a strong digraph $D$ , the strong distance $d (S)$ is the minimum size of a strong subdigraph of $D$ containing the vertices of $S$ . If $S$ contains $k$ vertices, then $d (S)$ is referred to as the $k$ -strong distance of $S$ . For an integer $k \geq 2$ and a vertex $v$ of a strong digraph $D$ , the $k$ -strong eccentricity ${s e}_{k} (v)$ of $v$ is the maximum $k$ -strong distance $d (S)$ among all sets $S$ of $k$ vertices in $D$ containing $v$ . The minimum $k$ -strong eccentricity among the vertices of $D$ is its $k$ -strong radius...

On perfect and unique maximum independent sets in graphs

Lutz Volkmann (2004)

Mathematica Bohemica

Similarity:

A perfect independent set $I$ of a graph $G$ is defined to be an independent set with the property that any vertex not in $I$ has at least two neighbors in $I$ . For a nonnegative integer $k$ , a subset $I$ of the vertex set $V (G)$ of a graph $G$ is said to be $k$ -independent, if $I$ is independent and every independent subset $I^{'}$ of $G$ with $| I^{'} | \geq | I | - (k - 1)$ is a subset of $I$ . A set $I$ of vertices of $G$ is a super $k$ -independent set of $G$ if $I$ is $k$ -independent in the graph $G [I, V (G) - I]$ , where $G [I, V (G) - I]$ is the bipartite graph obtained from $G$ by deleting...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol&#039;, Tomáš Madaras (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1, 3}$ and $K_{1, 4}$ and a light 4-path P₄. The results obtained for $K_{1, 3}$ and P₄ are best possible.

Intersection graph of gamma sets in the total graph

T. Tamizh Chelvam, T. Asir (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we consider the intersection graph $I_{Γ} (ℤ ₙ)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{Γ} (ℤ ₙ)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{Γ} (ℤ ₙ)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{Γ} (ℤ ₙ)$ .