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.