Arabic
Bulgarian
Chinese
Croatian
Czech
Danish
Dutch
English
Estonian
Finnish
French
German
Greek
Hebrew
Hindi
Hungarian
Icelandic
Indonesian
Italian
Japanese
Korean
Latvian
Lithuanian
Malagasy
Norwegian
Persian
Polish
Portuguese
Romanian
Russian
Serbian
Slovak
Slovenian
Spanish
Swedish
Thai
Turkish
Vietnamese

Arabic
Bulgarian
Chinese
Croatian
Czech
Danish
Dutch
English
Estonian
Finnish
French
German
Greek
Hebrew
Hindi
Hungarian
Icelandic
Indonesian
Italian
Japanese
Korean
Latvian
Lithuanian
Malagasy
Norwegian
Persian
Polish
Portuguese
Romanian
Russian
Serbian
Slovak
Slovenian
Spanish
Swedish
Thai
Turkish
Vietnamese

definition of Wikipedia

Advertizing ▼

In the mathematical field of graph theory, a graph *G* is **symmetric** (or **arc-transitive**) if, given any two pairs of adjacent vertices *u*_{1}—*v*_{1} and *u*_{2}—*v*_{2} of *G*, there is an automorphism

*f*:*V*(*G*) →*V*(*G*)

such that

*f*(*u*_{1}) =*u*_{2}and*f*(*v*_{1}) =*v*_{2}.^{[1]}

In other words, a graph is symmetric if its automorphism group acts transitively upon ordered pairs of adjacent vertices (that is, upon edges considered as having a direction).^{[2]} Such a graph is sometimes also called **1-arc-transitive**^{[2]} or **flag-transitive**.^{[3]}

By definition (ignoring *u*_{1} and *u*_{2}), a symmetric graph without isolated vertices must also be vertex transitive.^{[1]} Since the definition above maps one edge to another, a symmetric graph must also be edge transitive. However, an edge-transitive graph need not be symmetric, since *a*—*b* might map to *c*—*d*, but not to *d*—*c*. Semi-symmetric graphs, for example, are edge-transitive and regular, but not vertex-transitive.

Graph families defined by their automorphisms | ||||

distance-transitive | distance-regular | strongly regular | ||

symmetric (arc-transitive) |
t-transitive, t ≥ 2 |
|||

_{(if connected)} |
||||

vertex- and edge-transitive | edge-transitive and regular | edge-transitive | ||

vertex-transitive | regular | |||

Cayley graph | skew-symmetric | asymmetric |

Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree.^{[3]} However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric.^{[4]} Such graphs are called half-transitive.^{[5]} The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices.^{[1]}^{[6]} Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above.

A distance-transitive graph is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.^{[1]}

A *t*-arc is defined to be a sequence of *t*+1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A ** t-transitive graph** is a graph such that the automorphism group acts transitively on

## Contents |

Combining the symmetry condition with the restriction that graphs be cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. The **Foster census** and its extensions provide such lists.^{[7]} The Foster census was begun in the 1930s by Ronald M. Foster while he was employed by Bell Labs,^{[8]} and in 1988 (when Foster was 92^{[1]}) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.^{[9]} The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices^{[10]}^{[11]} (ten of these are also distance transitive; the exceptions are as indicated):

Vertices |
Diameter |
Girth |
Graph |
Notes |
---|---|---|---|---|

4 | 1 | 3 | The complete graph K_{4} |
distance transitive, 2-transitive |

6 | 2 | 4 | The complete bipartite graph K_{3,3} |
distance transitive, 3-transitive |

8 | 3 | 4 | The vertices and edges of the cube | distance transitive, 2-transitive |

10 | 2 | 5 | The Petersen graph | distance transitive, 3-transitive |

14 | 3 | 6 | The Heawood graph | distance transitive, 4-transitive |

16 | 4 | 6 | The Möbius–Kantor graph | 2-transitive |

18 | 4 | 6 | The Pappus graph | distance transitive, 3-transitive |

20 | 5 | 5 | The vertices and edges of the dodecahedron | distance transitive, 2-transitive |

20 | 5 | 6 | The Desargues graph | distance transitive, 3-transitive |

24 | 4 | 6 | The Nauru graph (the generalized Petersen graph G(12,5)) | 2-transitive |

