A.G. Sittampalam1, A.D. Keedwell1
1Department of Mathematical and Computing Sciences University of Surrey, U.K.
Abstract:

In this paper, we obtain critical sets for the general dihedral group, but we are not able to decide whether they are minimal. We also show the existence of a weakly completable critical set in the latin square based on the dihedral group of order six. We believe this to be the smallest group-based square to have such a set.

Bernt Lindstrom1
1Department of Mathematics Royal Institute of Technology 8-100 44 Stockholm Sweden
Abstract:

An Sh-set (mod m) is a set S of integers such that the sumsa1+a2++ah of elements \(a_1 \leq a_2 \leq \cdots 1\) and prove that equality is possible at least when h=p is a prime (Theorem).

Anthony Bonato1
1Department of Mathematics Wilfrid Laurier University Waterloo, ON N2L 3C5. Canada.
Abstract:

We investigate those classes K of relational structures closed under operations that are defined by excluding a fixed class of finite structures. We characterize such classes and show they contain an infinite family of pairwise non-embeddable members. NEC structures are defined by certain extension conditions. We construct countable universal structures in K satisfying only finitely many of the NEC extension conditions.

M. Muzychuk1
1Department of Mathematics and Computer Science Netanya Academic College 16 Kibutz Galuyot St. 42365 Netanya, Israel
Abstract:

The notion of normal quotient of a vertex-transitive graph was introduced in [5]. It was shown there that many graph properties are inherited by normal quotients. The definition of a normal quotient was given in [5] in group-theoretical terms. In this note we give a combinatorial approximation to this notion which extends the original definition. We show that many of the properties that were inherited by group-theoretical normal quotients are also inherited by combinatorial ones.

Tao Jiang1
1Department of Mathematics University of Ilinois Urbana, IL 61801, USA
Abstract:

A (k;g)-cage is a smallest k-regular graph with girth g. Harary and Kovacs [2] conjectured that for all k3 and odd g5, there exists a (k;g)-cage which contains a cycle of length g+1. Among other results, we prove the conjecture for all k3 and g{5,7}.

Masakazu Nihei1
1Fyujishiro High School Fujishiro, Ibaraki, 300-1537, Japan
Abstract:

The toughness t(G) of a noncomplete graph G is defined as

t(G)=min{|S|ω(GS)SV(G),ω(GS)2}

where ω(GS) is the number of components of GS. We also define t(Kn)=+ for every n.

In this article, we discuss the toughness of the endline graph of a graph and the middle graph of a graph.

David A. Pike1, Nabil Shalaby1
1Department of Mathematics and Statistics Memorial University of Newfoundland St. John’s, Newfoundland, Canada, AiC 587
Abstract:

We present several new non-isomorphic one-factorizations of K36 and K40 which were found through hill-climbing and testing Skolem sequences. We also give a brief comparison of the effectiveness of hill-climbing versus exhaustive search for perfect one-factorizations of K2n for small values of 2n.

Omer Berkman1, Michal Parnas1, Yehuda Roditty1
1The Academic College of Tel-Aviv-Yaffo Tel-Aviv, Israel.
Abstract:

We prove that all cycles are edge-magic, thus solving a problem presented by [2]. In [3] it was shown that all cycles of odd length are edge-magic. We give explicit constructions that show that all cycles of even length are edge-magic. Our constructions differ for the case of cycles of length n0(mod4) and n2(mod4).

J. A. Dias da Silva1, Rosario Fernandes2
1Centro de Algebra da Universidade de Lisboa Av Gama. Pinto 2 1699 Lisboa Codex Portugal
2Departamento de Matematica Centro de Algebra da Universidade de Lisboa Av Gama Pinto 2 1699 Lisboa Codex Portugal
Abstract:

We present results that characterize the covering number and the rank partition of the dual of a matroid M using properties of M. We prove, in particular, that the elements of covering number 2 in M are the elements of the closure of the maximal 2-transversals of M.

From the results presented it can be seen that every matroid M is a weak map image of a transversal matroid with the same rank partition.

Teresa W. Haynes1, Michael A. Henning2, Lucas C. van der Merwe3
1Department of Mathematics East Tennessee State University Johnson City, TN 37614-0002 USA
2Department of Mathematics University of Natal Private Bag X01 Pietermaritzburg 3209 South Africa
3University of South Africa Pretoria, South Africa
Abstract:

Let G be a spanning subgraph of Ks,s, and let H be the complement of G relative to Ks,s,; that is, Ks,s=G oplusH is a factorization of Ks,s. For a graphical parameter μ(G), a graph G is μ(G)-critical if μ(G+e)<μ(G) for every e in the ordinary complement G¯ of G, while G is μ(G)-critical relative to Ks,s if μ(G+e)<μ(G) for all eE(H). We show that no tree T is μ(T)-critical and characterize the trees T that are μ(T)-critical relative to Ks,s, where μ(T) is the domination number and the total domination number of T.

Eddie Cheng1, Marc J. Lipman1, Hyungju Park1
1DEPARTMENT OF MATHEMATICS AND STATISTICS, OAKLAND UNIVERSITY, ROCHESTER, MICHIGAN 48309 USA
Abstract:

The star graph Sn and the alternating group graph An are two popular interconnection graph topologies. An has a higher connectivity while Sn has a lower degree, and the choice between the two graphs depends on the specific requirement of an application. The degree of Sn can be even or odd, but the degree of An is always even. We present a new interconnection graph topology, split-star graph Sn2, whose degree is always odd. Sn2 contains two copies of An and can be viewed as a companion graph for An. We demonstrate that this graph satisfies all the basic properties required for a good interconnection graph topology. In this paper, we also evaluate Sn, An, and Sn2 with respect to the notion of super connectivity and super edge-connectivity.

Charles F. Laywine1, Gary L. Mullen2
1Department of Mathematics, Brock University, St. Catharines, Ontario, L2S 3A1, Canada
2Department of Mathematics, The Pennsylvania State University, University Park, PA 16802, USA
Abstract:

We construct a small table of lower bounds for the maximum number of mutually orthogonal frequency squares of types F(n;λ) with n100.

Makiko Watanabe1
1Graduate school of mathematics, Kyushu University, Hakozaki 6-10-1, Higashi-ku, Hukuoka.
Allen G. Fuller1
1DIVISION OF NATURAL SCIENCES AND NURSING, GORDON COLLEGE, BARNESVILLE, GA 30204
Abstract:

A graph G is {R,S}-free if G contains no induced subgraphs isomorphic to R or S. The graph Z1 is a triangle with a path of length 1 off one vertex; the graph Z2 is a triangle with a path of length 2 off one vertex. A graph that is {K1,3,Z1}-free is known to be either a cycle or a complete graph minus a matching. In this paper, we investigate the structure of {K1,3,Z2}-free graphs. In particular, we characterize {K1,3,Z2}-free graphs of connectivity 1 and connectivity 2.

Shannon L. Fitzpatrick1, Richard J. Nowakowski2
1Acadia University Wolfville, Nova Scotia
2Dathouste University Halifax, Nova Scotia
Abstract:

The problem is to determine the number of `cops’ needed to capture a `robber’ where the game is played with perfect information with the cops and the robber alternating moves. The `cops’ capture the `robber’ if one of them occupies the same vertex as the robber at any time in the game. Here we show that a graph with strong isometric dimension two requires no more than two cops.

Sandi Klavzar1, Uros Milutinovic2, Ciril Petr3
1Department of Mathematics, PEF, Unversity of Maribor Korodka cesta 160, 2000 Maribor, Slovenia
2Department of Mathematics, PEF, University of Maribor Korogka cesta 160, 2000 Maribor, Slovenia
3Institute of Information Sciences PreSernova 17, 2000 Maribor, Slovenia
Abstract:

Combinatorial properties of the multi-peg Tower of Hanoi problem on n discs and p pegs are studied. Top-maps are introduced as maps which reflect topmost discs of regular states. We study these maps from several points of view. We also count the number of edges
in graphs of the multi-peg Tower of Hanoi problem and in this way obtain some combinatorial identities.

Zhang Cheng-heng1
1Hebei Langfang Teachers’ College Hebei Langfang 065000, China
Guantao Chen1, Joan Hutchinson2, Wiktor Piotrowski3, Warren Shreve4, Bing Wei5
1Department of Mathematics and Computer Science Georgia State University Atlanta GA 30303 USA
2Department of Mathematics and Computer Science Macalester College St. Paul MN 55105 USA
3Department of Mathematics and Computer Science University of Wisconsin-Superior Superior WI 54880 USA
4Department of Mathematics North Dakota State University Fargo, ND 58105-5075 USA
5Institute of Systems Science Academia Sinica Beijing 100080, China
Abstract:

A given nonincreasing sequence D=(d1,d2,,dn) is said to contain a (nonincreasing) repetition sequence D=(di1,di2,dik) for some kn2 if all values of DD are distinct and for any diiD, there exists some dtDD such that di1=dt. For any pair of integers n and k with nk+2, we investigate the existence of a graphic sequence which contains a given repetition sequence. Our main theorem contains the known results for the special case di1=dik if k=1 or k=2 (see [1, 5, 2]).

Spencer P. Hurd1, Dinesh G. Sarvate2
1Department of Mathematics and Computer Science The Citadel, Charleston, SC, 29409
2Department of Mathematics, University of Charleston, Charleston, SC, 29424
Abstract:

It is shown that the necessary conditions are sufficient for the existence of c-BRD(v,3,λ) for all c1. This was previously known for c=0 and for c=1.

Marilyn Breen1
1Department of Mathematics University of Oklahoma Norman, OK 73019-0315 U.S.A,
Abstract:

Let S be the set of vectors {eiθ:θ=0,n3,2n3}, and let S be a nonempty simply connected union of finitely many convex polygons whose edges are parallel to vectors in S. If every three points of S see a common point via paths which are permissible (relative to S), then S is star-shaped via permissible paths. The number three is best possible.

M. Ghebleh1, E.S. Mahmoodian2
1Institute for studies in theoretical Physics and Mathematics (IPM)
2Department of Mathematical Sciences Sharif University of Technology P.O. Box 11365-9415 Tehran, I.R. Iran
Abstract:

Let G be a graph with n vertices and suppose that for each vertex v in G, there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Recently, M. Mahdian and E.S. Mahmoodian characterized uniquely 2-list colorable graphs. Here, we state some results which will pave the way in characterization of uniquely k-list colorable graphs. There is a relationship between this concept and defining sets in graph colorings and critical sets in latin squares.

Rumen N.Daskalov1
1Department of Mathematics Technical University 5300 Gabrovo, Bulgaria
Abstract:

Let d3(n,k) be the maximum possible minimum Hamming distance of a ternary linear [n,k,d;3] code for given values of n and k. The nonexistence of [142,7,92;3], [162,7,106;3], [165,7,108;3], and [191,7,125;3] codes is proved.

Steve Bowser1, Charles Cable1
1DEPARTMENT OF MATHEMATICS,ALLEGHENY COLLEGE, MEADVILLE, PENNSYLVANIA 16335
Abstract:

The niche graph of a digraph D is the undirected graph defined on the same vertex set in which two vertices are adjacent if they share either a common in-neighbor or a common out-neighbor in D. We define a hierarchy of graphs depending on the condition of being the niche graph of a digraph having, respectively, no cycles, no cycles of length two, no loops, or loops. Our goal is to classify in this hierarchy all graphs of order n3 having a subgraph isomorphic to Kn2.

E.J. Cockayne1, O. Favaron2, P.J. P.Grobler3, C.M. Mynhardt3, J. Puech2
1Department of Mathematics, University of Victoria, Victoria, BC, Canada
2LRI, Université de Paris Sud, Orsay, France
3Department of Mathematics, University of South Africa, Pretoria, South Africa
Abstract:

Let H1,,Ht be classes of graphs. The class Ramsey number R(H1,,Ht) is the smallest integer n such that for each t-edge colouring (G1,,Gt) of Kn, there is at least one i{1,,t} such that Gi contains a subgraph HiHi. We take t=2 and determine R(Gl1,Gm1) for all 2lm and R(Gi2,Gm2) for all 3lm, where Gji consists of all edge-minimal graphs of order j and minimum degree i.

William Kocay1, Daniel Neilson1, Ryan Szypowski1
1Computer Science Department University of Manitoba Winnipeg, Manitoba, CANADA, R3T 2N2
Abstract:

Let G be a 2-connected graph with a toroidal rotation system given. An algorithm for constructing a straight line drawing with no crossings on a rectangular representation of the torus is presented. It is based on Read’s algorithm for constructing a planar layout of a 2-connected graph with a planar rotation system. It is proved that the method always works. The complexity of the algorithm is linear in the number of vertices of G.

