東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Automorphic decompositions of graphs.

Beeler, Robert A.

Linked to FindBook

Google Book

Amazon

博客來

Automorphic decompositions of graphs.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Automorphic decompositions of graphs./
Author:	Beeler, Robert A.
Description:	165 p.
Notes:	Adviser: Robert E. Jamison.
Contained By:	Dissertation Abstracts International68-07B.
Subject:	Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3274292
ISBN:	9780549149651

Automorphic decompositions of graphs.
Beeler, Robert A.

Automorphic decompositions of graphs. - 165 p.

Adviser: Robert E. Jamison.

Thesis (Ph.D.)--Clemson University, 2007.

Let G and H be graphs. A G -decomposition D of a graph H is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. It is well known that a graceful labelling (or more generally a rho-valuation) of a graph G induces a cyclic G-decomposition of a complete graph. We will extend these notions to that of a general valuation in a cyclic group. Such valuations yield decompositions of circulant graphs. We will show that every graph has a valuation and hence is a divisor of arbitrarily large circulant graphs. The problem of which graphs can host a decomposition by a graph G is much more difficult and is still open.

ISBN: 9780549149651Subjects--Topical Terms:

515831
Mathematics.

Automorphic decompositions of graphs.
LDR:03624nam 2200301 a 45 001 954005
005 20110621
008 110622s2007 ||||||||||||||||| ||eng d
020 $a 9780549149651
035 $a (UMI)AAI3274292
035 $a AAI3274292
040 $a UMI $c UMI
100 1 $a Beeler, Robert A. $3 1277483
245 1 0 $a Automorphic decompositions of graphs.
300 $a 165 p.
500 $a Adviser: Robert E. Jamison.
500 $a Source: Dissertation Abstracts International, Volume: 68-07, Section: B, page: 4518.
502 $a Thesis (Ph.D.)--Clemson University, 2007.
520 $a Let G and H be graphs. A G -decomposition D of a graph H is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. It is well known that a graceful labelling (or more generally a rho-valuation) of a graph G induces a cyclic G-decomposition of a complete graph. We will extend these notions to that of a general valuation in a cyclic group. Such valuations yield decompositions of circulant graphs. We will show that every graph has a valuation and hence is a divisor of arbitrarily large circulant graphs. The problem of which graphs can host a decomposition by a graph G is much more difficult and is still open.
520 $a Let D be a G-decomposition of H. The intersection graph generated by the decomposition D, denoted I(D), has a vertex for each part of the partition and an edge if the parts of the partition share a common node in H. While the problem of determining whether a G-decomposition of H exists is a well-studied one, the structure of the resulting intersection graph has not been the subject of much research. As such, we are interested in the structure of these graphs. Of specific interest is whether there exist H, G, and a G-decomposition of H such that the resulting intersection graph is isomorphic to H. A decomposition D such that I(D) &cong; H is said to be automorphic ("self-shaped"). If a graph H is able to host an automorphic decomposition, then we say that H is an automorphic host. Similarly, if there exists an H such that there exists an automorphic G-decomposition of H, then we say that G is an automorphic divisor.
520 $a In this dissertation, we will give several necessary conditions for the existence of an automorphic G-decomposition of H. These will allow us to examine the problem of which graphs are automorphic hosts. We conjecture that only even regular graphs are able to host an automorphic decomposition. In an attempt to prove this conjecture, we have shown the following special cases: (1) If chi(H) ≤ 3, then H is 2e(G)-regular. (2) If chi( H) = n(G) and G is d-regular, then H is n( G)d-regular. (3) If chi(H) = n(G), G is not a disjoint union of P2's, and the smallest elements of dseq(G) are 1 and a, where a ≥ 2e(G) - n(G) + 1, then H must be 2 e(G)-regular. (4) If G &cong; P4 and chi(H) = 4, then H is 6-regular. (5) If G is d-regular and any two blocks share at most one common node in H, then H is n(G)d-regular.
520 $a This dissertation will also examine the problem of which graphs are automorphic divisors. We conjecture that every graph is an automorphic divisor. In an attempt to prove this, we generalize our notion of a valuation for arbitrary groups. This allows us to consider direct products of the related valuations.
590 $a School code: 0050.
650 4 $a Mathematics. $3 515831
690 $a 0405
710 2 $a Clemson University. $b Mathematical Science. $3 1023032
773 0 $t Dissertation Abstracts International $g 68-07B.
790 $a 0050
790 1 0 $a Jamison, Robert E., $e advisor
791 $a Ph.D.
792 $a 2007
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3274292