Qing-De Kang 1, Zhi-He Liang 2
1Mathematics Department Hebei Normal College Shijiazhuang 050091 P.R. China
2Mathematics Department Hebei Educational College Shijiazhuang 050091 P.R. China
Abstract:

A covering of the complete directed symmetric graph \(DK_v\) by \(m\)-circuits, denoted by \((v,m) – {DCC}\), is a family of \(m\)-circuits in \(DK_v\) whose union is \(DK_v\). The covering number \(C(v,m)\) is the minimum number of \(m\)-circuits in such a covering.

The covering problem is to determine the value \(C(v,m)\) for every integer \(v \geq m\). In this paper, the problem is reduced to the case \(m+5 \leq v \leq 2m – 4\), for any fixed even integer \(m \geq 4\).

In particular, the values of \(C(v,m)\) are completely determined for \(m = 12, 14,\) and \(16\). Additionally, a directed construction of optimal \((6k + 11, 4k + 6) – {DCC}\) is given.

Yusheng Li1
1 Department of Mathematical Sciences The University of Memphis Memphis, Tennessee 38152
Abstract:

It is shown that if \(H\) is a connected graph obtained from \(H_1\) and \(H_2\) by joining them with a bridge, then \(r(K_k, H) \leq r(K_k, H_1) + r(K_k, H_2) + k – 2\). We give some applications of this result.

E.J. Cockayne1, P.J.P. Grobler2, S.T. Hedetniemi 3, A.A. McRae 4
1 Department of Mathematics University of Victoria P.O. Box 3045 Victoria BC Canada V8W 3P4
2Department of Mathematics, Applied Mathematics and Astronomy University of South Africa P.O. Box 392 Pretoria, 0001 South Africa
3Department of Computer Science Clemson University Clemson, South Carolina USA 29634-1906
4Department of Computer Science Appalachian State University Boone, North Carolina USA 28608
Abstract:

Two closely related types of vertex subsets of a graph, namely external redundant sets and weak external redundant sets, together with associated parameters, are discussed. Both types may be used to characterize those irredundant subsets of a graph which are maximal.

Sandra Hedetniemi 1, Stephen T. Hedetniemi1, Michael A. Henning2
1 Department of Computer Science Clemson University Clemson, SC 29634-1906
2Department of Mathematics University of Natal Private Bag X01 Pietermaritzburg, 3209 South Africa
Abstract:

Let \(G\) be a graph and let \(S\) be a subset of vertices of \(G\). A vertex \(v\) of \(G\) is called perfect with respect to \(S\) if \(|N[v] \cap S| = 1\), where \(N[v]\) denotes the closed neighborhood of \(v\). The set \(S\) is defined to be a perfect neighborhood set of \(G\) if every vertex of \(G\) is perfect or adjacent with a perfect vertex.

The perfect neighborhood number \(\theta(G)\) of \(G\) is defined to be the minimum cardinality among all perfect neighborhood sets of \(G\). In this paper, we present a variety of algorithmic results on the complexity of perfect neighborhood sets in graphs.

L. Gewali1, R. Venkatasubramanian1, D. Glasser1
1 HRH College of Engineering, University of Nevada, Las Vegas
Abstract:

We consider the problem of sweeping (or grazing) the interior/exterior of a polygon by a flexible rope whose one endpoint (anchor) is attached on the boundary of the polygon. We present a linear-time algorithm to compute the grazing area inside a simple polygon. We show how to extend the algorithm for computing the internal grazing area, without increasing its time complexity, to compute the grazing area in the exterior of a simple polygon. For grazing in the exterior of a convex polygon, we present an \(O(n)\) time algorithm to locate the anchor point that maximizes the simple grazing area. All three algorithms are optimal within a constant factor. Grazing area problems can be viewed as guard placement problems under \(L\)-visibility.

R.E. Sabin 1
1Computer Science Department Loyola College Baltimore, MD 21210 USA
Abstract:

