Indra Rajasingh1, Bharati Rajan1, M. Arockiaraj1, Paul Manuel2
1Department of Mathematics, Loyola College, Chennai 600 034, India
2Department of Information Science, Kuwait University, Safat, Kuwait.
Abstract:

A labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge (x,y) is the absolute value of the difference of the labels of x and y. We say that a labeling of the vertices of a graph of order n is minimally k-equitable if the vertices are labeled with 1,2,,n and in the induced labeling of its edges, every label either occurs exactly k times or does not occur at all. In this paper, we prove that Butterfly and Benes networks are minimally 2r-equitable where r is the dimension of the networks.

C.A. Rodger1, Meredith Roy1
1221 Parker Hall Auburn University, AL USA 36849-5310
Abstract:

The method of large scale group testing has been used in the economical testing of blood samples, and in non-testing situations such as experimental designs and coding theory, for over 50 years. Some very basic questions addressing the minimum number of tests required to identify defective samples still remain unsolved, including the situation where one defective sample in each of two batches are to be found. This gives rise to an intriguing graph theoretical conjecture concerning bipartite graphs, a conjecture which in this paper is proved to be true in the case where vertices in one part of the bipartite graph have low degree.

M.R. Darafsheh1, A.R. Ashrafi2, M. Khademi3
1School of Mathematics, Statistics and Computer Science, College of Science, University of Tehran, Tehran, Iran.
2Department of Mathematics, Faculty of Science, University of Kashan, Kashan, Iran.
3Islamic Azad University, South Tehran Branch, Tehran, Iran.
Abstract:

Using the action of the linear fractional groups L2(q), where q=8,25,27,29,31 and 32, some 1-designs are constructed. It is shown that subgroups of the automorphism group of L2(q) appear as the full automorphism group of the constructed designs. In the cases q=8 and 32, it is shown that the symmetric groups S9 and S33, respectively, appear as the automorphism group of one of the constructed designs.

Yoan José Pinzén Ardila1, Manolis Christodoulakis2, Costas S. Tliopoulos2, Manal Mohamed2
1National University of Colombia Department of System Engineering and Industrial Engineering Ciudad Universitaria – Bogoté D.C.- Colombia Avenida Carrera 30 No 45-03
2King’s College London, Department of Computer Science, London WC2R 2LS, UK
Abstract:

Here we consider string matching problems that arise naturally in applications to music retrieval. The δ-Matching problem calculates, for a given text T1..n and a pattern P1..m on an alphabet of integers, the list of all indices Iδ={1inm+1:maxj=1m{|PjTi+j1|δ}}. The γ-Matching problem computes, for given T and P, the list of all indices Iγ={1inm+1:j=1m|PjTi+j1|γ}. In this paper, we extend the current result on the different matching problems to handle the presence of “\emph{don’t care}” symbols. We present efficient algorithms that calculate Iδ, Iγ, and I(δ,γ)=IδIγ for pattern P with occurrences of “don’t cares”.

Abdollah Khodkar1, David Leach1
1Department of Mathematics University of West Georgia Carrollton, GA 30118
Abstract:

In 2004, Kim and Nakprasit showed that the chromatic number of K2(9,4) is at least 11. In this note we present an 11-coloring for K2(9,4) (the square of the Kneser graph K(9,4)). This proves that the chromatic number of K2(9,4) is 11.

S. Arumugam1, K. A. Germina2, T.M.K. Anandavally3
1Core Group Research Facility (CGRF) National Centre for Advanced Research in Discrete Mathematics (n-CARDMATH) Kalasalingam University Anand Nagar,Krishnankoil-626 190. INDIA
2Department of Mathematics Mary Matha Arts and Science College Mananthavadi- 670645 Kerala, India.
3Department of Mathematics Payyanur College Payyanur-670327 Kerala, India.
Abstract:

Let N and Z denote respectively the set of all nonnegative integers and the set of all integers. A (p,q)-graph G=(V,E) is said to be additively (a,r)-geometric if there exists an injective function f:VZ such that f+(E)={a,ar,,arq1} where a,rN, r>1, and f+ is defined by f+(uv)=f(u)+f(v) for all uvE. If further f(v)N for all vV, then G is said to be additively (a,r)-geometric. In this paper we characterise graphs which are additively geometric and additively -geometric.

lias S.Kotsireas1, Christos Koukouvinos2
1Department of Phys. and Comp. Sci. Wilfrid Laurier University Waterloo ON, N2L 3C5, Canada
2Department of Mathematics – National Technical University of Athens Zografou 15773, Athens, Greece
Abstract:

In this paper we find ten new weighing matrices of order 2n and weight 2n5 constructed from two circulants, by forming a conjecture on the locations of the five zeros in a potential solution. Establishing patterns for the locations of zeros in sequences that can be used to construct weighing matrices seems to be a worthwhile path to explore, as it reduces significantly the computational complexity of the problem.

Italo J.Dejter1, Abel A.Delgado2
1University of Puerto Rico Rio Piedras, PR 00931-3355
2 Auburn University Auburn, AL 36849-531
Abstract:

A dominating set S in a graph G is said to be perfect if every vertex of G not in S is adjacent to just one vertex of S. Given a vertex subset S of a side Pm of an m×n grid graph G, the perfect dominating sets S in G with S=SV(Pm) can be determined via an exhaustive algorithm of running time O(2m+n). Extending to infinite grid graphs of width m1, periodicity makes the binary decision tree of prunable into a finite threaded tree, a closed walk of which yields all such sets S. The graphs induced by the complements of such sets S can be codified by arrays of ordered pairs of positive integers via , for the growth and determination of which a speedier algorithm exists. A recent characterization of grid graphs having total perfect codes S (with just 1-cubes as induced components), due to Klostermeyer and Goldwasser, is given in terms of , which allows to show that these sets S are restrictions of only one total perfect code S1 in the integer lattice graph Λ of R2. Moreover, the complement ΛS1 yields an aperiodic tiling, like the Penrose tiling. In contrast, the parallel, horizontal, total perfect codes in Λ are in 11 correspondence with the doubly infinite {0,1}-sequences.

E. Butzen1, S. I. El-Zanatif 1, A. Modica1, R. Schrishuhn1, H. Jordon1
14520 Mathematics Department Illinois State University Normal, Illinois 61790-4520, U.S.A.
Abstract:

Let G be a graph of size n with vertex set V(G) and edge set E(G). A ρ-labeling of G is a one-to-one function f:V(G){0,1,,2n} such that {|f(u)f(v)|:{u,v}E(G)}={x1,x2,,xn}, where for each i{1,2,,n} either xi=i or xi=2n+1i. Such a labeling of G yields a cyclic G-decomposition of K2n+1. It is conjectured by El-Zanati and Vanden Eynden that every 2-regular graph G admits a ρ-labeling. We show that the union of up to ten vertex-disjoint C4x+1 admits a ρ-labeling.

Alan C.H.Ling1, J.H. Dinitz2
1Dept. of Computer Science University of Vermont Burlington, Vermont
2Dept. of Mathematics and Statistics University of Vermont Burlington, Vermont
Abstract:

The Hamilton-Waterloo problem in the case of triangle-factors and Hamilton cycles asks for a 2-factorization of Kn, in which each 2-factor is either a Hamilton cycle or a triangle-factor. Necessarily n3(mod6). The case of n9(mod18) was completely solved in 2004 by Horak, Nedela, and Rosa. In this note, we solve the problem when n3(mod18) and there are at least two Hamilton cycles. A companion paper treats the case when there is exactly one Hamilton cycle and n3(mod6).

M.J. Grannell1, T.S. Griggs2, G. LoFaro2, A. Tripodi2
1Department of Mathematics and Statistics The Open University Walton Hall Milton Keynes MK7 6AA UNITED KINGDOM
2Dipartimento di Matematica Universita di Messina Contrado Papardo Salita Sperone 31 98166 Sant’ Agata Messina ITALIA
Abstract:

There exist 3 near bowtie systems of order 7, 12 bowtie systems of order 9, and 1,411,422 balanced bowtie systems of order 13.

R.Douglas Chatham1, Maureen Doyle2, John J. Miller2, Amber M. Rogers2, R. Duane Skaggs1, Jeffrey A. Ward 2
1Department of Mathematics and Computer Science, Morehead State University, Morehead, Kentucky 40351 USA
2Department of Computer Science, Northern Kentucky University, Highland Heights, Kentucky 41099 USA
Abstract:

Chessboard separation problems are modifications to classic chessboard problems, such as the N Queens Problem, in which obstacles are placed on the chessboard. This paper focuses on a variation known as the N+k Queens Problem, in which k Pawns and N+k mutually non-attacking Queens are to be placed on an N-by-N chessboard. Results are presented from performance studies examining the efficiency of sequential and parallel programs that count the number of solutions to the N+k Queens Problem using traditional backtracking and dancing links. The use of Stochastic Local Search for determining the existence of solutions is also presented. In addition, preliminary results are given for a similar problem, the N+k Amazons.

G.L. Chia1, Chee-Kit Ho2
1Institute of Mathematical Sciences, University of Malaya 50603 Kuala Lumpur, Malaysia
2Department of Science & Mathematics Universiti Tenaga Nasional, 43009 Kajang, Selangor, Malaysia
Abstract:

In this paper, it is shown that the graph obtained by overlapping the cycle Cm (m3) and the complete bipartite graph K3,3 at an edge is uniquely determined by its chromatic polynomial.

Rommel Barbosa1, Bert Hartnell2
1Instituto de Informatica – UFG Goiania – GO, Brazil
2Department of Mathematics and Computing Science Saint Mary’s Universty, Halifax, Canada.
Abstract:

A graph G is said to be in the collection Mt if there are precisely t different sizes of maximal independent sets of vertices in G. For GMt, and vG, we determine the extreme values that x can assume where G{v} belongs to Mx. For both the minimum and maximum values, graphs are given that achieve them, showing that the bounds are sharp. The effect of deleting an edge from G on the number of sizes of maximal independent sets is also considered.

Amir Barghi1, Hossein Shahmohamad2
1Department of Mathematics Dartmouth College, Hanover, NH 03755
2School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623
Abstract:

The chromatic polynomial of a graph G, P(G;λ), is the polynomial in λ which counts the number of distinct proper vertex λ-colorings of G, given λ colors. We compute P(C4×Pn;λ) and P(C5×Pn;λ) in matrix form and will find the generating function for each of these sequences.

L.J. Cummings1
1Faculty of Mathematics, University of Waterloo Waterloo,Ontario, Canada N2L 3G1
Abstract:

The n-cube is the graph whose vertices are all binary words of length n>1 and whose edges join vertices that differ in exactly one entry; i.e., are at Hamming distance 1 from each other. If a word has a non-empty prefix, not the entire word, which is also a suffix, then it is said to be bordered. A word that is not bordered is unbordered. Unbordered words have been studied extensively and have applications in synchronizable coding and pattern matching. The neighborhood of an unbordered word w is the word itself together with the set of words at Hamming distance 1 from w. Over the binary alphabet, the neighborhood of an unbordered word w always contains two bordered words obtained by complementing the first and last entries of w. We determine those unbordered words w whose neighborhoods otherwise contain only unbordered words.

Harris Kwong1, Sin-Min Lee2, Sheng-Ping Bill Lo3, Hsin-Hao Su4, Yung-Chin Wang5
1Dept. of Math. Sci. SUNY at Fredonia Fredonia, NY 14063, USA
2Dept. of Comp. Sci. San Jose State University San Jose, CA 95192, USA
3Cisco Systems, Inc. 170 West Tasman Drive San Jose, CA 95134, USA
4Department of Mathematics Stonehill College Easton, MA 02357, USA
5 Dept. of Physical Therapy Tzu-Hui Institute of Technology Taiwan, Republic of China
Abstract:

Let G be a graph with vertex set V and edge set E. A labeling f:V{0,1} induces a partial edge labeling f:E{0,1} defined by f(xy)=f(x) if and only if f(x)=f(y) for each edge xyE. The balance index set of G, denoted BI(G), is defined as {|f1(0)f1(1)|:|f1(0)f1(1)|1}. In this paper, we study the balance index sets of graphs which are L-products with cycles and complete graphs.

Garry L.Johns1, Futaba Okamoto2, Ping Zhang3
1Department of Mathematical Sciences Saginaw Valley State University University Center, MI 48710-0001, USA
2Mathematics Department University of Wisconsin – La Crosse La Crosse, WI 54601, USA
3Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA
Abstract:

For two vertices u and v in a connected graph G, the detour distance D(u,v) between u and v is the length of a longest uv path in G. The detour diameter diamD(G) of G is the greatest detour distance between two vertices of G. Two vertices u and v are detour antipodal in G if D(u,v)=diamD(G). The detour antipodal graph DA(G) of a connected graph G has the same vertex set as G and two vertices u and v are adjacent in DA(G) if u and v are detour antipodal vertices of G. For a connected graph G and a nonnegative integer r, define DAr(G) as G if r=0 and as the detour antipodal graph of DAr1(G) if r>0 and DAr1(G) is connected. Then {DAr(G)} is the detour antipodal sequence of G. A graph H is the limit of {DAr(G)} if there exists a positive integer N such that DAr(G)H for all rN. It is shown that {DAr(G)} converges if G is Hamiltonian. All graphs that are the limit of the detour antipodal sequence of some Hamiltonian graph are determined.

A. Mohr1, T.D. Porter1
1Department of Mathematics Southern Illinois University Carbondale, IL 62901
J. P. McSorley 1, W. D. Wallis1
1Department of Mathematics, Southern Illinois University Carbondale, IL 62901-4408. USA.
Abstract:

For a vertex x in a graph G, we define Ψ1(x) to be the number of edges in the closed neighborhood of x. Vertex x is a neighborhood champion if Ψ1(x)>Ψ1(x) for all xx. We also refer to such an x as a unique champion. For d4, let n0(1,d) be the smallest number such that for every nn0(1,d) there exists an n-vertex d-regular graph with a unique champion. Our main result is that n0(1,d) satisfies d+3n0(1,d)<3d+1. We also observe that there can be no unique champion vertex when d=3.

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 Mathematics New Jersey Institute of Technology Newark, NJ 07102-1982, USA
Abstract:

In this paper, we consider the non-existence of some bi-level orthogonal arrays (O-arrays) of strength six, with m constraints (6m32), and with index set μ (1μ512). The results presented here tend to improve upon the results available in the literature.

P.Mark Kayll1, David Perkins2
1Department of Mathematical Sciences, University of Montana Missoula MT 59812-0864, USA
2Department of Mathematics and Computer Science Houghton College, Houghton NY 14744, USA
Spencer P.Hurd1, Nutan Mishra2, Dinesh G. Sarvate3
1The Citadel, Dept. Math/CS, Charleston, SC, 29409
2Dept. Math. Stastist., Univ. South Alabama, Mobile, AL
3College of Charleston, Dept. Math, Charleston, SC, 29424
Abstract:

We present constructions and results about GDDs with two groups and block size five in which each block has configuration (s,t), that is, in which each block has exactly s points from one of the two groups and t points from the other. After some results for a general k, s, and t, we consider the (2,3) case for block size 5. We give new necessary conditions for this family of GDDs and give minimal or near-minimal index examples for all group sizes n4 except for n=24s+17.

Patrick Bahls1
1Department of Mathematics University of North Carolina, Asheville, NC 28804
Abstract:

We compute the limiting average connectivity κ¯ of the family of 3-regular expander graphs whose members are formed from the finite fields Zp, by connecting every xZp with x±1 and x1, all computations performed modulo p. Namely, we show

limpκ¯(Zp)=3

for primes p. We compare this behavior with an upper bound on the expected value of κ¯(Zn) for a more general class {Zn}nN of related graphs.

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;