L. Chikamai1, B. G. Rodrigues1, Jamshid Moori2
1School of Mathematical Sciences University of KwaZulu-Natal Durban 4041, South Africa
2School of Mathematical Sciences North-West University (Mafikeng) Mmabatho 2735, South Africa
Abstract:

It is known that there are at least 8784 non-isomorphic designs with parameters \(2-(64, 28, 12)\) whose derived \(2-(28, 12, 11)\) designs are quasi-symmetric. In this paper, we examine the binary codes related to a class of non-isomorphic designs with these parameters and invariant under the Frobenius group of order 21 for which the derived \(2-(28, 12, 11)\) designs are not quasi-symmetric. We show that up to equivalence, there are 30 non-isomorphic binary codes obtained from them. Moreover, we classify the self-orthogonal doubly-even codes of length 13 obtained from the non-fixed parts of orbit matrices of these \(2-(64, 28, 12)\) designs under an action of an automorphism group of order four having 12 fixed points. The subcodes of codimension 1 and minimum weight 8 in these codes are all optimal single weight codes.

Behzad Omidi Koma1, Daniel Panario 1
1School of Mathematics and Statistics, Carleton University Ottawa, ON, K1S 5B6, Canada
Abstract:

Let \( N(n, t_1, \ldots, t_r) \) be the number of irreducible polynomials of degree \( n \) over the finite field \( \mathbb{F}_2 \) where the coefficients of the terms \( x^{n-1}, \ldots, x^{n-r} \) are prescribed. Finding the exact values for the numbers \( N(n, t_1, \ldots, t_r) \) for \( r \geq 4 \) seems difficult. In this paper, we give an approximation for these numbers. We treat in detail the case \( N(n, t_1, \ldots, t_4) \), and we state the approximation in the general case. We experimentally show how good our approximation is.

Christian Altomare1
1Department of Mathematics the Ono State Universtiy 231 WEsT 18TH AVENUE CoLuMBus, OH 43210-1174, USA
Abstract:

The degree sequence of a finite graph \( G \) is its list \( D = (d_1, \ldots, d_n) \) of vertex degrees in non-increasing order. The graph \( G \) is called a realization of \( D \). In this paper, we characterize the graphic degree sequences \( D \) such that no realization of \( D \) contains an induced four-cycle. Our characterization is stated in terms of the class of forcibly chordal graphs.

C. C. Cooley1, W. Ella2, M. Follett3, E. Gilson1, L. Traldi3
1Northwestern University, Evanston IL 60208
2George Washington University, Washington DC 20052
3Lafayette College, Easton PA 18042
Abstract:

A dice family \( D(n, a, b, s) \) includes all lists \( (x_1, \ldots, x_n) \) of integers with \( n \geq 1 \), \( a \leq x_1 \leq \ldots \leq x_n \leq b \), and \( \sum x_i = s \). Given two dice \( X \) and \( Y \), we compare the number of pairs \( (i, j) \) with \( x_i y_j \). If the second number is larger, then \( X \) is \emph{stronger} than \( Y \), and if the two numbers are equal, then \( X \) and \( Y \) are \emph{tied}. In previous work, it has been observed that the density of ties in \( D(n, a, b, s) \) is generally lower than one might expect. In this note, we provide more information about this observation by calculating the asymptotic proportion of ties in certain kinds of dice families. Many other properties of dice families remain to be determined.

Eddie Cheng1, Ke Qiu2, Zhizhang Shen3
1Dept. of Mathematics and Statistics Oakland University Rochester, MI 48309, USA
2Dept. of Computer Science Brock University St. Catharines, Ontario, L2S 3A1, Canada
3Dept. of Computer Science and Technology Plymouth State University Plymouth, NH 03264, USA
Abstract:

After introducing and discussing the notion of length two path centered surface area for general graphs, particularly for bipartite graphs, we derive a closed-form expression and an explicit expression for the length two path centered surface areas of the hypercube and the star graph, respectively.

Roland Lortz1, Ingrid Mengersen2
1Technische Universitit Braunschweig Diskrete Mathematik 38092 Braunschweig, Germany
2Ostfalia Hochschule fiir angewandte Wissenschaften Fakultat Informatik 38302 Wolfenbiittel, Germany
Abstract:

The Ramsey numbers \( r(F, G) \) are investigated, where \( F \) is a non-tree graph of order \( 5 \) and minimum degree \( 1 \), and \( G \) is a connected graph of order \( 6 \). For all pairs \( (F, G) \) where \( F \neq K_5 – K_{1,3} \), the exact value of \( r(F, G) \) is determined. In order to settle \( F = K_5 – K_{1,3} \), we prove \( r(K_5 – K_{1,3}, G) = r(K_4, G) \).