Yasuhiro Fukuchi1
1Department of Applied Mathematics Science University of Tokyo Shinjuku-ku, Tokyo 162-8601, JAPAN
Abstract:

A graph G is called super-edge-magic if there exists a bijection f from V(G)E(G) to {1,2,,|V(G)|+|E(G)|} such that f(u)+f(v)+f(uv)=C is a constant for any uvE(G) and f(V(G))={1,2,,|V(G)|}. In this paper, we show that the generalized Petersen graph P(n,k) is super-edge-magic if n3 is odd and k=2.

Klaus Dohmen1
1Institut fiir Informatik Humboldt-Universitat zu Berlin Unter den Linden 6 D-10099 Berlin, Germany
Abstract:

We reprove an important case of a recent topological result on improved Bonferroni inequalities due to Naiman and Wynn in a purely combinatorial manner. Our statement and proof involves the combinatorial concept of non-evasiveness instead of the topological concept of contractibility. In contradistinction to the proof of Naiman and Wynn, our proof does not require knowledge of simplicial homology theory.

M. H. Armanious1
1Mathematics Department, Faculty of Science, Mansoura University Mansoura, Egypt
Abstract:

Quackenbush [5] has studied the properties of squags or “Steiner quasigroups”, that is, the corresponding algebra of Steiner triple systems. He has proved that if a finite squag (P;) contains two disjoint subsquags (P1;) and (P2;) with cardinality |P1|=|P2|=13|P|, then the complement P3=P(P1P2) is also a subsquag and the three subsquags P1,P2 and P3 are normal. Quackenbush then asks for an example of a finite squag of cardinality 3n with a subsquag of cardinality n, but not normal. In this paper, we construct an example of a squag of cardinality 3n with a subsquag of cardinality n, but it is not normal; for any positive integer n7 and n1 or 3 (mod 6).

Hideo Komuro1, Kiyoshi Ando1
1University of Electro-Communications 1-5-1, Cofu, Tokyo, JAPAN
Abstract:

A plane graph is an embedding of a planar graph into the sphere which may have multiple edges and loops. A face of a plane graph is said to be a pseudo triangle if either the boundary of it has three distinct edges or the boundary of it consists of a loop and a pendant edge. A plane pseudo triangulation is a connected plane graph of which each face is a pseudo triangle. If a plane pseudo triangulation has neither a multiple edge nor a loop, then it is a plane triangulation. As a generalization of the diagonal flip of a plane triangulation, the diagonal flip of a plane pseudo triangulation is naturally defined. In this paper we show that any two plane pseudo triangulations of order n can be transformed into each other, up to ambient isotopy, by at most 14n64 diagonal flips if n7. We also show that for a positive integer n5, there are two plane pseudo triangulations with n vertices such that at least 4n15 diagonal flips are needed to transform into each other.

Zhang Cheng-heng1
1Hebei Langfang Teachers’ College Hebei Langfang 065000, China
Kuo-Bing Huang1, Wen-Chung Huang1, Chia-Chin Hung1, Guei-Hua Wang1
1Department of Mathematics Soochow University Taipei, Taiwan, Republic of China.
Abstract:

An extended Mendelsohn triple system of order v with a idempotent element (EMTS(v,a)) is a collection of cyclically ordered triples of the type {x,y,z}, {x,x,y} or {x,x,x} chosen from a v-set, such that every ordered pair (not necessarily distinct) belongs to only one triple and there are a triples of the type {x,x,x}. If such a design with parameters v and a exist, then they will have bv,a blocks, where bv,a=(v2+2a)/3. A necessary and sufficient condition for the existence of EMTS(v,0) and EMTS(v,1) are v0 (mod 3) and v0 (mod 3), respectively. In this paper, we have constructed two EMTS(v,0)’s such that the number of common triples is in the set {0,1,2,,bv,03,bv,0}, for v0 (mod 3). Secondly, we have constructed two EMTS(v,1)’s such that the number of common triples is in the set {0,1,2,,bv,12,bv,1}, for v0 (mod 3).

E-mail Alert

Add your e-mail address to receive upcoming issues of Ars Combinatoria.

Call for papers

Special issue: Proceedings of International Conference on Discrete Mathematics (ICDM 2025)

Guest editors: Peter J Cameron, Ambat Vijayakumar, Aparna Lakshmanan S

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.