Wei Jiang1, Jun Guo1
1College of Math. and Info. Sci., Langfang Teachers University, Langfang 065000, China
Abstract:

This paper obtains new combinatorial batch codes (CBCs) from old ones, studies properties of uniform CBCs, and constructs uniform CBCs using semilattices.

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

For graphs \(F\) and \(H\), where \(H\) has chromatic index \(t\), the proper Ramsey number \(PR(F, H)\) is the smallest positive integer \(n\) such that every \(t\)-edge coloring of \(K_n\) results in a monochromatic \(F\) or a properly colored \(H\). The proper Ramsey number \(PR(F, H)\) is investigated for certain pairs \(F, H\) of connected graphs when \(t = 2\), namely when \(F\) is a complete graph, star, or path and when \(H\) is a path or even cycle of small order. In particular, \(PR(F, H)\) is determined when (1) \(F\) is a complete graph and \(H\) is a path of order 6 or less, (2) \(F\) is a complete graph and \(H\) is a 4-cycle, (3) \(F\) is a star and \(H\) is a 4-cycle or a 6-cycle, and (4) \(F\) is a star and \(H\) is a path of order 8 or less.

Fengnan Yanling1, Chengfu Ye1, Yaping Mao1, Zhao Wang1
1 Department of Mathematics, Qinghai Normal University, Xining, Qinghai 810008, China
Abstract:

The \(k\)-rainbow index \(rx_k(G)\) of a connected graph \(G\) was introduced by Chartrand, Okamoto, and Zhang in 2010. Let \(G\) be a nontrivial connected graph with an edge-coloring \(c: E(G) \to \{1, 2, \ldots, q\}\), \(q \in \mathbb{N}\), where adjacent edges may be colored the same. A tree \(T\) in \(G\) is called a rainbow tree if no two edges of \(T\) receive the same color. For a graph \(G = (V, E)\) and a set \(S \subseteq V\) of at least two vertices, an \(S\)-Steiner tree or a Steiner tree connecting \(S\) (or simply, an \(S\)-tree) is a subgraph \(T = (V’, E’)\) of \(G\) that is a tree with \(S \subseteq V’\). For \(S \subseteq V(G)\) and \(|S| \geq 2\), an \(S\)-Steiner tree \(T\) is said to be a rainbow \(S\)-tree if no two edges of \(T\) receive the same color. The minimum number of colors that are needed in an edge-coloring of \(G\) such that there is a rainbow \(S\)-tree for every \(k\)-set \(S\) of \(V(G)\) is called the \(k\)-rainbow index of \(G\), denoted by \(rx_k(G)\). In this paper, we consider when \(|S| = 3\). An upper bound of complete multipartite graphs is obtained. By this upper bound, for a connected graph \(G\) with \(\text{diam}(G) \geq 3\), we give an upper bound of its complementary graph.

Tingting Liu1, Yumei Hu2
1Department of Mathematics,Tianjin University, Tianjin 300072, P. R. China
2Tianjin Binhai Foreign Language School, Tianjin 300467, P. R. China
Abstract:

A tree \( T \), in an edge-colored graph \( G \), is called a rainbow tree if no two edges of \( T \) are assigned the same color. For a vertex subset \( S \subseteq V(G) \), a tree that connects \( S \) in \( G \) is called an \( S \)-tree. A \( k \)-rainbow coloring of \( G \) is an edge coloring of \( G \) having the property that for every set \( S \) of \( k \) vertices of \( G \), there exists a rainbow \( S \)-tree \( T \) in \( G \). The minimum number of colors needed in a \( k \)-rainbow coloring of \( G \) is the \( k \)-rainbow index of \( G \), denoted by \( rx_k(G) \). It is NP-hard to compute the \( rx_k(G) \) for the general graphs \( G \). We consider the \( 3 \)-rainbow index of complete bipartite graphs \( K_{s,t} \). For \( 3 \leq s \leq t \), we have determined the tight bounds of \( rx_3(K_{s,t}) \). In this paper, we continue the study. For \( 2 \leq s \leq t \), we develop a converse idea and apply it with the model of chessboard to study the problem. Finally, we obtain the exact value of \( rx_3(K_{s,t}) \) with \( 2 \leq s \leq t \).

Tomer Kotek1, James Preen1, Peter Tittmann2
1Faculty of Informatics, Mathematics, Vienna University of Technology, syne ee Ly Coca da Favoritenstr. 9-11, A-1040 Vienna, Austria
2Faculty Mathematics Sciences Computer Sciences Hochschule Mittweida – University of Applied Sciences Mittweida, Germany
Abstract:

The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of the domination polynomials of families of graphs obtained by various products, including both explicit formulae and recurrences for specific families.

Sally Cockburn1
1Department Of Mathematics Hamilton College, Clinton, NY 13323
Abstract:

A graph \( G \) is a homomorphic preimage of another graph \( H \), or equivalently \( G \) is \( H \)-colorable, if there exists a graph homomorphism \( f: G \to H \). A classic problem is to characterize the family of homomorphic preimages of a given graph \( H \). A geometric graph \(\overline{G}\) is a simple graph \( G \) together with a straight line drawing of \( G \) in the plane with the vertices in general position. A geometric homomorphism (resp. isomorphism) \(\overline{G} \to \overline{H}\) is a graph homomorphism (resp. isomorphism) that preserves edge crossings (resp. and non-crossings). The homomorphism poset \(\mathcal{G}\) of a graph \( G \) is the set of isomorphism classes of geometric realizations of \( G \) partially ordered by the existence of injective geometric homomorphisms. A geometric graph \(\overline{G}\) is \(\mathcal{H}\)-colorable if \(\overline{G} \to \overline{H}\) for some \(\overline{H} \in \mathcal{H}\). In this paper, we provide necessary and sufficient conditions for \(\overline{G}\) to be \(C_n\)-colorable for \(3 \leq n \leq 5\).

R. B. Bapat1, Souvik Roy2
1Indian Statistical Institute, Delhi 7-SJSS Marg, New Delhi 110 016, India.
2Indian Statistical Institute, Kolkata 203, B.T. Road Kolkata 700 108, India.
Abstract:

The mixed discriminant of an \(n\)-tuple of \(n \times n\) matrices \(A_1, \ldots, A_n\) is defined as $$\mathcal{D}(A_1, A_2, \ldots, A_n) = \frac{1}{n!} \sum_{\sigma \in S(n)} \det(A_{\sigma(1)}^{(1)}, A_{\sigma(2)}^{(2)}, \ldots, A_{\sigma(n)}^{(n)}),$$
where \(A^{(i)}\) denotes the \(i\)th column of the matrix \(A\) and \(S(n)\) denotes the group of permutations of \(1, 2, \ldots, n\). For \(n\) matrices \(A_1, \ldots, A_n\) and indeterminates \(\lambda_1, \ldots, \lambda_n\), set $$\Phi_{\lambda_1, \ldots, \lambda_n}(A_1, \ldots, A_n) = \mathcal{D}(\lambda_1 I – A_1, \ldots, \lambda_n I – A_n).$$
It is shown that \(\Phi_{A_1, \ldots, A_n}(A_1, \ldots, A_n) = 0\).

S.R. Allen1, R.C. Bunge2, E. Doebel3, S. I. El-Zanati4, P. Kilgus5, C. Shinners4, S. M. Zeppetello5
1Armstrong Township High School, Armstrong, IL 61812
2Illinois State University, Normal, IL 61790
3Iowa State University, Ames, A 50011
4University of Wisconsin-La Crosse, La Crosse, WI 54601
5East Leyden High School, Franklin Park, IL 60131
Abstract:

For a graph \(H\) and a positive integer \(\lambda\), let \( ^{\lambda}{H} \) denote the multigraph obtained by replacing each edge of \(H\) with \(\lambda\) parallel edges. Let \(G\) be a multigraph with edge multiplicity \(2\) and with \(C_4\) as its underlying simple graph. We find necessary and sufficient conditions for the existence of a \(G\)-decomposition of \( ^{\lambda}{K_n} \) for all positive integers \(\lambda\) and \(n\).

Simon Crevals1, Patric R. J. Ostergard1
1Department of Communications and Networking Aalto University School of Electrical Engineering P.O. Box 13000, 00076 Aalto, Finland
Abstract:

The size of a minimum total dominating set in the \(m \times n\) grid graph is denoted by \(\gamma_t(P_m \square P_n)\). Here a dynamic programming algorithm that computes \(\gamma_t(P_m \square P_n)\) for any \(m\) and \(n\) is presented, and it is shown how properties of the algorithm can be used to derive formulae for a fixed, small value of \(m\). Using this method, formulae for \(\gamma_t(P_m \square P_n)\) for \(m \leq 28\) are obtained. Formulae for larger \(m\) are further conjectured, and a new general upper bound on \(\gamma_t(P_m \square P_n)\) is proved.

Ricky X. F. Chen1, Christian M. Reidys1
1 Virginia Bioinformatics Institute and Dept. of Mathematics, Virginia Tech, 1015 Life Sciences Circle, Blacksburg, VA 24061, USA
Abstract:

The 2-cell embeddings of graphs on closed surfaces have been widely studied. It is well known that (2-cell) embedding a given graph \(G\) on a closed orientable surface is equivalent to cyclically ordering the darts incident to each vertex of \(G\). In this paper, we study the following problem: given a genus \(g\) embedding \(\in\) of the graph \(G\) and a vertex of \(G\), how many different ways of reembedding the vertex such that the resulting embedding \(\in’\) is of genus \(g + \Delta g\)? We give formulas to compute this quantity and the local minimal genus achieved by reembedding. In the process, we obtain miscellaneous results. In particular, if there exists a one-face embedding of \(G\), then the probability of a random embedding of \(G\) to be one-face is at least \(\prod_{v \in V(G)} \frac{2}{\deg(v) + 2}\) where \(\deg(v)\) denotes the vertex degree of \(v\). Furthermore, we obtain an easy-to-check necessary condition for a given embedding of \(G\) to be an embedding of minimum genus.

Brooke Logan1, Michael J. Mossinghoff2ORIC ID
1Department of Mathematics, Rowan University, Glasssoro, NJ 08028 USA
2Department of Mathematics and Computer Science, Davidson Collecee, Davipson, NC 28035-6996 USA
Abstract:

We show that all but \(4489\) integers \(n\) with \(4 < n \leq 4 \cdot 10^{30}\) cannot occur as the order of a circulant Hadamard matrix. Our algorithm allows us to search \(10000\) times farther than prior efforts, while substantially reducing memory requirements. The principal improvement over prior methods involves the incorporation of a separate search for double Wieferich prime pairs \(\{p, q\}\), which have the property that \(p^{q-1} \equiv 1 \pmod{q^2}\) and \(q^{p-1} \equiv 1 \pmod{p^2}\).

Marc Glen1, Sergey Kitaevt2
1School of Computer and Information Sciences, University of Strathclyde, Glasgow, G1 1HX, UK.
2School of Computer and Information Sciences, University of Strathclyde, Glasgow, Gi 1HX, UK.
Abstract:

A graph \( G = (V, E) \) is word-representable if there exists a word \( w \) over the alphabet \( V \) such that letters \( x \) and \( y \) alternate in \( w \) if and only if \( (x, y) \) is an edge in \( E \).