26 | 5 | 6 | The F26A graph^{[11]} |
1-transitive |

28 | 4 | 7 | The Coxeter graph | distance transitive, 3-transitive |

30 | 4 | 8 | The Tutte–Coxeter graph | distance transitive, 5-transitive |

Other well known cubic symmetric graphs are the Dyck graph, the Foster graph and the Biggs–Smith graph. The ten distance-transitive graphs listed above, together with the Foster graph and the Biggs–Smith graph, are the only cubic distance-transitive graphs.

Non-cubic symmetric graphs include cycle graphs (of degree 2), complete graphs (of degree 4 or more when there are 5 or more vertices), hypercube graphs (of degree 4 or more when there are 16 or more vertices), and the graphs formed by the vertices and edges of the octahedron, icosahedron, cuboctahedron, and icosidodecahedron. The Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree.

The vertex-connectivity of a symmetric graph is always equal to the degree *d*.^{[3]} In contrast, for vertex-transitive graphs in general, the vertex-connectivity is bounded below by 2(*d*+1)/3.^{[2]}

A *t*-transitive graph of degree 3 or more has girth at least 2(*t*–1). However, there are no finite *t*-transitive graphs of degree 3 or more for *t* ≥ 8. In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for *t* ≥ 6.

- ^
^{a}^{b}^{c}^{d}^{e}^{f}Biggs, Norman (1993).*Algebraic Graph Theory*(2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8. - ^
^{a}^{b}^{c}Godsil, Chris; Royle, Gordon (2001).*Algebraic Graph Theory*. New York: Springer. p. 59. ISBN 0-387-95220-9. - ^
^{a}^{b}^{c}Babai, L (1996). "Automorphism groups, isomorphism, reconstruction". In Graham, R; Groetschel, M; Lovasz, L.*Handbook of Combinatorics*. Elsevier. http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps. **^**Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.**^**Gross, J.L. and Yellen, J. (2004).*Handbook of Graph Theory*. CRC Press. p. 491. ISBN 1-58488-090-2.**^**Holt, Derek F. (1981). "A graph which is edge transitive but not arc transitive".*Journal of Graph Theory***5**(2): 201–204. DOI:10.1002/jgt.3190050210..**^**Marston Conder,*Trivalent symmetric graphs on up to 768 vertices,*J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63**^**Foster, R. M. "Geometrical Circuits of Electrical Networks."*Transactions of the American Institute of Electrical Engineers***51**, 309–317, 1932.**^**"The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2**^**Biggs, p. 148- ^
^{a}^{b}Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

- Cubic symmetric graphs (The Foster Census). Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
- Trivalent (cubic) symmetric graphs on up to 2048 vertices. Marston Conder, August 2006, retrieved 2009-08-20.

sensagent's content

- definitions
- synonyms
- antonyms
- encyclopedia

Dictionary and translator for handheld

New : sensagent is now available on your handheld

Advertising ▼

Webmaster Solution

Alexandria

A windows (pop-into) of information (full-content of Sensagent) triggered by double-clicking any word on your webpage. Give contextual explanation and translation from your sites !

SensagentBox

With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.

Business solution

Improve your site content

Add new content to your site from Sensagent by XML.

Crawl products or adds

Get XML access to reach the best products.

Index images and define metadata

Get XML access to fix the meaning of your metadata.

Please, email us to describe your idea.

Lettris

Lettris is a curious tetris-clone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.

boggle

Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !

English dictionary

Main references

Most English definitions are provided by WordNet .

English thesaurus is mainly derived from The Integral Dictionary (TID).

English Encyclopedia is licensed by Wikipedia (GNU).

Copyrights

The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.

The web service Alexandria is granted from Memodata for the Ebay search.

The SensagentBox are offered by sensAgent.

Translation

Change the target language to find translations.

Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.

last searches on the dictionary :

The Key to Time ·
Tirlemont ·
Magma (comics) ·
JANET PARSHALL ·
Gulf of Kvarner ·
Sudbury School ·
siege of vienna ·
versity ·
Frizzle Sizzle ·
Rotex ·

2062 online visitors

computed in 0.031s

I would like to report:

section :

a spelling or a grammatical mistake

an offensive content(racist, pornographic, injurious, etc.)

a copyright violation

an error

a missing statement

other

please precise: