# Vertex-primitive graphs of valency 5

N/A
N/A
Protected

Share "Vertex-primitive graphs of valency 5"

Copied!
50
0
0

Full text

(1)

## Vertex-primitive graphs of valency 5

Gabriel Verret

The University of Western Australia

Symmetries and Covers of Discrete Objects, Queenstown February 18th 2016

(2)

## Primitive groups

G is a permutation groupon a finite set Ω.

G is transitiveif, for every two elements of Ω, there is an element ofG mapping one to the other.

G is primitiveif it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

(3)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G is primitiveif it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

(4)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G isprimitive if it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

(5)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G isprimitive if it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

(6)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G isprimitive if it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

(7)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless).

They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K2. Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(8)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2).

They are vertex-transitive and thus regular.

Valency 1 =⇒ K2. Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(9)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K2. Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(10)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K2.

Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(11)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K2. Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(12)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K2. Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(13)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K2. Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(14)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K2. Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

(15)

## Vertex-primitive graphs of valency 5

Aut(Γ) Aut(Γ)v |V(Γ)|

Z42oSym(5) Sym(5) 16 PΓL(2,9) AGL(1,5)×Z2 36

PGL(2,11) D10 66

Sym(9) Sym(4)×Sym(5) 126 Suz(8) AGL(1,5) 1 456 J3o2 AΓL(2,4) 17 442

Th Sym(5) 756 216 199 065 600

Aut(Γ) Aut(Γ)v |V(Γ)| Conditions PSL(2,p) Alt(5) p1203−p p ≡ ±1,±9 (mod 40) PΣL(2,p2) Sym(5) p6120−p2 p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) p9(p6−1)(p2404−1)(p2−1) p ≡ ±1 (mod 8) PGSp(6,p) Sym(5) p9(p6−1)(p1204−1)(p2−1) p≡ ±3 (mod 8), p ≥11 (Note K6 hiding sneakily...)

(16)

## Vertex-primitive graphs of valency 5

Aut(Γ) Aut(Γ)v |V(Γ)|

Z42oSym(5) Sym(5) 16 PΓL(2,9) AGL(1,5)×Z2 36

PGL(2,11) D10 66

Sym(9) Sym(4)×Sym(5) 126 Suz(8) AGL(1,5) 1 456 J3o2 AΓL(2,4) 17 442

Th Sym(5) 756 216 199 065 600 Aut(Γ) Aut(Γ)v |V(Γ)| Conditions PSL(2,p) Alt(5) p1203−p p ≡ ±1,±9 (mod 40) PΣL(2,p2) Sym(5) p6120−p2 p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) p9(p6−1)(p2404−1)(p2−1) p ≡ ±1 (mod 8) PGSp(6,p) Sym(5) p9(p6−1)(p1204−1)(p2−1) p≡ ±3 (mod 8), p ≥11

(Note K6 hiding sneakily...)

(17)

## Vertex-primitive graphs of valency 5

Aut(Γ) Aut(Γ)v |V(Γ)|

Z42oSym(5) Sym(5) 16 PΓL(2,9) AGL(1,5)×Z2 36

PGL(2,11) D10 66

Sym(9) Sym(4)×Sym(5) 126 Suz(8) AGL(1,5) 1 456 J3o2 AΓL(2,4) 17 442

Th Sym(5) 756 216 199 065 600 Aut(Γ) Aut(Γ)v |V(Γ)| Conditions PSL(2,p) Alt(5) p1203−p p ≡ ±1,±9 (mod 40) PΣL(2,p2) Sym(5) p6120−p2 p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) p9(p6−1)(p2404−1)(p2−1) p ≡ ±1 (mod 8) PGSp(6,p) Sym(5) p9(p6−1)(p1204−1)(p2−1) p≡ ±3 (mod 8), p ≥11 (Note K6 hiding sneakily...)

(18)

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

(19)

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

(20)

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

(21)

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

(22)

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

(23)

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit). 2 =⇒G ∼=Dp.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)). 5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

(24)

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=Dp.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)). 5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

(25)

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=Dp.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)). 5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

(26)

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=Dp.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)). 5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

(27)

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=Dp.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)).

5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

(28)

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=Dp.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)).

5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

(29)

## Idea of proof

Let ∆ be asuborbit of length 5 forGω.

Wang (1995,1996) dealt with the case when Gω is soluble, or whenGω is insoluble and unfaithful. (With a few omissions.) It remains to deal with the case whenGω is isomorphic to Alt(5) orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

(30)

## Idea of proof

Let ∆ be asuborbit of length 5 forGω.

Wang (1995,1996) dealt with the case whenGω is soluble, or whenGω is insoluble and unfaithful.

(With a few omissions.) It remains to deal with the case whenGω is isomorphic to Alt(5) orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

(31)

## Idea of proof

Let ∆ be asuborbit of length 5 forGω.

Wang (1995,1996) dealt with the case whenGω is soluble, or whenGω is insoluble and unfaithful. (With a few omissions.)

It remains to deal with the case whenGω is isomorphic to Alt(5) orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

(32)

## Idea of proof

Let ∆ be asuborbit of length 5 forGω.

Wang (1995,1996) dealt with the case whenGω is soluble, or whenGω is insoluble and unfaithful. (With a few omissions.) It remains to deal with the case whenGω is isomorphic to Alt(5) orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

(33)

## Idea of proof

Let ∆ be asuborbit of length 5 forGω.

Wang (1995,1996) dealt with the case whenGω is soluble, or whenGω is insoluble and unfaithful. (With a few omissions.) It remains to deal with the case whenGω is isomorphic to Alt(5) orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

(34)

## Idea of proof

Let ∆ be asuborbit of length 5 forGω.

