Peter Horak1, Salem Al Yakoob 1
1Department of Mathematics and Computer Science Kuwait: University, P.O.Box 5969 Safat 13060, Kuwait
Abstract:

We give a necessary and sufficient condition of Hall’s type for a family of sets of even cardinality to be decomposable into two subfamilies having a common system of distinct representatives. An application of this result to partitions of Steiner Triple Systems into small configurations is presented.

Peter Adams1, Elizabeth J. Billington1, C.C. Lindner 2
1 Centre for Discrete Mathematics and Computing, Department of Mathematics, The University of Queensland, Queensland 4072 Australia
2Department of Discrete and Statistical Sciences 120 Math Annex Auburn University Auburn Alabama 36849-5307 U.S.A.
Abstract:

In this paper, we construct 2-factorizations of Kn (n odd) containing a specified number, k, of 6-cycles, for all integers k between 0 and the maximum possible expected number of 6-cycles in any 2-factorization, and for all odd n, with no exceptions.

Martin BACA 1, Yuqing LIN 2, Mirka MILLER 3
1 Department of Applied Mathematics Technical University, Kogice, Slovak Republic
2 Department of Computer Science and Software Engineering The University of Newcastle, Australia
3Department of Computer Science and Software Engineering The University of Newcastle, Australia
Abstract:

We deal with (a,d)-face antimagic labelings of a certain class of plane quartic graphs. A connected plane graph G=(V,E,F) is said to be (a,d)-\emph{face antimagic} if there exist positive integers a and d, and a bijection g:E(G){1,2,,|E(G)|} such that the induced mapping φg:F(G)N, defined by φg(f)={g(e):eE(G) adjacent to face f}, is injective and φg(F)={a,a+d,,a+(|F(G)|1)d}.

Mahesh Andar1, Samina Boxwala2, N. B. Limaye 3
1Department of Mathematics N. Wadia College, Pune
2 Department of Mathematics N. Wadia College, Pune
3 Department of Mathematics University of Mumbai Vidyanagari, Mumbai 400098, India
Abstract:

Let G be a graph with vertex set V and edge set E. A vertex labelling f:V{0,1} induces an edge labelling f¯:E{0,1} defined by f¯(uv)=|f(u)f(v)|. Let vf(0),vf(1) denote the number of vertices v with f(v)=0 and f(v)=1 respectively. Let ef(0),ef(1) be similarly defined. A graph is said to be cordial if there exists a vertex labeling f such that |vf(0)vf(1)|1 and |ef(0)ef(1)|1. In this paper, we show that for every positive integer t and n the following families are cordial: (1) Helms Hn. (2) Flower graphs FLn. (3) Gear graphs Gn. (4) Sunflower graphs SFLn. (5) Closed helms CHn. (6) Generalised closed helms CH(t,n). (7) Generalised webs W(t,n).

Lutz Volkmann1
1 Lehrstuhl II fir Mathematik, RWTH Aachen, 52056 Aachen, Germany
Abstract:

A cycle C of a graph G is called a q-dominating cycle if every vertex of G which is not contained in C is adjacent to at least q vertices of C. Let G be a k-connected graph with k2. We present a sufficient condition, in terms of the degree sum of k+1 independent vertices, for G to have a qg-dominating cycle. This is an extension of a 1987 result by J.A. Bondy and G. Fan. Furthermore, examples will show that the given condition is best possible.

Zi-Xia Song1
1Department of Mathematics National University of Singapore 10 Kent Ridge Crescent Singapore, 119260
Abstract:

In an earlier paper [11], we proved that there does not exist any Δ-critical graph of even order with five major vertices. In this paper, we prove that if G is a Δ-critical graph of odd order 2n+1 with five major vertices, then e(G)=nΔ+1. This extends an earlier result of Chetwynd and Hilton, and also completes our characterization of graphs with five major vertices. In [9], we shall apply this result to establish some results on class 2 graphs whose core has maximum degree two.

Ch. Eslahchi1, M. Ghebleh2, H. Hajiabolhassan3
1Department of Mathematics Shahid Beheshti University Evin, Tehran, Iran
2Department of Mathematical Sciences Sharif University of Technology P.O. Box 11365-9415, Tehran, Iran
3Institute for Studies in Theoretical Physics and Mathematics (IPM)
Abstract:

In this paper, uniquely list colorable graphs are studied. A graph G is said to be uniquely k-list colorable if it admits a k-list assignment from which G has a unique list coloring. The minimum k for which G is not uniquely k-list colorable is called the m-number of G. We show that every triangle-free uniquely colorable graph with chromatic number k+1 is uniquely k-list colorable. A bound for the m-number of graphs is given, and using this bound it is shown that every planar graph has m-number at most 4. Also, we introduce list criticality in graphs and characterize all 3-list critical graphs. It is conjectured that every χ-critical graph is χ-critical, and the equivalence of this conjecture to the well-known list coloring conjecture is shown.

Christian Barrientos1
1Departament de Matematica Aplicada i Telematica Universitat Politécnica de Catalunya c/ Jordi Girona 1-3, Médul C3 Campus Nord 08034 Barcelona, Spain
Abstract:

A labeling f of the vertices of a graph G is said k-\emph{equitable} if each weight induced by f on the edges of G appears exactly k times. A graph G is said \emph{equitable} if for every proper divisor k of its size, the graph G has a k-equitable labeling.

