In a graph \( G \), the Steiner distance \( d(S) \) of the vertex subset \( S \subseteq V(G) \) is the minimum size among all connected subgraphs whose vertex sets contain \( S \). The Steiner \( k \)-diameter of a connected graph \( G \) is the maximum \( d(S) \) among all \( k \)-element vertex subsets \( S \subseteq V(G) \).

In this paper, we examine the Steiner \( k \)-diameter for large \( k \) and then discuss the applications of the results.

A set of vertices, \( S \), in a digraph \( D \), is split dominating provided it is:

1. dominating and
2. \( D[V(D) \setminus S] \) is either trivial or has a lower level of connection than \( D \).

In this paper, we consider split dominating sets in strongly connected tournaments. The split domination number of a strongly connected tournament \( T \), denoted by \( \gamma_s(T) \), is the minimum cardinality of a split dominating set for that tournament.

The authors previously gave a tight lower bound for \( \gamma_s(T) \) when \( T \) is regular. In this paper, we show that when \( T \) is a nearly regular \( 2k \)-tournament, then \( \gamma_s(T) \geq \lceil \frac{2k}{3} \rceil \) and this bound is tight.

Redrawing lines for redistricting plans that represent U.S. congressional districts is a tricky business. There are many laws that dictate how lines can and cannot be drawn, such as contiguity. In fact, building all redistricting plans for a single U.S. state is an intractable problem. Researchers have turned to heuristics in order to analyze current redistricting plans. Many of these heuristics (e.g. local search heuristics and Markov chain Monte Carlo algorithms) used by researchers form new congressional districts by switching the smaller pieces (e.g. precincts or census blocks) that make up congressional districts from one congressional district to another.
In this paper, we discuss the various natural definitions involved in satisfying rules for contiguity and simply connectedness of precincts or census blocks and how these relate to contiguity and simply connectedness of congressional districts. We also propose and analyze several constructions to alleviate violations of contiguity and simply connectedness in precincts and census blocks. Finally, we develop efficient algorithms that allow practitioners to assess redistricting plans using local search heuristics or Markov chain Monte Carlo algorithms efficiently.

A set \( S \subseteq V \) is \( \alpha \)-dominating if for all \( v \in V – S \), \( |N(v) \cap S| \geq \alpha |N(v)| \). The \( \alpha \)-domination number of \( G \) equals the minimum cardinality of an \( \alpha \)-dominating set \( S \) in \( G \). Since being introduced by Dunbar et al. in 2000, \( \alpha \)-domination has been studied for various graphs and a variety of bounds have been developed.

In this paper, we propose a new parameter derived by flipping the inequality in the definition of \( \alpha \)-domination. We say a set \( S \subset V \) is a \( \beta \)-packing set of a graph \( G \) if \( S \) is a proper, maximal set having the property that for all vertices \( v \in V – S \), \( |N(v) \cap S| \leq \beta |N(v)| \) for some \( 0 < \beta \leq 1 \). The \( \beta \)-\emph{packing number} of \( G \), denoted \( \beta\text{-pack}(G) \), equals the maximum cardinality of a \( \beta \)-packing set in \( G \).

In this research, we determine \( \beta\text{-pack}(G) \) for several classes of graphs, and we explore some properties of \( \beta \)-packing sets.

A perfect matching of a graph is a subset of edges in the graph such that each vertex is contained in exactly one edge. We study the number of perfect matchings of a given graph. In particular, we are interested in the power of two that divides this number. A new type of vertex set, called a channel, is considered, whose presence is associated with powers of two in the perfect matching count. This provides a method for determining lower bounds on such powers. Algebraic and involutive proofs are given for these results, and methods for channel identification are provided. We specialize to perfect matchings on subgraphs of the square lattice, which are identified with domino tilings of the plane, and apply channels to some conjectures by Pachter.

A dominating set of a graph \( G \) is a set of vertices \( D \) such that for all \( \nu \in V(G) \), either \( \nu \in D \) or \( [\nu,d] \in E(G) \) for some \( d \in D \). The cardinality-redundance of a vertex set \( S \), \( CR(S) \), is the number of vertices \( x \in V(G) \) such that \( |N[x] \cap S| \geq 2 \). The cardinality-redundance of \( G \) is the minimum of \( CR(S) \) taken over all dominating sets \( S \). A set of vertices \( S \) such that \( CR(S) = CR(G) \) is a \( \gamma_{CR} \)-set, and the size of a minimum \( \gamma_{CR} \)-set is denoted \( \gamma_{CR}(G) \).

Here, we are concerned with extremal problems concerning cardinality-redundance. We give the maximum number of edges in a graph with a given number of vertices and given cardinality-redundance. In the cases that \( CR(G) = 0 \) or \( 1 \), we give the minimum and maximum number of edges of graphs when \( \gamma_{CR}(G) \) is fixed, and when \( CR(G) = 2 \), we give the maximum number of edges of graphs where \( \gamma_{CR}(G) \) is fixed. We give the minimum and maximum values of \( \gamma_{CR}(G) \) when the number of edges are fixed and \( CR(G) = 0, 1 \), and we give the maximum values of \( \gamma_{CR}(G) \) when the number of edges are fixed and \( CR(G) = 2 \).

It is known that for a maximal planar graph \( G \) with order \( n \geq 4 \), the independence number satisfies \( \frac{n}{4} \leq \alpha(G) \leq \frac{2n-4}{3} \). We show that the lower bound is sharp and characterize the extremal graphs for \( n \leq 12 \). For the upper bound, we characterize the extremal graphs of all orders.

The independence number \( \alpha(G) \) of a graph \( G \) is the size of the largest independent set. This parameter is difficult to determine in general, but can be bounded on various graph classes. This paper considers planar and maximal planar graphs.

Constraint Programming (CP) is a method used to model and solve complex combinatorial problems. An alternative to Integer Programming for solving large-scale industrial problems, it is, under some circumstances, more efficient than IP, but its strength lies mainly in the use of predicates to model problems. This paper presents the at-least-\( m \)-different predicate and provides a class of facet-defining inequalities of the convex hull of integer solutions. This predicate bounds the number of values that variables in a set may receive. The paper also presents a polynomial-time separation algorithm to be used in the context of a branch-and-bound optimization approach.

Let \( N_2DL(v) \) denote the set of degrees of vertices at distance \( 2 \) from \( v \). The \( 2 \)-neighborhood degree list of a graph is a listing of \( N_2DL(v) \) for every vertex \( v \). A degree restricted \( 2 \)-switch on edges \( v_1v_2 \) and \( w_1w_2 \), where \( \deg(v_1) = \deg(w_1) \) and \( \deg(v_2) = \deg(w_2) \), is the replacement of a pair of edges \( v_1v_2 \) and \( w_1w_2 \) by the edges \( v_1w_2 \) and \( v_2w_1 \), given that \( v_1w_2 \) and \( v_2w_1 \) did not appear in the graph originally. Let \( G \) and \( H \) be two graphs of diameter \( 2 \) on the same vertex set. We prove that \( G \) and \( H \) have the same \( 2 \)-neighborhood degree list if and only if \( G \) can be transformed into \( H \) by a sequence of degree restricted \( 2 \)-switches.