Faults in software systems often occur due to interactions between parameters. Several studies show that faults are caused by 2-way through 6-way interactions of parameters. In the context of test suite prioritization, we have studied prioritization by 2-way inter-window interaction coverage and found that this criterion is effective at finding faults quickly in the test execution cycle. However, since faults may be caused by interactions between more than 2 parameters, in this paper, we provide a greedy algorithm for test suite prioritization by \( n \)-way combinatorial coverage of inter-window interactions. While greedy algorithms that generate Combinatorial Interaction Test suites enumerate and track the coverage of all possible \( t \)-tuples and constraints, we have noticed that our user-session-based test suites often do not contain every possible \( t \)-tuple, and we can take advantage of this in our algorithm by only storing \( t \)-tuples that appear in the test suite. Our empirical study shows both time and memory usage associated with our algorithm for 3-way inter-window parameter-value interaction coverage. Further, we conduct an empirical study where we compare 2-way and 3-way combinatorial coverage of inter-window parameter interactions in terms of the rate of fault detection for a web application called Schoolmate and a user-session-based test suite. Our results show that the rate of fault detection for 2-way and 3-way prioritization are within \(1\%\) of each other, but 2-way provides a slightly better result. A closer look at the characteristics of the web application, test cases, and faults reveals that most faults are triggered by 2-way interactions. We motivate the need for future work to examine a larger set of empirical studies to identify characteristics of web applications that benefit from prioritization with higher strength inter-window event interaction coverage.

In this work, we present a greedy algorithm for covering the set of incomplete STRIPS planning domain interpretations by \( t \)-strength diagnoses. We present a greedy algorithm to cover the incomplete domain model interpretations with a set of plans by iteratively generating plans so that each additional plan is biased to cover at least one new interpretation not previously covered. We also present a second greedy algorithm to construct a set of plans that covers all \( t \)-strength diagnoses of plan failure for plans in the incomplete domain model. We show that covering domain interpretations by \( t \)-strength diagnoses leads to increased coverage by a set of plans despite potentially lower coverage per plan because covering by \( t \)-strength diagnoses leads to a more scalable approach to planning where more plans can be found.

The article presents the compatibility matrix method and illustrates it with the application to the \( \text{P} \) vs \( \text{NP} \) problem. The method is a generalization of descriptive geometry: in the method, we draft problems and solve them utilizing the image creation technique. The method reveals: \( \text{P} = \text{NP} = \text{PSPACE} \subseteq \text{P/poly} \), etc.

Our previous paper [9] applied a lopsided version of the Lovász Local Lemma that allows negative dependency graphs [5] to the space of random matchings in \( K_{2n} \), deriving new proofs to a number of results on the enumeration of regular graphs with excluded cycles through the configuration model [3]. Here we extend this from excluded cycles to some excluded balanced subgraphs, and derive asymptotic results on the probability that a random regular multigraph from the configuration model contains at least one from a family of balanced subgraphs in question.

The induced path number \( \rho(G) \) of a graph \( G \) is defined as the minimum number of subsets into which the vertex set of \( G \) can be partitioned so that each subset induces a path. A Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum (or product) of a parameter of a graph and its complement. If \( G \) is a subgraph of \( H \), then the graph \( H – E(G) \) is the complement of \( G \) relative to \( H \). In this paper, we consider Nordhaus-Gaddum type results for the parameter \( \rho \) when the relative complement is taken with respect to the complete bipartite graph \( K_{m,n} \).

Rado constructed a (simple) denumerable graph \( R \) with the positive integers as vertex set with the following edges: For given \( m \) and \( n \) with \( m < n \), \( m \) is adjacent to \( n \) if \( n \) has a \( 1 \) in the \( m \)'th position of its binary expansion. It is well known that \( R \) is a universal graph in the set \( \mathcal{I} \) of all countable graphs (since every graph in \( \mathcal{I} \) is isomorphic to an induced subgraph of \( R \)) and that \( R \) can be characterized using this notion and that of being homogeneous and having the extension property. In this paper, we extend these notions to arbitrary induced-hereditary properties (of graphs), relate them to the construction of a universal graph for any such property, and obtain results which remind one of some characterizations of \( R \).

In this note, we prove that for any tree \( T \), \( \gamma_{\leq2}(T) \leq \gamma_\gamma(T) \leq ir(T) \leq \gamma(T) \), where \( \gamma_{\leq2}(G) \) is the distance-2 domination number, \( ir(T) \) is the (lower) irredundance number, \( \gamma(T) \) is the domination number, and \( \gamma_\gamma(T) \), newly defined here, equals the minimum cardinality of a set of vertices that dominates a minimum dominating set of \( T \).

A graph is \((k, l)\)-colorable if its vertex set can be partitioned into \( k \) independent sets and \( l \) cliques. A graph is chordal if it does not contain any induced cycle of length at least four. A theorem by Hell et al. states that a chordal graph is \((k, l)\)-colorable if and only if it does not contain \((l+1)K_{k+1}\) as an induced subgraph. Presented here is a short alternative proof of this result, using the characterization of chordal graphs via perfect elimination orderings.

A subset \( X \) of the vertex set of a graph \( G \) is a secure dominating set of \( G \) if \( X \) is a dominating set of \( G \) and if, for each vertex \( u \) not in \( X \), there is a neighboring vertex \( v \) of \( u \) in \( X \) such that the swap set \( (X – \{v\}) \cup \{u\} \) is again a dominating set of \( G \). The secure domination number of \( G \), denoted by \( \gamma_s(G) \), is the cardinality of a smallest secure dominating set of \( G \). In this paper, we present two algorithms (a branch-and-reduce algorithm as well as a branch-and-bound algorithm) for determining the secure domination number of a general graph \( G \) of order \( n \). The worst-case time complexities of both algorithms are \( \mathcal{O}(2^{n-s-\sum_{i=1}^{k}(|\mathcal{R}_i|-1)}) \), where \( s \) is the number of support vertices in \( G \) and \( \mathcal{R}_i, \ldots, \mathcal{R}_k \) are the redundancy classes of \( G \) (two vertices are in the same redundancy class if they are adjacent and share the same closed neighborhood which forms a clique in \( G \)).

The distinguishing chromatic number of a graph \( G \) is the least integer, \( \chi_D(G) \), for which \( G \) has a coloring of its vertices so that adjacent vertices receive different colors, and the identity is the only automorphism of \( G \) that preserves vertex colors. Our focus is on determining the distinguishing chromatic numbers of wreath products of graphs, extending the work of Tang. We prove that if \( C_n \) is a cycle with \( n \) vertices and \( P_n \) is a path with \( n \) vertices, then \( \chi_D(C_n[G]) \) and \( \chi_D(P_n[G]) \) can be found for any connected graph \( G \). We also obtain an upper bound on \( \chi_D(T[G]) \) when \( T \) is a tree and \( G \) is any connected graph. Some of our results depend on the notion of inequivalent colorings. Cheng introduces inequivalent colorings and provides a formula for computing the number of inequivalent distinguishing \( k \)-colorings of a rooted tree. We add to this work by obtaining an expression for computing the number of inequivalent distinguishing \( k \)-colorings of a cycle.