MIGHTY XXXVI

Abstracts

Do you teach Taylor's Theorem discretely?

Allen Schwenk
Western Michigan University

    American colleges thoroughly introduce our students to calculus, but do we take the time to convey an equal awareness of analogous discrete methods? As a case in point, consider Taylor's Theorem, a staple of second semester
calculus.  Do your students know the discrete version?

On a Restricted Vertex Isoperimetric Problem

 

Sergei Bezrukov
Victor Piotrowski*
University of Wisconsin-Superior

A bipartite graph has a natural structure of a two level ranked poset. The Shadow Minimization Problem (SMP) on that poset is equivalent to the graph Vertex Isoperimetric Problem (VIP) restricted to one of the partite sets. We call it a Restricted Vertex Isoperimetric Problem (RVIP). The only known solution to RVIP is for the n-cube. In this talk, we study relations between VIP and RVIP on Cartesian powers of bipartite graphs, including a new version of a local-global principle with respect to the simplicial order. We also provide applications to the theory of Macaulay posets and to enumeration problems in coding theory.

Convex Subset Lattices of Clone-Free Multipartite Tournaments

 

Darren B. Parker*
Randall F. Westhoff
Marty J. Wolf

Abstract: The collection of convex subsets of a digraph forms a lattice under inclusion.  The lattice structure has been studied by John Pfaltz, who used a somewhat restrictive definition of convexity, and by Jules Varlet, who looked at convex subsets of tournaments.  Our focus is on multipartite tournaments, specifically those without clones (i.e. pairs of vertices with identical arc orientations).  We study the breadth of the lattice of convex subsets of various classes of clone-free tournaments, deriving upper bounds in the case of clone-free tournaments, and certain clone-free regular multipartite tournaments.  We also prove results on bipartite tournaments of breadth 2.

 Gamma-Set Domination Graphs:
Complete Biorientations of Trees

 

Kim Factor

Domination graphs have been studied for tournaments and other digraphs in general.  Two vertices u and v dominate in a digraph D if for any other vertex z, (u,z) is an arc in D or (z,u) is an arc in D .  The domination graph of D, dom(D), is constructed using the vertex set of D and placing an edge between every dominating pair of vertices.  In a graph, the minimum number of vertices needed to dominate all vertices in G is referred to as γ(G), the domination number of G.  Replacing every edge {u,v} in a graph G with arcs (u,v) and (v,u), creates the complete biorientation of G.  When γ(G)>2, the domination number of the complete biorientation of G is the null graph.  So in this talk, we explore the creation of  gamma-set domination graphs, where each gamma-set in G creates a copy of K_γ  in the γ-set domination graph of the complete biorientation.  When γ = 2, the problem becomes that of dom(D).  Here, complete biorientations of trees are the subject of discussion.

Minimum dominating sets of the 2 ^j-cube

William D. Weakley

Indiana - Purdue University at Fort Wayne

For a graph G, a dominating set is a set D of vertices of G such that every vertex of G is either in D or adjacent to a vertex in D. Let γ(Q_n) denote the minimum size of a dominating set of the binary hypercube of dimension n. For j>0 and n = 2 ^j, it is known that γ(Q_n) = 2· γ(Q_n-1) = 2^n-j. We show that for n = 2 ^j, any minimum dominating set of Q_n gives a packing of Q_n using at most two kinds of subgraphs. A general method of constructing such dominating sets is given.

The Detour Number of a Graph

 

Garry Johns*
Saginaw Valley State University
Gary Chartrand and Ping Zhang
Western Michigan University

For vertices u and v in a graph G, the detour distance D(u, v) is the length of a longest uv path in G.  The closed detour interval for vertices u and v consists of vertices u and v and all vertices on any longest uv path of G.  A set S of vertices is a detour set if the union of closed detour intervals for all pairs of vertices in S includes every vertex of G.  Finally, the detour number of G is the minimum cardinality of a detour set.  In this talk, bounds will be given for the detour numbers for various classes of graphs and relationships will be determined between the detour number and structural features of a graph (such as the number of blocks, cut-vertices, and geodesics).

The Hub Number of a Graph

 