A graph G is a corona graph if G is obtained from two graphs, G1 and G2, taking one copy of G1, which is supposed to have order p$,and\(p copies of G2, and then joining by an edge the kth vertex of G1 to every vertex in the kth copy of G2. We denote G by G1G2.

In this paper, we proved that the corona graph CnK1 is equitable. Moreover, we show k-equitable labelings of the corona graph CmnK1, for some values of the parameters k,m, and n.

R. Dios1, D.V. Chopra2
1New Jersey Institute of Technology Newark, New Jersey 07102, U.S.A.
2Wichita State University Wichita, Kansas 67260, U.S.A.
Abstract:

In this paper, we derive a necessary existence condition involving the parameters of a balanced array (B-array) with two symbols and of strength t=8. Consequently, we demonstrate that the existence condition derived here can provide us with useful information on the maximum number of constraints for B-arrays with a given number of columns.

Charles F. Laywine1, David McCarthy 2
1Mathematics Department Brock University St. Catharines, Ontario L2S 3A1 Canada
2Department of Computer Science Brock University St. Catharines, Ontario L2S 3A1 Canada
Abstract:

A set of n+1 orthogonal squares of order n is known to be equivalent to a complete set of n1 mutually orthogonal Latin squares of order n together with canonical row and column squares. In this note, we show that this equivalence does not extend to orthogonal hypercubes of dimensions d>2 by providing examples of affine designs that can be represented by complete sets of type 0 orthogonal hypercubes but not by complete sets of orthogonal Latin hypercubes together with canonical hypercubes that generalize the row and column squares in the case where d=2. These examples also clarify the relationship between affine designs and orthogonal hypercubes that generalize the classical equivalence between affine planes and complete sets of MOLS.

We conclude with the statement of a number of conjectures regarding some open questions.

A. Gutiérrez1, A. S. Lladdt1
1 Dept Matematica Aplicada i Telematica Universitat Politecnica de Catalunya Jordi Girona, 1 E-08034 Barcelona, Spain
Abstract:

We prove that if S is a quasiminimal generating set of a group Γ and F is an oriented forest with |S|>2 arcs, then the Cayley graph Cay(Γ,S) can be decomposed into |Γ| arc-disjoint subdigraphs, each of which is isomorphic to F.

R.G. Stanton 1
1Department of Computer Science University of Manitoba Winnipeg, Canada R3T 2N2
Abstract:

The quantity g2(k)(v) is the minimum number of blocks in a family of blocks from a v-set that covers all (v2) pairs exactly twice, given the restriction that the longest block in the covering family has length k (there may be many blocks of length k). We give certain results for the case k=4.

Robert W. Cutler, III1, Mark D. Halsey2
1 Departments of Biology & Computer Science Bard College, Annandale, NY 12504 USA
2Department of Mathematics Bard College, Annandale, NY 12504 USA
Abstract:

A set of edges D in a graph G is a dominating set of edges if every edge not in D is adjacent to at least one edge in D. The minimum cardinality of an edge dominating set of G is the edge domination number of G, denoted DE(G). A graph G is edge domination critical, or EDC, if for any vertex v in G we have DE(Gv)=DE(G)1. Every graph G must have an induced subgraph F such that F is EDC and DE(G)=DE(F). In this paper, we prove that no tree with more than 2 vertices is EDC, develop a forbidden subgraph characterization for the edge domination number of a tree, and we develop a construction that conserves the EDC property.

Ahmed M. Assaf1, L.P.S. Singh2
1Department of Mathematics
2Department of Computer Science Central Michigan University Mt. Pleasant, MI 48859
Abstract:

Let V be a finite set of order v. A (v,k,λ) covering design of index λ and block size k is a collection of k-element subsets, called blocks, such that every 2-subset of V occurs in at least λ blocks. The covering problem is to determine the minimum number of blocks, α(v,k,λ)$,inacoveringdesign.Itiswellknownthat\(α(v,k,λ)vkv1k1.λ=ϕ(v,k,λ), where x is the smallest integer satisfying xx. In this paper, we determine the value α(v,5,λ), with few possible exceptions, for λ=3, v2(mod4) and λ=9,10,v5, and λ11, v2(mod4).

Ping Wang1, Stephanie A. Moellert1
1Department of Mathematics, Statistics, and Computer Science St. Francis Xavier University Antigonish, Nova Scotia, Canada
Abstract:

Let G=(V,E) be a connected undirected graph. Suppose a fire breaks out at a vertex of G and spreads to all its unprotected neighbours in each time interval. Also, one vertex can be protected in each time interval. We are interested in the number of vertices that can be “saved”, that is, which will never be burned. An algorithm is presented to find the optimal solution in the 2-dimensional grid graphs and 3-dimensional cubic graphs. We also determined the upper and lower bounds of the maximum number of vertices that can be saved on the large product graphs. The problem of containing the fire with one firefighter or more is also considered.

Elizabeth J. Billington1, Gaetano Quattrocchit2
1Centre for Discrete Mathematics and Computing Department of Mathematics The University of Queensland Queensland 4072, Australia
2Department of Mathematics University of Catania viale A. Doria 6 95125 Catania, Italy
Abstract:

Let C be the underlying graph of a configuration of l blocks in a path design of order v and block size 3, (V,B). We say that (V,B) is (l,C)-ordered if it is possible to order its blocks in such a way that each set of l consecutive blocks has the same underlying graph C. In this paper, we completely solve the problem of the existence of a (2,C)-ordered path design P(v,3,1) for any configuration having two blocks.

R. Dios1
1New Jersey Institute of Technology Newark, New Jersey 07102, U.S.A.
Abstract:

Summary. In this paper, we present some inequalities on balanced arrays ({B-arrays}) of strength five with two symbols.

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;