Wyniki wyszukiwania

1

On Two Generalized Connectivities of Graphs

100%

Sun Y., Li F., Jin Z.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 38

|

nr 1

245-261

EN

The concept of generalized k-connectivity κk(G), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity τk(G) was also introduced by Hager in 1985, which is a specialization of generalized k-connectivity but a generalization of the classical connectivity. Another generalized connectivity of a graph G, named k-connectivity κ′k(G), introduced by Chartrand et al. in 1984, is a generalization of the cut-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of κ′k(G) and τk(G) by showing that for a connected graph G of order n, if κ′k(G) ≠ n − k + 1 where k ≥ 3, then 1 ≤ κ′k(G) − τk(G) ≤ n − k; otherwise, 1 ≤ κ′k(G) ‘− τk(G) ≤ n − k + 1. Moreover, all of these bounds are sharp. We get a sharp upper bound for the 3-connectivity of the Cartesian product of any two connected graphs with orders at least 5. Especially, the exact values for some special cases are determined. Among our results, we also study the pendant tree-connectivity of Cayley graphs on Abelian groups of small degrees and obtain the exact values for τk(G), where G is a cubic or 4-regular Cayley graph on Abelian groups, 3 ≤ k ≤ n.

2

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

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

100%

Alaeiyan M.

Discussiones Mathematicae Graph Theory

|

2006

|

tom 26

|

nr 3

359-368

EN

Let G be a finite group, and let $1_G ∉ S ⊆ 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 $yx^{-1} ∈ S$. Further, if $S = S^{-1}:= {s^{-1}|s ∈ 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, a graph Γ is s-regular if Aut(Γ) acts regularly on the set of s-arcs. In this paper, we first give a complete classification for arc-transitive Cayley graphs of valency five on finite Abelian groups. Moreover, we classify s-regular Cayley graph with valency five on an abelian group for each s ≥ 1.

3

Some applications of pq-groups in graph theory

75%

Exoo G.

Discussiones Mathematicae Graph Theory

|

2004

|

tom 24

|

nr 1

109-114

EN

We describe some new applications of nonabelian pq-groups to construction problems in Graph Theory. The constructions include the smallest known trivalent graph of girth 17, the smallest known regular graphs of girth five for several degrees, along with four edge colorings of complete graphs that improve lower bounds on classical Ramsey numbers.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

1 Alaeiyan M.

1 Exoo G.

1 Jin Z.

1 Li F.

1 Sun Y.

1 2018

1 2006

1 2004

On Two Generalized Connectivities of Graphs

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

Some applications of pq-groups in graph theory