On strongly regular graphs with m2 = qm3 and m3 = qm2

2010 Mathematics Subject Classification: 05C50.

d-Regular Graphs of Acyclic Chromatic Index at Least d+2

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Suclakov and Zaks (and earlier by Fiamcik) that a'(G) <= Delta+2, where Delta = Delta(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require Delta+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d-regular graphs with 2n vertices and d>n, requires at least d+2 colors. We also show that a'(K-n,K-n) >= n+2, when n is odd using a more non-trivial argument. (Here K-n,K-n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn,n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d >= 5, n >= 2d+3 and dn even, there exist d-regular graphs which require at least d+2-colors to be acyclically edge colored. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226-230, 2010.

Main eigenvalues and (κ, τ)-regular sets

A (κ, τ)-regular set is a subset of the vertices of a graph G, inducing a κ-regular subgraph such that every vertex not in the subset has τ neighbors in it. A main eigenvalue of the adjacency matrix A of a graph G has an eigenvector not orthogonal to the all-one vector j. For graphs with a (κ, τ)-regular set a necessary and sufficient condition for an eigenvalue be non-main is deduced and the main eigenvalues are characterized. These results are applied to the construction of infinite families of bidegreed graphs with two main eigenvalues and the same spectral radius (index) and some relations with strongly regular graphs are obtained. Finally, the determination of (κ, τ)-regular sets is analyzed. © 2009 Elsevier Inc. All rights reserved.

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p ≥ 3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. © 2008 Elsevier B.V. All rights reserved.

Energies of some non-regular graphs

The energy of a graph G is the sum of the absolute values of its eigenvalues. In this paper, we study the energies of some classes of non-regular graphs. Also the spectrum of some non-regular graphs and their complements are discussed.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

Groups, graphs and mutually unbiased bases

A new characteristic free approach to constructing large sets of mutually unbiased bases in Hilbert space is developed. We associate with a seed set of bases a finite subgroup of which defines a strongly regular graph. Large sets of mutually unbiased bases are obtained as the cliques of the graph.

Fixed block configuration GDDs with block size 6 and (3, r)-regular graphs

Chapter 1 is used to introduce the basic tools and mechanics used within this thesis. Most of the definitions used in the thesis will be defined, and we provide a basic survey of topics in graph theory and design theory pertinent to the topics studied in this thesis. In Chapter 2, we are concerned with the study of fixed block configuration group divisible designs, GDD(n; m; k; λ1; λ2). We study those GDDs in which each block has configuration (s; t), that is, GDDs in which each block has exactly s points from one of the two groups and t points from the other. Chapter 2 begins with an overview of previous results and constructions for small group size and block sizes 3, 4 and 5. Chapter 2 is largely devoted to presenting constructions and results about GDDs with two groups and block size 6. We show the necessary conditions are sufficient for the existence of GDD(n, 2, 6; λ1, λ2) with fixed block configuration (3; 3). For configuration (1; 5), we give minimal or nearminimal index constructions for all group sizes n ≥ 5 except n = 10, 15, 160, or 190. For configuration (2, 4), we provide constructions for several families ofGDD(n, 2, 6; λ1, λ2)s. Chapter 3 addresses characterizing (3, r)-regular graphs. We begin with providing previous results on the well studied class of (2, r)-regular graphs and some results on the structure of large (t; r)-regular graphs. In Chapter 3, we completely characterize all (3, 1)-regular and (3, 2)-regular graphs, as well has sharpen existing bounds on the order of large (3, r)- regular graphs of a certain form for r ≥ 3. Finally, the appendix gives computational data resulting from Sage and C programs used to generate (3, 3)-regular graphs on less than 10 vertices.

MAXIMAL ARCS, ABOVE AND BEYOND

This report explores combinatorial structures in Finite Geometries by giving known constructions of maximal arcs; using maximal arcs to construct two-weight codes, partial geometries, strongly regular graphs and LDPC codes; a review on how to generalize maximal arcs to higher dimensions through Perp-Systems; and an effort in finding constructions of new Perp-Systems.

Benson's Theorem for Partial Geometries

In 1970 Clark Benson published a theorem in the Journal of Algebra stating a congruence for generalized quadrangles. Since then this theorem has been expanded to other specific geometries. In this thesis the theorem for partial geometries is extended to develop new divisibility conditions for the existence of a partial geometry in Chapter 2. Then in Chapter 3 the theorem is applied to higher dimensional arcs resulting in parameter restrictions on geometries derived from these structures. In Chapter 4 we look at extending previous work with partial geometries with α = 2 to uncover potential partial geometries with higher values of α. Finally the theorem is extended to strongly regular graphs in Chapter 5. In addition we obtain expressions for the multiplicities of the eigenvalues of matrices related to the adjacency matrices of these graphs. Finally, a four lesson high school level enrichment unit is included to provide students at this level with an introduction to partial geometries, strongly regular graphs, and an opportunity to develop proof skills in this new context.

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]