K. Brewington!1, R. C. Bunge2, L. J. Cross2, El- Zanati2, C. K. Pawlak2, J. L. Smith1, S. M. Zeppetello2
1Department of Mathematics, Computer Science & Physics Morehead State University Morehead, KY 40351
2Department of Mathematics Illinois State University Normal, IL 61790-4520
Abstract:

Let \( G \) be the one-point union of two cycles and suppose \( G \) has \( n \) edges. We show via various graph labelings that there exists a cyclic \( G \)-decomposition of \( K_{2nt+1} \) for every positive integer \( t \).

Mustafa Asci1, Osman Kecilioglu2, Bijan Davvaz3
1Pamukkale University Science and Arts Faculty Department of Mathematics Denizli Turkey
2Kirikkale University Science And Arts Faculty Department Of Mathematics Kirikkale Turkey
3Yazd UNIVERSITY DEPARTMENT OF MATHEMATICS YAZD IRAN
Abstract:

Recently Ozbal and Firat [22] introduced the notion of symmetric \( f \) bi-derivation of a lattice. They give illustrative examples and they also characterized the distributive lattice by symmetric \( f \) bi-derivation. In this paper, we define the isotone symmetric \( f \) bi-derivation and obtain some interesting results about isotoneness. We also provide the relations between distributive, modular, and isotone lattices through symmetric \( f \) bi-derivation.

Wai Chee Shiu1
1Department of Mathematics, Hong Kong Baptist University, 224 Waterloo Road, Kowloon Tong, Hong Kong, China.
Abstract:

In 2003, Lee, Wang and Wen found a non-edge-magic simple connected cubic graph which satisfying the necessary condition of edge-magicness by using computer search. They asked for a mathematical proof. In this paper, we will provide such a proof.

Jiansheng Cai1
1School of Mathematics and information Sciences, Weifang University, Weifang 261061, P. R. China
Abstract:

Let \( G \) be a graph and let \( f \) be a positive integer-valued function defined on \( V(G) \) such that \( 1 \leq a \leq f(x) \leq b \leq 2a \) for every \( x \in V(G) \). If \( t(G) \geq \frac{b^2}{a} \), \( |V(G)| \geq \frac{b^2}{a} + 1 \), and \( f(V(G)) \) is even, then \( G \) has an \( f \)-factor.

Hau Chan1, Derek W.Hein2, Dinesh G. Sarvate3
1Stony Brook University, Dept. or C. S., Srony Brook, NY, 11794
2SOUTHERN UTAH University, Dept. or MaTH., Cepar City, UT, 84720
3COLLEGE OF CHARLESTON, Dept. OF MATH., CHARLESTON, SC, 29424
Abstract:

A general construction for \( t \)-SB(\(2t-1\), \(2t-2\)) designs is given. In addition, large sets of \( t \)-SB(\(v\), \(k\)) are discussed and some examples are provided.

Shota Konishi1, Kenjiro Ogawa1, Satoshi Tagusari1, Morimasa Tsuchitya1
1Department of Mathematical Sciences, Tokai University Hiratsuka 259-1292, JAPAN
Abstract:

For a poset \( P = (X, \leq_P) \), the strict-double-bound graph (\(sDB\)-graph) of \( P = (X, \leq_P) \) is the graph \( sDB(P) \) on \( X \) for which vertices \( u \) and \( v \) of \( sDB(P) \) are adjacent if and only if \( u \neq v \) and there exist \( x \) and \( y \) in \( X \) distinct from \( u \) and \( v \) such that \( x \leq u \leq y \) and \( x \leq v \leq y \). The strict-double-bound number \( \zeta(G) \) is defined as

\[
\zeta(G) = \min \{ n \mid G \cup N_n \text{ is a strict-double-bound graph} \},
\]

where \( N_n \) is the graph with \( n \) vertices and no edges.

In this paper we deal with strict-double-bound numbers of some graphs. For example, we obtain that

\[
\zeta(P_n) = \lceil 2\sqrt{n-1} \rceil \text{ (} n \geq 2 \text{)},
\]

\[
\zeta(C_n) = \lceil 2\sqrt{n} \rceil \text{ (} n \geq 4 \text{)},
\]

\[
\zeta(W_n) = \lceil 2\sqrt{n-1} \rceil \text{ (} n \geq 5 \text{)},
\]

and