Derek W. Hein1, Dinesh G. Sarvate2
1SouTHERN UTAH University, DEPT. OF MATH., CEDAR CiTy, UT, 84720
2COLLEGE OF CHARLESTON, DEPT. OF MATH., CHARLESTON, SC, 29424
Abstract:

A Stanton-type graph \( S(n, m) \) is a connected multigraph on \( n \) vertices such that for a fixed \( m \) with \( n-1 \leq m \leq \frac{n}{2} \), there is exactly one edge of multiplicity \( i \) (and no others) for each \( i = 1, 2, \ldots, m \). In this note, we show how to decompose \( \lambda K_n \) (for the appropriate minimal values of \( \lambda \)) into Stanton-type graphs \( S(4, 3) \) of the LOE and OLE types.

Eric Andrews1, Chira Lumduanhom1, Ping Zhang1
1Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
D.V. Chopra1, Richard M. Low2, R. Dios3
1Department of Mathematics and Statistics Wichita State University Wichita, KS 67260-0033, USA
2Department of Mathematics San Jose State University San Jose, CA 95192, USA
3Department of Mathematical Sciences New Jersey Institute of Technology Newark, NJ 07102-1982, USA
Abstract:

In this paper, we consider the use of balanced arrays (B-arrays) in constructing discrete fractional factorial designs (FFD) of resolution \((2u+1)\), with \(u=2\) and \(3\), in which each of the \(m\) factors is at two levels (say, \(0\) and \(1\)), denoted by factorial designs of \(2^m\) series. We make use of the well-known fact that such designs can be realized under certain conditions, by using balanced arrays of strength four and six (with two symbols), respectively. Here, we consider the existence of B-arrays of strength \(t=4\) and \(t=6\), and discuss how the results presented can be used to obtain the maximum value of \(m\) for a given set of treatment-combinations. Also, we provide some illustrative examples in which the currently available \(\max(m)\) values have been improved upon.

Gee-Choon Lau1, Sin-Min Lee2, Karl Schaffer3, Siu-Ming Tong4, Samantha Lui5
1Faculty of Computer & Mathematical Sciences Universiti Teknologi MARA (Segamat Campus) 85000, Johore, Malaysia
234803, Hollyhock Street, Union City, CA 94587 USA
3Department of Mathematics De Anza College, Cupertino, CA 95014,USA
4Department of Computer Science Northwestern Polytechnic University Fremont, CA 94539, USA
5Department of Mathematics San Franscisco State University San Franscisco, CA 94132, USA
Abstract:

For integers \( k \geq 1 \), a \((p,q)\)-graph \( G = (V, E) \) is said to admit an AL(\(k\))-traversal if there exists a sequence of vertices \((v_1, v_2, \ldots, v_p)\) such that for each \( i = 1, 2, \ldots, p-1 \), the distance between \( v_i \) and \( v_{i+1} \) is \( k \). We call a graph \( k \)-step Hamiltonian (or say it admits a \( k \)-step Hamiltonian tour) if it has an AL(\(k\))-traversal and \( d(v_1, v_p) = k \). In this paper, we investigate the \( k \)-step Hamiltonicity of graphs. In particular, we show that every graph is an induced subgraph of a \( k \)-step Hamiltonian graph for all \( k \geq 2 \).

Abstract:

A difference system of sets (DSS) is any collection of subsets of \(\mathbb{Z}_n\) with the property that the differences from distinct sets cover \(\mathbb{Z}_n\). That is, every non-zero class in \(\mathbb{Z}_n\) can be written as a difference of classes in at least one way. DSS were introduced by Levenstein in 1971 only for finite fields but the case for just 2 subsets had been previously considered by Clauge. Their work emphasized an application to synchronizable codes. A DSS is triangular if its sets contain only triangular numbers mod \(n\). We show that a triangular DSS cannot exist in \(\mathbb{Z}_{2^k}\) for \(k > 3\).

Michael Burton1, Tara Noble2, Chelynn Day1, Quentin Mayo3
1Computer Science, Utah State University, Logan, UT 84322, USA
2Cognitive, Linguistic & Psychological Sciences, Brown University, Providence, RI 02912, USA
3Computer Science, University of North Texas, Denton, TX 76203, USA
Abstract:

