Discrete Mathematics and Combinatorics Commons^™

An Edge-Swap Heuristic For Finding Dense Spanning Trees, Mustafa Ozen, Hua Wang, Kai Wang, Demet Yalman

Theory & Applications of Graphs

Finding spanning trees under various restrictions has been an interesting question to researchers. A "dense" tree, from a graph theoretical point of view, has small total distances between vertices and large number of substructures. In this note, the "density" of a spanning tree is conveniently measured by the weight of a tree (defined as the sum of products of adjacent vertex degrees). By utilizing established conditions and relations between trees with the minimum total distance or maximum number of sub-trees, an edge-swap heuristic for generating "dense" spanning trees is presented. Computational results are presented for randomly generated graphs and specific …

An Extremal Problem For Finite Lattices, John Goldwasser, Brendan Nagle, Andres Saez

Theory & Applications of Graphs

For a fixed M x N integer lattice L(M,N), we consider the maximum size of a subset A of L(M,N) which contains no squares of prescribed side lengths k(1),...,k(t). We denote this size by ex(L(M,N), {k(1),...,k(t)}), and when t = 1, we abbreviate this parameter to ex(L(M,N), k), where k = k(1).

Our first result gives an exact formula for ex(L( …

Gallai-Ramsey Number Of An 8-Cycle, Jonathan Gregory

College of Graduate Studies: Theses & Dissertations

Given a graph G and a positive integer k, define the Gallai-Ramsey number to be the minimum number of vertices n such that any k-edge-coloring of Kn contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this work, we establish the Gallai-Ramsey number of an 8-cycle for all positive integers.

A Class Of Graphs Approaching Vizing's Conjecture, Aziz Contractor, Elliot Krop

Theory & Applications of Graphs

For any graph G=(V,E), a subset S ⊆ V dominates G if all vertices are contained in the closed neighborhood of S, that is N[S]=V. The minimum cardinality over all such S is called the domination number, written γ(G). In 1963, V.G. Vizing conjectured that γ(G □ H) ≥ γ(G)γ(H) where □ stands for the Cartesian product of graphs. In this note, we define classes of graphs Α_n, for n≥0, so that every graph belongs to some such class, and Α₀ corresponds to class A of Bartsalkin and German. We prove that …