\[
\zeta(G + K_n) = \zeta(G)
\]

for a graph \( G \) with no isolated vertices.

Linda Eroh1, Cong X. Kang2, Eunjeong Yi2
1University of Wisconsin Oshkosh, Oshkosh, WI 54801, US
2Texas A&M University at Galveston, Galveston, TX 77553, USA
Abstract:

The metric dimension of a graph \(G\), denoted by \(\text{dim}(G)\), is the minimum number of vertices such that all vertices are uniquely determined by their distances to the chosen vertices. For a graph \(G\) and its complement \(\overline{G}\), each of order \(n \geq 4\) and connected, we show that

\[
2 \leq \text{dim}(G) + \text{dim}(\overline{G}) \leq 2(n-3).
\]

It is readily seen that \(\text{dim}(G) + \text{dim}(\overline{G}) = 2\) if and only if \(n = 4\). We characterize graphs satisfying

\[
\text{dim}(G) + \text{dim}(\overline{G}) = 2(n-3)
\]

when \(G\) is a tree or a unicyclic graph.

Bill Butler1, Stephanie Costa2, Norman J.Finizio3, Christopher Teixeira4
1238 Pine Ridge Loop Durango, CO 81301
2Department of Mathematics Rhode Island College Providence, RI 02906
3Department of Mathematics University of Rhode Island Rhode Kingston, RI 02881
4Department of Mathematics Rhode Island College Providence, Ri 02906
Abstract:

Whist tournament designs are known to exist for all \( v \equiv 0,1 \pmod{4} \). Much less is known about the existence of \(\mathbb{Z}\)-cyclic whist designs. Previous studies \([5, 6]\) have reported on all \(\mathbb{Z}\)-cyclic whist designs for \( v \in \{4,5,8,9,12,13,16,17,20,21,24,25\} \). This paper is a report on all \(\mathbb{Z}\)-cyclic whist tournament designs on 28 players, including a detailed summary of all known whist specializations related to a 28 player \(\mathbb{Z}\)-cyclic whist design. Our study shows that there are \( 7,910,127 \) \(\mathbb{Z}\)-cyclic whist designs on 28 players. Of these designs, \( 2,568,510 \) possess the Three Person Property, \( 240,948 \) possess the Triplewhist Property and none possess the Balancedwhist Property. Introduced here is the concept of the mirror image of a \(\mathbb{Z}\)-cyclic whist design. In general, utilization of this concept reduces the computer search for \(\mathbb{Z}\)-cyclic whist designs by nearly fifty percent.

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

Let \( S \) be an orthogonal polygon in the plane bounded by a simple closed curve. Assume that every two boundary points of \( S \) have a common staircase illuminator whose edges are north and east. Then \( S \) contains a staircase path \( \mu_0 \) whose edges are north and east such that \( \mu_0 \) illumines every point of \( S \). Without the requirement that the illuminators share a common direction, the result fails.

Changming Su1, Fangnian Lang1,2, Zehui Shao1
1School of Information Science & Technology, Chengdu University, Chengdu, 610106, China; University Key Laboratory of Pattern Recognition and Intelligent Information Processing, Sichuan Province
2School of Electronic Engineering, University of Electronic Science and Technology of China, Chengdu, 610054, China
Abstract:

The upper domination Ramsey number \(u(3, 3, 3)\) is the smallest integer \(n\) such that every \(3\)-coloring of the edges of complete graph \(K_n\) contains a monochromatic graph \(G\) with \(\Gamma(\overline{G}) \geq 3\), where \(\Gamma(\overline{G})\) is the maximum order over all the minimal dominating sets of the complement of \(G\). In this note, with the help of computers, we determine that \(U(3, 3, 3) = 13\), which improves the results that \(13 \leq U(3, 3, 3) \leq 14\) provided by Michael A. Henning and Ortrud R. Oellermann.

Jiansheng Cai1
1School of Mathematics and information Sciences, Weifang University, Weifang 261061, P. R. China
Abstract:

Let \(G\) be a graph of order \(n \geq 4k+8\), where \(k\) is a positive integer with \(kn\) even and \(\delta(G) > k+1\). We show that if \(max\{d_G(u),d_G(v)\} > {n}/{2}\) for each pair of nonadjacent vertices \(u,v\), then \(G\) has a connected \([k, k+1]\)-factor excluding any given edge \(e\).