In testing web applications, details of user visits may be recorded in a web log and converted to test cases. This is called user-session-based testing and studies have shown that such tests may be effective at revealing faults. However, for popular web applications with a larger user base, many user-sessions may build up and test suite management techniques are needed. In this paper, we focus on the problem of test suite prioritization. That is, given a large test suite, reorder the test cases according to a criterion that is hypothesized to increase the rate of fault detection. Previous work shows that 2-way combinatorial-based prioritization is an effective prioritization criterion. We develop a greedy algorithm where we consider memory usage and the time that it takes to prioritize test suites. We represent software tests in a graph by storing unique parameters as vertices and \( n \)-way sets as edges or series of edges. Our experiments demonstrate the efficiency of this approach.

Abstract:

The lattice-simplex covering density problem aims to determine the minimal density by which lattice translates of the \( n \)-simplex cover \( n \)-space. Currently, the problem is completely solved in \( 2 \) dimensions. A computer search on the problem in three dimensions gives experimental evidence that for the simplex \( D \) (the convex hull of the unit basis vectors), the most effective lattice corresponds to the tile known as the \( 84 \)-shape. The \( 84 \)-shape tile has been shown to be a local minimum of the density function. We explain the mechanics behind an algorithm which determines the most efficient lattice in the interior of an arbitrary combinatorial type.

Charles J. Colbourn1
1School Of Computing, Informatics, And Decision Systems Engineering, Ari- Zona State University, Tempe Az 85287-8809, U.S.A. And State Key Laboratory Of Sortware Development Environment, Beihang University, Being 100191, China
Abstract:

An efficient conditional expectation algorithm for generating covering arrays has established a number of the best known upper bounds on covering array numbers. Despite its theoretical efficiency, the method requires a large amount of storage and time. In order to extend the range of its application, we generalize the method to find covering arrays that are invariant under the action of a group, reducing the search to consider only orbit representatives of interactions to be covered. At the same time, we extend the method to construct a generalization of covering arrays called quilting arrays. The extended conditional expectation algorithm, as expected, provides a technique for generating covering and quilting arrays that reduces the time and storage required. Remarkably, it also improves on the best known bounds on covering array numbers in a variety of parameter situations.

Eric Andrews1, Ping Zhang1, Chira Lumduanhom1
1Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
Abstract:

Historically, a number of problems and puzzles have been introduced that initially appeared to have no connection to graph colorings but, upon further analysis, suggested graph colorings problems. In this paper, we discuss two combinatorial problems and several graph colorings problems that are inspired by these two problems. We survey recent results and open questions in this area of research as well as some relationships among these coloring parameters and well-known colorings and labelings.

Sin-Min Lee1, Ho Kuen Ng2
1Department of Computer Science San Jose State University San Jose, CA 95192, USA
2Department of Mathematics San Jose State University San Jose, CA 95192, USA
Abstract:

Let \( G \) be a graph with vertex set \( V(G) \) and edge set \( E(G) \), and let \( A \) be an abelian group. A labeling \( f: V(G) \to A \) induces an edge labeling \( f^*: E(G) \to A \) defined by \( f^*(xy) = f(x) + f(y) \) for each edge \( xy \in E(G) \). For \( i \in A \), let \( v_f(i) = |\{v \in V(G) : f(v) = i\}| \), and \( e_f(i) = |\{e \in E(G) : f^*(e) = i\}| \). Define \( c(f) = \{ |e_f(i) – e_f(j)| : (i, j) \in A \times A \} \).

A labeling \( f \) of a graph \( G \) is said to be **A-friendly** if \( |\text{v}_f(i) – \text{v}_f(j)| \leq 1 \) for all \( (i, j) \in A \times A \). If \( c(f) \) is a \( (0,1) \)-matrix for an A-friendly labeling \( f \), then \( f \) is said to be **A-cordial**.

When \( A = \mathbb{Z}_2 \), the friendly index set of the graph \( G \), denoted \( FI(G) \), is defined as \( \{ |e_f(0) – e_f(1)| : \text{the vertex labeling } f \text{ is } \mathbb{Z}_2\text{-friendly} \} \).

In this paper, we completely determine the friendly index sets for two classes of cubic graphs: prisms and Möbius ladders.

Eunjeong Yi1
1Texas A&M University at Galveston, Galveston, TX 77553, USA
Abstract:

A vertex \( x \) in a graph \( G \) strongly resolves a pair of vertices \( v \) and \( w \) if there exists a shortest path from \( x \) to \( w \) that contains \( v \), or a shortest path from \( x \) to \( v \) that contains \( w \) in \( G \). A set of vertices \( S \subseteq V(G) \) is a strong resolving set of \( G \) if every pair of distinct vertices in \( G \) is strongly resolved by some vertex in \( S \). The strong metric dimension \( sdim(G) \) of a graph \( G \) is the minimum cardinality of a strong resolving set of \( G \).

Given two disjoint copies of a graph \( G \), denoted \( G_1 \) and \( G_2 \), and a permutation \( \sigma : V(G_1) \to V(G_2) \), the permutation graph \( G_\sigma = (V, E) \) is defined with vertex set \( V = V(G_1) \cup V(G_2) \) and edge set \( E = E(G_1) \cup E(G_2) \cup \{uv \mid v = \sigma(u)\} \).

We show that for a connected graph \( G \) of order \( n \geq 3 \), the strong metric dimension of \( G_\sigma \) satisfies \( 2 \leq sdim(G_\sigma) \leq 2n – 2 \). We also provide an example demonstrating that there is no function \( f \) such that \( f(sdim(G)) > sdim(G_\sigma) \) for all pairs \( (G, \sigma) \). Additionally, we prove that \( sdim(G_{\sigma_o}) \leq 2sdim(G) \) when \( \sigma_o \) is the identity permutation.

Further, we characterize permutation graphs \( G_\sigma \) that satisfy \( sdim(G_\sigma) = 2n – 2 \) or \( 2n – 3 \) when \( G \) is a complete \( k \)-partite graph, a cycle, or a path on \( n \) vertices.

Eric Freden1, Michael Grady2
1Department of Mathematics, Southern Utah University, Cedar City UT
2Department Computer Science & Informations Systems, Southern Utah Univer- Sity, Cedar City UT
Abstract:

In a recent paper, E. Gelman provided an exact formula for the number of subgroups of a given index for the Baumslag-Solitar groups \( \text{BS}(p, q) \) when \( p \) and \( q \) are coprime. We use Gelman’s proof as the basis for an algorithm that computes a maximal set of inequivalent permutation representations of \( \text{BS}(p, q) \) with degree \( n \). The computational complexity of this algorithm is linear in both space and time with respect to the index. We compare the performance of this algorithm with the Todd-Coxeter procedure, which generally lacks a polynomial bound on the number of cosets used during the enumeration process.

Dinesh G. Sarvate1, Li Zhang1
1Department of Mathematics Department of Mathematics College of Charleston and Computer Science Charleston, SC 29424 The Citadel
Abstract:

An \( H_2 \) graph is a multigraph on three vertices with a double edge between one pair of distinct vertices and a single edge between the other two pairs. The problem of decomposing a complete multigraph \( 3K_{8t} \) into \( H_2 \) graphs has been completely solved. In this paper, we describe some new procedures for such decompositions and pose the following question: Can these procedures be adapted or extended to provide a unified proof of the existence of \( H_2(8t, \lambda) \)’s?

Futaba Fujie1, Ping Zhang2
1Graduate School of Mathematics Nagoya University Nagoya, 464-8602 Japan
2Department of Mathematics Western Michigan University Kalamazoo, MI 46008 USA
Abstract:

For a nontrivial connected graph \( G \) of order \( n \) and a cyclic ordering \( s: v_1, v_2, \ldots, v_n, v_{n+1} = v_1 \) of \( V(G) \), let \( d(s) = \sum_{i=1}^n d(v_i, v_{i+1}) \), where \( d(v_i, v_{i+1}) \) is the distance between \( v_i \) and \( v_{i+1} \) for \( 1 \leq i \leq n \). The Hamiltonian number \( h(G) \) and the upper Hamiltonian number \( h^+(G) \) of \( G \) are defined as:

  1. \( h(G) = \min \{ d(s) \} \), where the minimum is taken over all cyclic orderings \( s \) of \( V(G) \).
  2. \( h^+(G) = \max \{ d(s) \} \), where the maximum is taken over all cyclic orderings \( s \) of \( V(G) \).

All connected graphs \( G \) with \( h^+(G) = h(G) \) and \( h^+(G) = h(G) + 1 \) have been characterized in [6, 13]. In this note, we first present a new and significantly improved proof of the characterization of all graphs whose Hamiltonian and upper Hamiltonian numbers differ by 1. We then determine all pairs of integers that can be realized as the order and upper Hamiltonian number of some tree.

E-mail Alert

Add your e-mail address to receive upcoming issues of Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC).

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;