Forming all distinct subsets with \(k\) or fewer objects from a set with \(n\) elements can be accomplished by generating a subset of the binary reflected Gray code. This paper presents a straightforward algorithm that generates the desired Gray codewords by altering the stack which maintains the transition sequence that determines the next codeword position to be altered.

Gary Chartrand1, Heather Gavlas1, Robert C. Vandell1, Frank Harary2
1Department of Mathematics and Statistics Western Michigan University Kalamazoo, MI 49008
2 Department of Computer Science New Mexico State University Las Cruces, NM 88003
Abstract:

A vertex of a graph \(G\) dominates itself and its neighbors. A set \(S\) of vertices of \(G\) is a dominating set if each vertex of \(G\) is dominated by some vertex of \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a dominating set of \(G\). A minimum dominating set is one of cardinality \(\gamma(G)\). A subset \(T\) of a minimum dominating set \(S\) is a forcing subset for \(S\) if \(S\) is the unique minimum dominating set containing \(T\). The forcing domination number \(f(S, \gamma)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\), and the forcing domination number \(f(G, \gamma)\) of \(G\) is the minimum forcing domination number among the minimum dominating sets of \(G\). For every graph \(G\), \(f(G, \gamma) \leq \gamma(G)\).

It is shown that for integers \(a, b\) with \(b\) positive and \(0 \leq a \leq b\), there exists a graph \(G\) such that \(f(G, \gamma) = a\) and \(\gamma(G) = b\). The forcing domination numbers of several classes of graphs are determined, including complete multipartite graphs, paths, cycles, ladders, and prisms. The forcing domination number of the cartesian product \(G\) of \(k\) copies of the cycle \(C_{2k+1}\) is studied. Viewing the graph \(G\) as a Cayley graph, we consider the algebraic aspects of minimum dominating sets in \(G\) and forcing subsets.

Thomas Niessen1
1Institute of Statistics, RWTH Aachen 52056 Aachen, Federal Republic of Germany
Abstract:

The complete stability \(cs(P_k)\), where \(P_k\) denotes the property of having a \(k\)-factor, satisfies \(cs(P_k) = n + k – 2, \text{ if } 1 \leq k \leq 3\), and \(n + k – 2 \leq cs(P_k) \leq n + k – 1, \text{ if } k \geq 4\). A similar result for bipartite graphs with complete biclosure is proved also.

A. Gyarfast1, A. Jagotat2, R.H. Schelpt2
1omputer and Automation Institute, Hungarian Academy of Sciences Budapest, Hungary
2Department of Mathematical Sciences, University of Memphis Memphis, TN, 38152
Abstract:

It is known that in every 2-coloring of the edges of the complete graph there exist two vertex disjoint paths—one red, one blue—that collectively cover all the vertices. In this paper, analogous existence and efficiency questions are examined when edges are missing from the complete graph. The main result shows the existence of a path cover when at most \(\left\lfloor{n}/{2}\right\rfloor\) edges are missing. An example shows this result is sharp. A second result shows that a path cover can be found efficiently if a matching is missing.

Frank Harary1, Aurora Morgana 2, Bruno Simeone 3
1Department of Computer Science New Mexico State University
2Dipartimento di Matematica Universita di Roma “La Sapienza”
3Dipartimento di Statistica Probabilité e Statistiche Applicate Universita di Roma “La Sapienza”
Abstract:

A map shows only the names of some (but not all) towns in a region. If for each town, the names of all neighboring towns are known, when is it possible to reconstruct from this information the missing names? We deal with a generalization of this problem to arbitrary graphs. For a graph \(G = (V, E)\) with \(n\) nodes, we give an \(O(n^3)\) algorithm to recognize those instances for which the answer is YES, as well as two characterization theorems: NO-instances are determined by the existence of a certain partition of \(V\) and YES-instances by the existence of a suitable weak order in \(V\).

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;