Abhaya M.Chitre1, Nirmala B.Limaye2
1Department of Mathematics D. G. Ruparel College Mahim, Mumbai 400025
2Department of Mathematics Indian Institute of Technology Powai, Mumbai 400076
Abstract:

A \( k \)-edge labeling of a graph \( G \) is a function \( f \) from the edge set \( E(G) \) to the set of integers \( \{0, \ldots, k-1\} \). Such a labeling induces a labeling \( f \) on the vertex set \( V(G) \) by defining \( f(v) = \sum f(e) \), where the summation is taken over all the edges incident on the vertex \( v \) and the value is reduced modulo \( k \). Cahit calls this labeling edge-\( k \)-equitable if \( f \) assigns the labels \( \{0, \ldots, k-1\} \) equitably to the vertices as well as edges.

If \( G_1, \ldots, G_T \) is a family of graphs having a graph \( H \) as an induced subgraph, then by \( H \)-union \( G \) of this family we mean the graph obtained by identifying all the corresponding vertices as well as edges of the copies of \( H \) in \( G_1, \ldots, G_T \).

In this paper we prove that the \( \overline{K}_n \)-union of gears is edge-\( 3 \)-equitable.

M. Sheikholeslami1, L. Volkmann2
1Department of Mathematics Azarbaijen University of Tarbiat Moallem Tabriz, I.R. Iran
2Lehrstuhl II fiir Mathematik RWTH Aachen University 52056 Aachen, Germany
Abstract:

Let \( k \) be a positive integer and let \( G \) be a simple graph with vertex set \( V(G) \). If \( v \) is a vertex of \( G \), then the open \( k \)-neighborhood of \( v \), denoted by \( N_{k,G}(v) \), is the set \( N_{k,G}(v) = \{u \mid u \neq v \text{ and } d(u, v) \leq k\} \). The closed \( k \)-neighborhood of \( v \), denoted by \( N_{k,G}[v] \), is \( N_{k,G}[v] = N_{k,G}(v) \cup \{v\} \). A function \( f: V(G) \to \{-1,1\} \) is called a \({signed\; distance \; k -dominating\; function}\) if \( \sum_{u \in N_{k,G}(v)} f(u) \geq 1 \) for each vertex \( v \in V(G) \). A set \( \{f_1, f_2, \ldots, f_d\} \) of signed distance \( k \)-dominating functions on \( G \) with the property that \( \sum_{i=1}^d f_i(v) \leq 1 \) for each \( v \in V(G) \) is called a \({signed\; distance \; k -dominating \;family}\) (of functions) on \( G \). The maximum number of functions in a signed distance \( k \)-dominating family on \( G \) is the \({signed\; distance \; k -domatic\; number}\) of \( G \), denoted by \( d_{k,s}(G) \). Note that \( d_{1,s}(G) \) is the classical signed domatic number \( d_s(D) \). In this paper, we initiate the study of signed distance \( k \)-domatic numbers in graphs and we present some sharp upper bounds for \( d_{k,s}(G) \).

Min Sha1
1Institut De Mathématiques De Bordeaux, Université Bordeaux 1, 351, Cours De La Libération, 33405 Talence Cedex, France
Abstract:

We associate each endomorphism of a finite cyclic group with a digraph and study many properties of this digraph, including its adjacency matrix and automorphism group.

Qiuju Bian1
1Science School, Shandong University of Technology, Zibo, 255049, P. R. China.
Abstract:

In this paper, we consider a variation of toughness, and prove stronger results for the existence of \([a, b]\)-factors. Furthermore, we show that the results are sharp in some sense.

Robert A. Beeler1
1East Tennessee State University Johnson City, TN 37614-1700 USA
Abstract:

A decomposition \( \mathcal{D} \) of a graph \( H \) by a graph \( G \) is a partition of the edge set of \( H \) such that the subgraph induced by the edges in each part of the partition is isomorphic to \( G \). The intersection graph \( I(\mathcal{D}) \) of the decomposition \( \mathcal{D} \) has a vertex for each part of the partition and two parts \( A \) and \( B \) are adjacent if and only if they share a common node in \( H \). If \( I(\mathcal{D}) \cong H \), then \( \mathcal{D} \) is an automorphic decomposition of \( H \). If \( n(G) = \chi(H) \) as well, then we say that \( \mathcal{D} \) is a fully automorphic decomposition. In this paper, we examine the question of whether a fully automorphic host will have an even degree of regularity. We also give several examples of fully automorphic decompositions as well as necessary conditions for their existence.

