#### Semester

Fall

#### Date of Graduation

1998

#### Document Type

Dissertation

#### Degree Type

PhD

#### College

Eberly College of Arts and Sciences

#### Department

Mathematics

#### Committee Chair

Hong-Jian Lai.

#### Abstract

Let G = (V, E) be a graph and A a non-trivial Abelian group, and let F( G, A) denote the set of all functions f : E (G) → A. Denote by D an orientation of E( G). Then G is A-colorable if and only if for every f ∈ F(G, A) there exists an A-coloring c: V( G) → A such that for every e = (x, y) ∈ E(G) (assumed to be directed from x to y), c( x)--c(y) ≠ f(e). We define the group chromatic number of c1 (G) to be the minimum number m for which G is A-colorable for any Abelian group A of order ≥ m under the orientation D. Chapters 2 and 3 are mainly concerned with group chromatic number and some results are given.;The edge-integrity of a graph G is defined by minS⊆E GS +mG-S , where mG-S denotes the maximum order of a component of G-S . Let I'(G) denote the edge-integrity of a graph G. We define a graph G to be I'-maximal if for every edge e in G, the complement of graph G, I'( G + e) > I'( G). In chapter 4, some results of I' -maximal graphs are established, the girth of a connected I'-maximal graph is given and lower and upper bounds on the size of I'-maximal connected graphs with given order and edge-integrity are investigated. Also, the I'-maximal trees and unicyclic graphs are completely characterized.;For any given edges e1, e 2 in E(G), a spanning trail of G with e1 as the first edge and e2 as the last edge is called a spanning (e 1, e2)-trail. In chapter 5, we consider best possible degree conditions to assure the existence of these trails for every pair of edges e1, e 2 in a 3-edge-connected graph G.

#### Recommended Citation

Zhang, Xiankun, "Generalizations of colorability and connectivity of graphs" (1998). *Graduate Theses, Dissertations, and Problem Reports*. 3122.

https://researchrepository.wvu.edu/etd/3122