Anthony B. Evans1
1Department Of Mathematics and Statistics, Wright State University, Day- Ton, Ohio 45435
Abstract:

For a finite group G, a bijection θ:GG is a strongcompletemapping if the mappings ggθ(g) and gg1θ(g) are both bijections. A group is stronglyadmissible if it admits strong complete mappings. Strong complete mappings have several combinatorial applications. There exists a Latin square orthogonal to both the multiplication table of a finite group G and its normal multiplication table if and only if G is strongly admissible. The problem of characterizing strongly admissible groups is far from settled. In this paper, we will update progress towards its resolution. In particular, we will present several infinite classes of strongly admissible dihedral and quaternion groups and determine all strongly admissible groups of order at most 31.

R.C. Bunge1, S. 1. El-Zainat2, H. J. Fry3, K.S. Krauss4, D.P. Roberts5, C. A. Sullivan6, A. A. Unsicker, N. BE. Witt
1Illinois State University, Normal, IL 61790
2 Alma College, Alma, MI 48801
3Tllinois Wesleyan University, Bloomington, IL 61701
4Bowling Green State University, Bowling Green, OH 43403
5Brigham Young University, Provo, UT 84602
6Simeon Career Academy, Chicago, IL, 60620
Abstract:

The complete directed graph of order n, denoted Kn, is the directed graph on n vertices that contains the arcs (u,v) and (v,u) for every pair of distinct vertices u and v. For a given directed graph D, the set of all n for which Kn admits a D-decomposition is called the spectrum of D. In this paper, we find the spectrum for each bipartite subgraph of K4 with 5 or fewer arcs.

Abdollah Khodkar1, Alex L. Peterson2, Christina J. Wahl3, Zach W. Walsh4
1Department of Mathematics University of West Georgia Carrollton, GA 30118
2Berry College Mount Berry, GA 30149
3The State University of New York at Potsdam Potsdam, NY 13676
4Carleton College Northfield, MN 55057
Abstract:

A bipartite graph on n vertices, with n even, is called uniquely bi-pancyclic (UBPC) if it contains precisely one cycle of length 2m for every 2mn2. In this note, using computer programs, we show that if 32n56, and n44, then there are no UBPC graphs of order n. We also present the six non-isomorphic UBPC graphs of order 44. This improves the recent results on UBPC graphs of order at most 30.

Babak Samadi1, Abdollah Khodkar2, Hamid R. Golmochammadi3
1Department of Mathematics Arak University, Arak IRI
2Department of Mathematics University of West Georgia Carrollton, GA 30118, USA
3Department of Mathematics University of Tafresh, Tafresh, IRI
Abstract:

We first introduce the concept of (k,k,k)-domination numbers in graphs, which is a generalization of many domination parameters. Then we find lower and upper bounds for this parameter, which improve many well-known results in the literature.

Dan S. Archdeacon1, Jeffrey H. Dinitz1, Amelia Mattern2, Douglas R. Stinson2
1Department of Mathematics and Statistics, University of Vermont, Burlington, VT 05405 U.S.A.
2David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada
Abstract:

We are interested in ordering the elements of a subset A of the non-zero integers modulo n in such a way that all the partial sums are distinct. We conjecture that this can always be done, and we prove various partial results about this problem.

Xuechao Li1, Shuchao Li2, Wei Bing3
1The University of Georgia, GA, USA 30602
2The Central China Normal University, P.R.China
3The University of Mississippi, MS, USA
Abstract:

A graph G with maximum degree Δ and edge chromatic number χ(G)>Δ is \emph{edge-Δ-critical} if χ(Ge)=Δ for each eE(G). In this article, we provide a new proof of adjacency Lemmas on edge-critical graphs such that Vizing’s adjacency lemma becomes a corollary of our results.

Margaret A. Readdy1
1Department of Mathematics, University of Kentucky Lexington KY 40506 USA
Abstract:

This paper surveys recent results for flag enumeration of polytopes, Bruhat graphs, balanced digraphs, Whitney stratified spaces and quasi-graded posets.

W. D. Wallis1
1Department of Mathematics, Southern Illinois University, Carbondale, IL 62901, USA
Abstract:

A bipancyclic graph on v vertices is a bipartite graph that contains, as subgraphs, cycles of length n for every even integer n such that 4nv. Such a graph is uniquely bipancyclic if it contains exactly one subgraph of each permissible length.

In this paper, we find all uniquely bipancyclic graphs on 30 or fewer vertices.

Daniel Johnston1, Ping Zhang1
1Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
Abstract:

A balanced complete bipartite graph is a complete bipartite graph where the degrees of its vertices differ by at most 1. In a red-blue-green coloring of the edges of a graph G, every edge of G is colored red, blue, or green. For three graphs F1, F2, and F3, the 2-Ramsey number R2(F1,F2,F3) of F1, F2, and F3, if it exists, is the smallest order of a balanced complete bipartite graph G such that every red-blue-green coloring of the edges of G contains a red F1, a blue F2, or a green F3. In this note, we determine that

20R2(C4,C4,C4)21.

FUTABA FUJIE1, ZHENMING BI, PING ZHANG2
1Graduate School of Mathematics, Nagoya University, Nagoya, 464-8602, Japan.
2Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA
Abstract:

A Hamiltonian graph G is said to be -path-Hamiltonian, where is a positive integer less than or equal to the order of G, if every path of order in G is a subpath of some Hamiltonian cycle in G. The Hamiltonian cycle extension number of G is the maximum positive integer for which every path of order or less is a subpath of some Hamiltonian cycle in G. If the order of G equals n, then it is known that hce(G)=n if and only if G is a cycle or a regular complete bipartite graph (when n is even) or a complete graph. We present a complete characterization of Hamiltonian graphs of order n that are -path-Hamiltonian for each {n3,n2,n1,n}.

Eric Andrews1, Elliot Laforge2, Chira Lumduanhom3, Ping Zhang2
1Department of Mathematics and Statistics University of Alaska Anchorage Anchorage, AK 99508, USA
2Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA
3Department of Mathematics Srinakharinwirot University, Sukhumvit Soi 23, Bangkok, 10110, Thailand
Abstract:

Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. An edge coloring is a proper-path coloring of G if every pair u,v of distinct vertices of G is connected by a proper uv path in G. The minimum number of colors required for a proper-path coloring of G is the proper connection number pc(G) of G. We study proper-path colorings in those graphs obtained by some well-known graph operations, namely line graphs, powers of graphs, coronas of graphs, and vertex or edge deletions. Proper connection numbers are determined for all iterated line graphs and powers of a given connected graph. For a connected graph G, sharp lower and upper bounds are established for the proper connection number of (i) the k-iterated corona of G in terms of pc(G) and k, and (ii) the vertex or edge deletion graphs Gv and Ge, where v is a non-cut-vertex of G and e is a non-bridge of G, in terms of pc(G) and the degree of v. Other results and open questions are also presented.

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

A red-blue coloring of a graph G is an edge coloring of G in which every edge of G is colored red or blue. Let F be a connected graph of size 2 or more with a red-blue coloring, at least one edge of each color, where some blue edge of F is designated as the root of F. Such an edge-colored graph F is called a color frame. An F-coloring of a graph G is a red-blue coloring of G in which every blue edge of G is the root edge of a copy of F in G. The F-chromatic index χF(G) of G is the minimum number of red edges in an F-coloring of G. A minimal F-coloring of G is an F-coloring with the property that if any red edge of G is re-colored blue, then the resulting red-blue coloring of G is not an F-coloring of G. The maximum number of red edges in a minimal F-coloring of G is the upper F-chromatic index χF(G) of G. For integers k and m with 1k<m and m3, let Sk,m be the color frame of the star K1,m of size m such that Sk,m has exactly k red edges and mk blue edges. For a positive integer k, a set X of edges of a graph G is a Δk-set if Δ(G[X])=k, where G[X] is the subgraph of G induced by X. The maximum size of a Δk-set in G is referred to as the k-matching number of G and is denoted by ak(G). A Δk-set X is maximal if X{e} is not a Δk-set for every eE(G)X. The minimum size of a maximal Δk-set of G is the lower k-matching number of G and is denoted by ak(G). In this paper, we consider Sk,m-colorings of a graph and study relations between Sk,m-colorings and Δk-sets in graphs. Bounds are established for the Sk,m-chromatic indexes χSk,m(G) and χSk,m(G) of a graph G in terms of the k-matching numbers ak(G) and ak(G) of the graph. Other results and questions are also presented.

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

Let G be a Hamiltonian graph of order n3. For an integer with 1n, the graph G is -path-Hamiltonian if every path of order lies on a Hamiltonian cycle in G. The Hamiltonian cycle extension number of G is the maximum positive integer for which every path of order or less lies on a Hamiltonian cycle of G. For an integer with 2n1, the graph G is -path-pancyclic if every path of order in G lies on a cycle of every length from +1 to n. (Thus, a 2-path-pancyclic graph is edge-pancyclic.) A graph G of order n3 is path-pancyclic if G is -path-pancyclic for each integer with 2n1. In this paper, we present a brief survey of known results on these two parameters and investigate the -path-Hamiltonian graphs and -path-pancyclic graphs having small minimum degree and small values of . Furthermore, highly path-pancyclic graphs are characterized and several well-known classes of 2-path-pancyclic graphs are determined. The relationship among these two parameters and other well-known Hamiltonian parameters is investigated along with some open questions in this area of research.

Yong-Song Ho 1, Sin-Min Lee2, Bill Lo3
1Nan Chiau High School Singapore
2 34803 Hollyhock Street Union City, CA 94587,USA
32217 Rivers Bend Circle Livermore, CA 94550
Abstract:

Let G be a graph with vertex set V(G) and edge set E(G). A (p,q)-graph G=(V,E) is said to be AL(k)-traversal if there exists a sequence of vertices (v1,v2,,vp) such that for each i=1,2,,p1, the distance between vi and vi+1 is equal to k. We call a graph G a 2-steps Hamiltonian graph if it has an AL(2)-traversal in G and d(vp,v1)=2. In this paper, we characterize some cubic graphs that are 2-steps Hamiltonian. We show that no forbidden subgraph characterization for non-2-steps-Hamiltonian cubic graphs is available by demonstrating that every cubic graph is a homeomorphic subgraph of a non-2-steps Hamiltonian cubic graph.

Ebrahim Salehi1, Daniel Corral1
1Department of Mathematical Sciences University of Nevada, Las Vegas Las Vegas, NV 89154-4020
Abstract:

For a graph G=(V,E) and a coloring f:V(G)Z2, let vf(i)=|f1(i)|. f is said to be friendly if |vf(1)vf(0)|1. The coloring f:V(G)Z2 induces an edge labeling f+:E(G)Z2 defined by f+(xy)=|f(x)f(y)|, for all xyE(G). Let ef(i)=|f+1(i)|. The friendly index set of the graph G, denoted by FI(G), is defined by
FI(G)={|ef(1)ef(0)|:f is a friendly vertex labeling of G}.

In this paper, we determine the friendly index set of certain classes of trees and introduce a few classes of fully cordial trees.

Gee-Choon Lau1, Wai-Chee Shiu2, Ho-Kuen Ng3, Carmen D. Ng4, P. Jeyanthi5
1Faculty of Computer & Mathematical Sciences, Universiti Teknologi MARA (Segamat Campus), 85000, Johore, Malaysia.
2Department of Mathematics, Hong Kong Baptist University, 224 Waterloo Road, Kowloon Tong, Hong Kong, P.R. China.
3Department of Mathematics, San Jose State University, San Jose, CA 95192 U.S.A.
4Graduate Group in Demography University of Pennsylvania Philadelphia, PA 19104 U.S.A.
5Research Centre, Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur – 628 215, India.
Abstract:

Let G=(V(G),E(G)) be a simple, finite, and undirected graph with n vertices. Given a bijection f:V(G){1,,n}, one can associate two integers S=f(u)+f(v) and D=|f(u)f(v)| with every edge uvE(G). The labeling f induces an edge labeling f:E(G){0,1} such that for any edge uv in E(G), f(uv)=1 if gcd(S,D)=1, and f(uv)=0 otherwise. Such a labeling is called an SD-prime labeling if f(uv)=1 for all uvE(G). We say that G is SD-prime if it admits an SD-prime labeling. A graph G is said to be a stronglySDprimegraph if for every vertex v of G there exists an SD-prime labeling f satisfying f(v)=1. In this paper, we first give some sufficient conditions for a theta graph to be strongly SD-prime. We then provide constructions of new SD-prime graphs from known SD-prime graphs and investigate the SD-primality of some general graphs.

Dinesh G. Sarvate1, Paul A. Winter2, Li Zhang3
1COLLEGE OF CHARLESTON, DEPT. OF MATH., CHARLESTON, SC, 29424
2HowArD CoLLece, UKZN, Dept. or Matu., DURBAN, KZN 4041, SOUTH AFRICA
3THE CrrapEL, DEPT. OF MATH. AND COMPUTER SCIENCE, CHARLESTON, SC, 29409
Abstract:

Recently, the authors proposed a fundamental theorem for the decomposing of a complete bipartite graph. They applied the theorem to obtain complete results on the decomposition of a complete bipartite graph into connected subgraphs on four vertices and up to four edges. In this paper, we decompose a complete multi-bipartite graph into its subgraphs of four vertices and five edges. We show that necessary conditions are sufficient for the decompositions, with some exceptions where decompositions do not exist

Derek W. Hein 1, Dinesh G. Sarvate2
1Southern UTAH University, DEPT. Of Math., CEDAR City, UT, 84720
2COLLEGE OF CHARLESTON, DEPT. OF MATH., CHARLESTON, SC, 29424
Abstract:

The authors previously defined the Stanton-type graph S(n,m) and demonstrated how to decompose λKn (for the appropriate minimal values of λ) into Stanton-type graphs S(4,3) of the LOE-, OLE-, LEO-, and ELO-types. Sarvate and Zhang showed that for all possible values of λ, the necessary conditions are sufficient for LOE- and OLE-decompositions. In this paper, we show that for all possible values of λ, the necessary conditions are sufficient for LEO- and ELO-decompositions.

Sin-Min Lee 1, Hsin-Hao Su1
134803 Hollyhock Street Department of Mathematics Union City, CA 94587,USA Stonehill! College Easton, MA 02357, USA
Abstract:

Let G be a graph with vertex set V(G) and edge set E(G). A (p,q)-graph G=(V,E) is said to be AL(k)-traversal if there exists a sequence of vertices {v1,v2,,vp} such that for each i=1,2,,p1, the distance between vi and vi+1 is equal to k. We call a graph G a k-steps Hamiltonian graph if it has an AL(k)-traversal in G and the distance between vp and v1 is k. In this paper, we completely classify whether a subdivision graph of a cycle with a chord is 2-steps Hamiltonian.

Martin Griittmiiller1, Nabil Shalaby Daniela Silvesan2
1HTWK Leipzig – University of Applied Science Germany
2Department of Mathematics and Statistics Memorial University of Newfoundland St. John’s, Newfoundland CANADA A1C 587
Abstract:

A triple system is decomposable if the blocks can be partitioned into two sets, each of which is itself a triple system. It is cyclically decomposable if the resulting triple systems are themselves cyclic. In this paper, we prove that a cyclic two-fold triple system is cyclically indecomposable if and only if it is indecomposable. Moreover, we construct cyclic three-fold triple systems of order $v$ which are cyclically indecomposable but decomposable for all v3mod6. The only known example of a cyclic three-fold triple system of order v1mod6 that is cyclically indecomposable but decomposable was a triple system on 19 points. We present a construction which yields infinitely many such triple systems of order v1mod6. We also give several examples of cyclically indecomposable but decomposable cyclic four-fold triple systems and few constructions that yield infinitely many such triple systems.

Danny Dyer1, Sadegheh Haghshenas1, Nabil Shalaby1
1Department of Mathematics and Statistics, Memorial University of Newfoundland, St. John’s, Newfoundland, Canada, A1C 5S7
Abstract:

The spectrum problem for decomposition of trees with up to eight edges was introduced and solved in 1978 by Huang and Rosa. Additionally, the packing problem was settled for all trees with up to six edges by Roditty. For the first time, we consider obtaining all possible leaves in a maximum tree-packing of Kn, which we refer to as the spectrum problem for packings of complete graphs. In particular, we completely solve this problem for trees with at most five edges. The packing designs are used in developing optimal error-correcting codes, which have applications in biology, such as in DNA sequencing.

Sin-Min Lee1, Hsin-Hao Su1, Heiko Todt2
1Hollyhock Street Dept. of Math. Union City, CA 94587, USA Stonehill College Easton, MA 02357, USA
2Dept. of Math. Stonehill College Easton, MA 02357, USA
Abstract:

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f of a graph G is said to be edge-friendly if |ef(0)ef(1)|1, where ef(i)=card{eE(G):f(e)=i}. An edge-friendly labeling f:E(G)Z2 induces a partial vertex labeling f+:V(G)A defined by f+(x)=0 if the edges incident to x are labeled 0 more than 1. Similarly, f+(x)=1 if the edges incident to x are labeled 1 more than 0. f+(x) is not defined if the edges incident to x are labeled 1 and 0 equally. The edge-balance index set of the graph G, EBI(G), is defined as {|vf(0)vf(1)|:the edge labeling f is edge-friendly}, where vf(i)=card{vV(G):f+(v)=i}.

An n-wheel is a graph consisting of n cycles, with each vertex of the cycles connected to one central hub vertex. The edge-balance index sets of n-wheels are presented.

Suhadi Wido Saputro1
1Combinatorial Mathematics Research Division Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung Jl.Ganesha 10 Bandung 40132 Indonesi
Abstract:

A set of vertices W locallyresolves a graph G if every pair of adjacent vertices is uniquely determined by its coordinate of distances to the vertices in W. The minimum cardinality of a local resolving set of G is called the localmetricdimension of G. A graph G is called a k-regular graph if every vertex of G is adjacent to k other vertices of G. In this paper, we determine the local metric dimension of an (n3)-regular graph G of order n, where n5.

Sean Bailey 1, LeRoy B. Beasley1
1Department of Mathematics and Statistics, Utah State University Logan, Utah 84322-3900, USA
Abstract:

Let Gn be the set of all simple loopless undirected graphs on n vertices. Let T be a linear mapping, T:GnGn, such that the dot product dimension of T(G) is the same as the dot product dimension of G for any GGn. We show that T is necessarily a vertex permutation. Similar results are obtained for mappings that preserve sets of graphs with specified dot product dimensions.

Michelle Robinette1, Jessica Thunet1
1Department of Mathematical Sciences University of Nevada Las Vegas Las Vegas, NV 89154
Abstract:

A permutation π on a set of positive integers {a1,a2,,an} is said to be graphical if there exists a graph containing exactly ai vertices of degree π(ai) for each i (1in). It has been shown that for positive integers with a1<a2<<an, if π(an)=an, then the permutation π is graphical if and only if the sum i=1naiπ(ai) is even and ani=1n1aiπ(ai).

We use a criterion of Tripathi and Vijay to provide a new proof of this result and to establish a similar result for permutations π such that π(an1)=an. We prove that such a permutation is graphical if and only if the sum i=1naiπ(ai) is even and anan1an1(an11)+in1aiπ(ai). We also consider permutations such that π(an)=an1 and, more generally, those such that π(an)=anj for some j (1<j<n).

S. A. Katre1, Laleh Yahyaei1
1Department of Mathematics, S. P. Pune University, Pune-411007, INDIA.
Abstract:

A k-labeling of a graph is a labeling of the vertices of the graph by k-tuples of non-negative integers such that two vertices of G are adjacent if and only if their label k-tuples differ in each coordinate. The dimension of a graph G is the least k such that G has a k-labeling.

Lovász et al. showed that for n3, the dimension of a path of length n is (log2n)+. Lovász et al. and Evans et al. determined the dimension of a cycle of length n for most values of n. In the present paper, we obtain the dimension of a caterpillar or provide close bounds for it in various cases.

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;