Futaba Fujie1, Topp G. Witt2
1Graduate School of Mathematics, Nagoya University, Nagoya 464-8602, Japan.
2Mathematics department, University of Wisconsin-La Crosse, La Crosse, WI 54601, USA.
Abstract:

A modular \(k\)-coloring, \(k \geq 2\), of a graph \(G\) without isolated vertices is a coloring of the vertices of \(G\) with the elements in \(\mathbb{Z}_k\) (where adjacent vertices may be colored the same) having the property that for every two adjacent vertices in \(G\) the sums of the colors of their neighbors are different in \(\mathbb{Z}_k\). The minimum \(k\) for which \(G\) has a modular \(k\)-coloring is the modular chromatic number mc\((G)\) of \(G\). It is known that \(2 \leq \text{mc}(T) \leq 3\) for every nontrivial tree \(T\). We present an efficient algorithm that computes the modular chromatic number of a given tree.

P. C. Li1
1Dept. of Computer Science University of Manitoba Winnipeg, Manitoba Canada R3T 2N2
Abstract:

In this note, we consider the \(i\)-block intersection graphs (\(i\)-BIG) of a universal friendship \(3\)-hypergraph and show that they are pancyclic for \(i = 1,2\). We also show that the \(1\)-BIG of a universal friendship \(3\)-hypergraph is Hamiltonian-connected.

Arnold Knopfmacher1, Toufik Mansour2
1The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics University of the Witwatersrand, Johannesburg, South Africa
2Department of Mathematics University of Haifa, 31905 Haifa, Israel
Abstract:

We study samples \(\Gamma = (\Gamma_1, \ldots, \Gamma_n)\) of length \(n\) where the letters \(\Gamma_i\) are independently generated according to the geometric distribution \(\mathbb{P}(\Gamma_j = i) = pq^{i-1}\), for \(1 \leq j \leq n\), with \(p+q=1\) and \(0<p<1\). An \({up-smooth\; sample}\) \(\Gamma\) is a sample such that \(\Gamma_{i+1}- \Gamma_i \leq 1\). We find generating functions for the probability that a sample of \(n\) geometric variables is up-smooth, with or without a specified first letter. We also extend the up-smooth results to words over an alphabet of \(k\) letters and to compositions of integers. In addition, we study smooth samples \(T\) of geometric random variables, where the condition now is \(|\Gamma_{i+1}- \Gamma_i| \leq 1\).

Nader Jafari Rad1
1Department of Mathematics, Shahrood University of Technology, Shahrood, Iran
Abstract:

A Roman dominating function on a graph \(G = (V, E)\) is a function \(f : V \to \{0,1,2\}\) satisfying the condition that every vertex \(u \in V\) for which \(f(u) = 0\) is adjacent to a vertex \(v\) for which \(f(v) = 2\). The weight of a Roman dominating function is the value \(f(V) = \sum_{u \in V} f(u)\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum weight of a Roman dominating function on \(G\). In this paper, we study those graphs for which the removal of any pair of vertices decreases the Roman domination number. A graph \(G\) is said to be \emph{Roman domination bicritical} or just \(\gamma_R\)-bicritical, if \(\gamma_R(G – \{v,u\}) < \gamma_R(G)\) for any pair of vertices \(v,u \in V\). We study properties of \(\gamma_R\)-bicritical graphs, and we characterize \(\gamma_R\)-bicritical trees and unicyclic graphs.

Meilian Liang1, Xiaodong Xu2, Zehui Shao3, Baoxin Xiu4
1School of Mathematics and Information Science, Guangxi University, Nanning 530004, China
2Guangxi Academy of Sciences, Nanning 530007, China
3Key Laboratory of Pattern Recognition and Intelligent Information Processing, School of Information Science & Technology, Chengdu University, Chengdu 610106, China
4College of Information System and Management, National University of Defense Technology, Changsha 410073, China
Abstract:

The van der Waerden number \(W(r, k)\) is the least integer \(N\) such that every \(r\)-coloring of \(\{1, 2, \ldots, N\}\) contains a monochromatic arithmetic progression of length at least \(k\). Rabung gave a method to obtain lower bounds on \(W(2, k)\) based on quadratic residues, and performed computations on all primes no greater than \(20117\). By improving the efficiency of the algorithm of Rabung, we perform the computation for all primes up to \(6 \times 10^7\), and obtain lower bounds on \(W(2, k)\) for \(k\) between \(11\) and \(23\).

S. Arumugam1, K. Raja Chandrasekar1
1National Centre for Advanced Research in Discrete Mathematics (r-CARDMATH) Kalasalingam University Anand Nagar, Krishnankoil-626126, INDIA.
Abstract:

Let \( G = (V, E) \) be a graph with chromatic number \( k \). A dominating set \( D \) of \( G \) is called a chromatic transversal dominating set (ctd-set) if \( D \) intersects every color class of any \( k \)-coloring of \( G \). The minimum cardinality of a ctd-set of \( G \) is called the chromatic transversal domination number of \( G \) and is denoted by \( \gamma_{ct}(G) \). In this paper, we obtain sharp upper and lower bounds for \( \gamma_{ct} \) for the Mycielskian \( \mu(G) \) and the shadow graph \( \text{Sh}(G) \) of any graph \( G \). We also prove that for any \( c \geq 2 \), the decision problem corresponding to \( \gamma_{ct} \) is NP-hard for graphs with \( \chi(G) = c \).

Jinbo Li1, Guizhen Liu2
1College of Sciences, China University of Mining and Technology Xuzhou, P.R. China, 221116
2School of Mathematics, Shandong University Jinan, P.R. China, 250100
Abstract:

Let \( G(V, E) \) be a simple graph, and let \( f \) be an integer function defined on \( V \) with \( 1 \leq f(v) \leq d(v) \) for each vertex \( v \in V \). An \( f \)-edge covered colouring is an edge colouring \( C \) such that each colour appears at each vertex \( v \) at least \( f(v) \) times. The maximum number of colours needed to \( f \)-edge covered colour \( G \) is called the \( f \)-edge covered chromatic index of \( G \) and denoted by \( \chi_{fc}'(G) \). Any simple graph \( G \) has an \( f \)-edge covered chromatic index equal to \( \delta_f \) or \( \delta_f – 1 \), where \( \delta_f = \min \left\{\left\lfloor\frac{d(v)}{f(v)}\right\rfloor : v \in V(G)\right\} \). Let \( G \) be a connected and not complete graph with \( \chi_{fc}’ = \delta_f – 1 \). If for each \( u, v \in V \) and \( e = uv \notin E \), we have \( \chi_{fc}'(G+e) > \chi_{fc}'(G) \); then \( G \) is called an \( f \)-edge covered critical graph. In this paper, some properties of \( f \)-edge covered critical graphs are discussed. It is proved that if \( G \) is an \( f \)-edge covered critical graph, then for each \( u, v \in V \) and \( e = uv \notin E \) there exists \( w \in \{u, v\} \) with \( d(w) \leq \delta_f(f(w) + 1) – 2 \) such that \( w \) is adjacent to at least \( \max \left\{d(w) – \delta_f f(w) + 1, (f(w) + 2)d(w) – \delta_f(f(w) + 1)^2 + f(w) + 3\right\} \) vertices which are all \( \delta_f \)-vertices in \( G \).

Julian Allagan1, Mo Hendon2, Peter Johnson Jr. ¢3, David Slutzky1
1School of Science Technology Engineering and Mathematics, Gainesville State College, Watkinsville, GA – 30677, USA
2Department of Mathematics, University of Georgia, GA – 30602, USA
3Department of Mathematics and Statistics, Auburn University, AL – 36849, USA
Abstract:

We answer in the affirmative a question posed by Al-Addasi and Al-Ezeh in 2008 on the existence of symmetric diametrical bipartite graphs of diameter 4. Bipartite symmetric diametrical graphs are called \( S \)-graphs by some authors, and diametrical graphs have also been studied by other authors using different terminology, such as self-centered unique eccentric point graphs. We include a brief survey of some of this literature and note that the existence question was also answered by Berman and Kotzig in a 1980 paper, along with a study of different isomorphism classes of these graphs using a \( (1,-1) \)-matrix representation which includes the well-known Hadamard matrices. Our presentation focuses on a neighborhood characterization of \( S \)-graphs, and we conclude our survey with a beautiful version of this characterization known to Janakiraman.

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;