Chip Vandell*
Matt Walsh

    For a graph G, a hub set H is a subset of the vertex set such that for any pair of vertices u , v in G - H, there is a uv – path with all internal vertices in H. The hub number h(G) is defined to be the order of the smallest hub set of G. In this talk we will explore this definition, and give formulas for some infinite classes of graphs.

 

Classifying Trees with Edge-Deleted Central Appendage Number 2

Shubhangi Stalder*
University of Wisconsin Waukesha
Linda Eroh, John Koker, Hosien S. Moghadam, Steven J. Winters
University of Wisconsin Oshkosh

The eccentricity of a vertex v of a connected graph G is the distance from v to a vertex farthest from v in G. The center of G is the subgraph of G induced by the vertices having minimum eccentricity. For a vertex v in a 2-edge-connected graph G, the edge-deleted eccentricity of v is defined to be the maximum eccentricity of v in G – e over all edges e of G. The edge-deleted center of G is the subgraph induced by those vertices of G having minimum edge-deleted eccentricity. The edge-deleted central appendage number of a graph G is the minimum difference |V(H)| – |V(G)| over all graphs H where the edge-deleted center of H is isomorphic to G. We will talk about the edge-deleted central appendage number of all trees.

Vertex magic total labeling of Cartesian products of cycles

 

Dalibor Froncek
Petr Kovar
Tereza Kovarova *

University of Minnesota, VSB - Technical University of Ostrava

    A vertex-magic total labeling of a graph G (V, E) is defined as one-to-one mapping from the set of integers {1,2, . . . ,|V|+|E|} to VÈE with the property that the sum of the label of a vertex and the labels of all edges adjacent to this vertex is the same constant for all vertices of the graph.
    In the talk we present some labeling techniques for cycles. We construct labelings, which are not vertex magic total, but the sums on vertices form an arithmetic sequence with difference 1 or 2. These labelings of cycles allow us to construct vertex magic total labeling of Cartesian products of odd cycles as well as Cartesian products of some even cycles and odd cycles.

 

Vertex magic total labeling of Cartesian products of some vertex magic total regular graphs and odd cycles

 

Dalibor Froncek
Petr Kovar *
Tereza Kovarova

University of Minnesota, VSB -- Technical University of Ostrava

    A vertex-magic total labeling of a graph G (V, E) is defined as one-to-one mapping from the set of integers {1,2, . . ., |V|+|E|} to VÈE with the property that the sum of the label of a vertex and the labels of all edges adjacent to this vertex is the same constant for all vertices of the graph.
    In the talk we present some more labeling techniques for cycles. We construct labelings, which are not vertex magic total, but the sums on vertices form an arithmetic sequence with difference 4. These labelings of cycles allow us to construct vertex magic total labeling of Cartesian products of odd cycles and some 4-regular graphs with  ‘nice’ vertex magic total labeling.
    We present the main idea of this construction on Cartesian products of  K₅ and odd cycles, vertex magic total labeling of `drums' and their Cartesian products with odd cycles. If time permits, vertex magic total labeling for some other classes of graphs will be presented.

Non-traditional round robin tournaments

Dalibor Froncek*
University of Minnesota Duluth and Technical University Ostrava
Mariusz Meszka
University of Mining and Metallurgy Kraków

    Many sports competitions are played as 2-leg round robin tournaments with 2n teams. They are usually scheduled in such a way that a 1-leg tournament with 2n–1 rounds is repeated twice. The home and away games of every team should interchange as regularly as possible provided that each team meets every opponent once at its own field and once at the opponent's field. The best home-away pattern (HAP) is indeed one with no two consecutive home or away games (called a break in the schedule). Obviously, one can never find a schedule with no breaks—in this case the teams that start the season with a home game would never meet. Therefore, looking at HAPs, the best schedule is one with the minimum number of breaks. This number in a 1-leg round robin tournaments is 2n–2, as proved by de Werra.
    We will show that if each team has exactly one bye, we can construct schedules with no breaks, and that these schedules are unique.
    Another way to minimize the number of away breaks is based on team locations. If two teams share a home field, then when they meet they both play a home game. However, even if we consider 2n teams where there are n such pairs, there is no schedule with the minimum number of rounds, 2n–2, and no away breaks. On the other hand, we show that there exists a schedule with only n–1 away breaks.
    We may also discuss schedules of incomplete round robin tournaments and their connection to 1 vertex magic vertex graph labeling.