Wang (1995,1996) dealt with the case whenGω is soluble, or whenGω is insoluble and unfaithful. (With a few omissions.) It remains to deal with the case whenGω is isomorphic to Alt(5) orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

(35)

## Almost simple groups with a maximal Sym(5)

G m Conditions

Alt(7) 1 M11 1 M12o Z2 1 J2o Z2 1

Th 2

PSL(2,52) 1

PΣL(2,p2) 2 p≡ ±3 (mod 10) PSL(2,22r)o Z2 1 r odd prime

PGL(2,5r) 1 r odd prime PSL(3,4)ohσi 1 σ a graph-field aut.

PSL(3,5) 1

PSp(6,p) 2 p≡ ±1 (mod 8) PGSp(6,3) 1

PGSp(6,p) 2 p ≡ ±3 (mod 8), p≥11 m:=|NG(Sym(4)) :Sym(4)|

(36)

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups

2. Classical groups

3. Lie groups of exceptional type

≈7×1014, order≈9×1016)

(37)

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type

≈7×1014, order≈9×1016)

(38)

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type

≈7×1014, order≈9×1016)

(39)

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type 4. Sporadic groups

≈7×1014, order≈9×1016)

(40)

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type

≈7×1014, order≈9×1016)

(41)

## Consequence: half-arc-transitive graphs

A graph ishalf-arc-transitiveif its automorphism group is transitive on edges and vertices but not on arcs.

No vertex-primitive half-arc-transitive graph of valency at most 10. There are examples of valency 14.

This leaves valency 12...

(42)

## Consequence: half-arc-transitive graphs

A graph ishalf-arc-transitiveif its automorphism group is transitive on edges and vertices but not on arcs.

No vertex-primitive half-arc-transitive graph of valency at most 10.

There are examples of valency 14. This leaves valency 12...

(43)

## Consequence: half-arc-transitive graphs

A graph ishalf-arc-transitiveif its automorphism group is transitive on edges and vertices but not on arcs.

No vertex-primitive half-arc-transitive graph of valency at most 10.

There are examples of valency 14.

This leaves valency 12...

(44)

## Consequence: half-arc-transitive graphs

A graph ishalf-arc-transitiveif its automorphism group is transitive on edges and vertices but not on arcs.

No vertex-primitive half-arc-transitive graph of valency at most 10.

There are examples of valency 14.

This leaves valency 12...

(45)

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type). 2. Once we have the graphs, we still have to do a little extra

work.

(46)

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type). 2. Once we have the graphs, we still have to do a little extra

work.

(47)

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type). 2. Once we have the graphs, we still have to do a little extra

work.

(48)

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type). 2. Once we have the graphs, we still have to do a little extra

work.

(49)

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type).

2. Once we have the graphs, we still have to do a little extra work.

(50)

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type).

2. Once we have the graphs, we still have to do a little extra work.

References

Related documents

We discuss related results along two strands: the problem of finding decompositions of large graphs with high minimum degree and the problem of decomposing bipartite graphs

We review the Cartan classification of the primitive infinite-dimensional Lie pseudogroups (and hence of dynamical systems), and select the conformal pseudogroups for further

If it is important that the students in our schools are taught by committed Christian teachers then there is a need to expand our collective efforts to put before Christians

Motivated from the fact that the metaheuristic approach of D-Wave has provided efficient and accurate solutions for many instances of graph theoretic problems, we experimented with

the uniquely defined outer border cycle of M separates one (infinite) background component and a finite number of improper holes from M any inner border cycle of M separates a

We say that a (punctual) structure is punctually categorical if between any two punctual copies of the structure there is a primitive recursive isomorphism with primitive

 For studying Cayley graphs we want to decide existence of regular subgroups maybe in primitive groups – but a graph has a 2-transitive automorphism group only if it is empty

“Leaky” graphs are a more realistic model of graph-like nanostructures because they take quantum tunneling into account.. Summarizing

There will be more vertex-transitive graphs, but essentially we may repeat the same line of arguments to compute the automorphisms. Instead of using full automorphims group we have

You should prove for yourself the vertex form of Menger’s Theorem for undirected graphs.. 8.2

The algorithm accepts a t-parse encoding G of a bounded pathwidth graph as input and returns the minimum dominating number of the underlying graph.. Both s and q are subsets of

(s, δ)-coreset for the problem of computing closed graphs Weighted multiset of frequent δ-tolerance closed graphs with minimum support s using their relative support as

We have described our data-parallel algorithms and CUDA implementations of graph component labelling for the cases of arbitrarily structured graphs and hypercubic data graphs

Graphs in Life: Global Internet Connections.. Graphs in Life: Social

• For planar graphs it has been proven that one can show that a graph does or does not have a branch decomposition of less than or equal to a given branchwidth in true polynomial

By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, so it suﬃces to find all 4-valent arc-transitive graphs

Mar´ıa del R´ıo Francos (IMate, UNAM) Flag graphs and symmetry type graphs SCDO’16, Queenstown,

Theorem ( Zhou &amp; Feng, J. Graph Theory, 2010 ) Let p &gt; q be odd primes and X a connected cubic vertex-transitive non-Cayley graph of order 2pq... Cubic VNC-graphs of order

Theorem 1.1 There is a black-box polynomial-time Monte Carlo algorithm to determine the characteristic of a quasisimple group G of Lie type, subject to the existence of an oracle

For all but E 8 (q) in even characteristic, our algorithms to construct the SL 2 subgroups and to label the root and toral elements are black-box provided that the algorithms

Form appropriate 4 element generating sets and build corresponding Cayley graphs. Take only those graphs that are connected

More generally, G with large abelian factor group may have Cayley graphs with diameter proportional to |G|... The diameter

existence. In making such an estimate, the Government Printer was requested to take as understood that each author body would have its report printed by the