A recent elegant result of Akrobotu \( et \, al. \) \([1]\) states that a triangulation of any convex polyomino is word-representable if and only if it is 3-colourable. In this paper, we generalize a particular case of this result by showing that the result of Akrobotu \( et \, al. \) \([1]\) is true even if we allow a domino tile, instead of having just \(1 \times 1\) tiles on a rectangular polyomino.

Abstract:

The eternal domination number of a split graph is shown to equal either its domination number, or its domination number plus one. A characterization of the split graphs which achieve equality in either instance is given. It is shown that the problem of deciding whether the domination number of a Hamiltonian split graph is at most a given integer \(k\) is NP-complete, as is the problem of deciding whether the eternal domination number of a Hamiltonian split graph is at most a given integer \(k\). Finally, the problem of computing the eternal domination number is shown to be polynomial for any subclass of split graphs for which the domination number can be computed in polynomial time, in particular for strongly chordal split graphs.

Zhenming Bi1, Alexis Byers1, Sean English1, Elliot Laforge1, Ping Zhang1
1 Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
Abstract:

A graceful labeling of a graph \( G \) of order \( n \) and size \( m \) is a one-to-one function \( f : V(G) \rightarrow \{0, 1, \ldots, m\} \) that induces a one-to-one function \( f’ : E(G) \rightarrow \{1, 2, \ldots, m\} \) defined by \( f'(uv) = |f(u) – f(v)| \). A graph that admits a graceful labeling is a graceful graph. A proper coloring \( c : V(G) \rightarrow \{1, 2, \ldots, k\} \) is called a graceful \( k \)-coloring if the induced edge coloring \( c’ \) defined by \( c'(uv) = |c(u) – c(v)| \) is proper. The minimum positive integer \( k \) for which \( G \) has a graceful \( k \)-coloring is its graceful chromatic number \( \chi_g(G) \). The graceful chromatic numbers of cycles, wheels, and caterpillars are determined. An upper bound for the graceful chromatic number of trees is determined in terms of its maximum degree.

Abstract:

For a graph \( G = (V, E) \) with a coloring \( f : V(G) \rightarrow \mathbb{Z}_2 \), let \( v_f(i) = |f^{-1}(i)| \). We say \( f \) is friendly if \( |v_f(1) – v_f(0)| \leq 1 \). The coloring \( f \) induces an edge labeling \( f_+ : E \rightarrow \mathbb{Z}_2 \) defined by \( f_+(uv) = f(u) + f(v) \mod 2 \), for each \( uv \in E \). Let \( e_f = |f_+^{-1}(i)| \). The friendly index set of the graph \( G \), denoted by \( FI(G) \), is defined by \(\{|e_f(1) – e_f(0)| : f \text{ is a friendly coloring of } G \}\). We say \( G \) is fully cordial if \( FI(G) = \{|E|, |E| – 2, |E| – 4, \ldots, |E| – 2[\binom{|E|}{2}]\} \). In this paper, we develop a new technique to calculate friendly index sets without labeling vertices, and we develop a technique to create fully cordial graphs from smaller fully cordial graphs. In particular, we show the first examples of fully cordial graphs that are not trees, as well as new infinite classes of fully cordial graphs.

Mohammad Abudayah1, Hasan Al-Ezeh2
1Department of Mathematics German Jordanian University
2Department of Mathematics University of Jordan
Abstract:

This paper studies the unitary Cayley graph associated with the ring of dual numbers, \(\mathbb{Z}_n[\alpha]\). It determines the exact diameter, vertex chromatic number, and edge chromatic number. In addition, it classifies all perfect graphs within this class.

Abstract:

Stanton-type graphs were introduced recently. In this paper, we define generalized Stanton-type graphs. We also identify LO and OE graphs, find the minimum \(\lambda\) for decomposition of \(\lambda K_n\) into these graphs, and show that for all viable values of \(\lambda\), the necessary conditions are sufficient for LO- and OE-decompositions using cyclic decompositions from base graphs.

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

For a finite graph \(G\) with vertices \(\{v_1, \ldots, v_r\}\), a representation of \(G\) modulo \(n\) is a set \(\{a_1, \ldots, a_r\}\) of distinct, nonnegative integers with \(0 \leq a_i < n\), satisfying \(\gcd(a_i – a_j, n) = 1\) if and only if \(v_i\) is adjacent to \(v_j\). The representation number, \(Rep(G)\), is the smallest \(n\) such that \(G\) has a representation modulo \(n\). Evans \(et \, al.\) obtained the representation number of paths. They also obtained the representation number of a cycle except for cycles of length \(2^k + 1\), \(k \geq 3\). In the present paper, we obtain upper and lower bounds for the representation number of a caterpillar, and get its exact value in some cases.

Gaowen Xi1
1College of Mathematics and Physics Chongqing University of Science and Technology Chongaing, 401331, P. R. China
Abstract:

By applying the method of generating functions, the purpose of this paper is to give several summations of reciprocals related to the quintuple product of the general second-order recurrence \(\{W_{rn}\}\) for arbitrary positive integers \(r\). As applications, some identities involving Fibonacci and Lucas numbers are obtained.

Michael Epstein1, Spyros S. Magliveras1, Daniela Nikolova-Popova1
1Department of Mathematical Sciences, Florida Atlantic University Boca Raton, FL 33431
Abstract:

A collection \(\mathcal{S}\) of proper subgroups of a group \(G\) is said to be a cover (or covering) for \(G\) if the union of the members of \(\mathcal{S}\) is all of \(G\). A cover \(\mathcal{C}\) of minimal cardinality is called a minimal cover for \(G\) and \(|\mathcal{C}|\) is called the covering number of \(G\), denoted by \(\sigma(G)\). In this paper we determine the covering numbers of the alternating groups \(A_9\) and \(A_{11}\).

L. J. Langley1, S. K. Merz1
1University of the Pacific
Abstract:

Given a (not necessarily proper) coloring of a digraph \( c:V(D)\rightarrow\mathds{N}\), let \( OC(v)\) denote the set of colors assigned to the out-neighbors of \(v\). Similarly, let \( IC(v)\) denote the set of colors assigned to the in-neighbors of \(v\). Then \(c\) is a set coloring of \(D\) provided \((u,v) \in A(D)\) implies \( OC(u) \neq OC(v)\). Analogous to the set chromatic number of a graph given by Chartrand, \(et\) \(al.\) \([3]\), we define \( \chi_s(D) \) as the minimum number of colors required to produce a set coloring of \(D\). We find bounds for \(\chi_s(D)\) where \(D\) is a digraph and where \(D\) is a tournament. In addition we consider a second set coloring, where \((u,v) \in A(D)\) implies \( OC(u) \neq IC(v)\).

Marilyn Breen1
1The University of Oklahoma Norman, Oklahoma 73019 U.S.A.
Abstract:

Let \(\mathcal{C}\) be a finite family of distinct boxes in \(\mathbb{R}^d\), with \(G\) the intersection graph of \(\mathcal{C}\), and let \(S = \cup\{C : C \in \mathcal{C}\}\). For each block of \(G\), assume that the corresponding members of \(\mathcal{C}\) have a staircase convex union. Then when \(S\) is staircase starshaped, its staircase kernel will be a staircase convex set. Moreover, this result (and others) will hold for more general families \(\mathcal{C}\) as well.

Jason Hedetniemi1, Kevin James1
1Department of Mathematical Sciences Clemson University Clemson, South Carolina 29634 U.S.A.
Abstract:

The domination chain \(\iota_r(G) \leq \gamma(G) \leq \iota(G) \leq \beta_o(G) \leq \Gamma(G) \leq IR(G)\), which holds for any graph \(G\), is the subject of much research. In this paper, we consider the maximum number of edges in a graph having one of these domination chain parameters equal to \(2\) through a unique realization. We show that a specialization of the domination chain still holds in this setting.

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;