A study on equivalence classes of painted graphs
Date Issued
2005
Date
2005
Author(s)
Wu, Hsin-Jung
DOI
en-US
Abstract
A Vogan diagram is a Dynkin diagram with two extra data: There is an automorphism θ on the diagram with θ^2 = 1, and the vertices fixed by θ may be painted or unpainted. Each Vogan diagram corresponds to a real simple
Lie algebra. Two diagrams are said to be equivalent if they represent the same Lie algebra. Borel-de Siebenthal proved that every Vogan diagram with painted vertices is equivalent to one with a single painted vertex. Chuah and
Hu reproved the theorem combinatorially.
We describe Chuah and Hu's work in a more general setting by considering all graphs rather only Dynkin diagrams. Suppose G is a graph. A painting of G is a mapping c : V(G) → Z_2 , for which vertices i with c(i) = 1 (0) are called painted(unpainted). We also call painted(unpainted)vertices black(white). As a painting c and the set B of all black vertices determine each other, we use B as a painting.
For any black vertex i in a painting B, the flip operation F[i] transforms B to the painting BΔN(i),where N(i) = {j : ij in E(G)} and XΔY =(X-Y)∪(Y-X). A painting B_1 is equivalent to another painting B_2 , denoted by B_1 ~ B_2, if B_1 can be transformed to B_2 by a sequence of flips.
We also denote |B| be the number of black vertices of painting B. In a graph G, we use [B] to denote the equivalence class containing a painting B. Define p([B])=min{|A| : A ~B} and p(G) = max{p([B]): B is a painting of G}.
In this thes is we study p(G) for general graphs. In particular, we establish results on trees, cycles, cacti and complete r-partitegraphs.
Subjects
著色圖
painted graphs
Vogandiagram
Dynkindiagram
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R93221031-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):bb0266b5145515d53255ee14cf8b881f