Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Mathematics
Domination Numbers Of Semi-Strong Products Of Graphs, Stephen R. Cheney
Domination Numbers Of Semi-Strong Products Of Graphs, Stephen R. Cheney
Theses and Dissertations
This thesis examines the domination number of the semi-strong product of two graphs G and H where both G and H are simple and connected graphs. The product has an edge set that is the union of the edge set of the direct product of G and H together with the cardinality of V(H), copies of G. Unlike the other more common products (Cartesian, direct and strong), the semi-strong product is neither commutative nor associative.
The semi-strong product is not supermultiplicative, so it does not satisfy a Vizing like conjecture. It is also not submultiplicative so it shares these two …
Coloring The Square Of Planar Graphs Without 4-Cycles Or 5-Cycles, Robert Jaeger
Coloring The Square Of Planar Graphs Without 4-Cycles Or 5-Cycles, Robert Jaeger
Theses and Dissertations
The famous Four Color Theorem states that any planar graph can be properly colored using at most four colors. However, if we want to properly color the square of a planar graph (or alternatively, color the graph using distinct colors on vertices at distance up to two from each other), we will always require at least \Delta + 1 colors, where \Delta is the maximum degree in the graph. For all \Delta, Wegner constructed planar graphs (even without 3-cycles) that require about \frac{3}{2} \Delta colors for such a coloring.
To prove a stronger upper bound, we consider only planar graphs …