For a vertex \(v\) of a connected graph \(G\) and a subset \(S\) of \(V(G)\), the distance between \(v\) and \(S\) is \(d(v, S) = \min\{d(v,x) : x \in S\}\), where \(d(v,x)\) is the distance between \(v\) and \(x\). For an ordered \(k\)-partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) of \(V(G)\), the code of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(c_\Pi(v) = (d(v,S_1), d(v,S_2), \ldots, d(v, S_k))\). The \(k\)-partition \(\Pi\) is a resolving partition if the codes \(c_\Pi(v)\), \(v \in V(G)\), are distinct. A resolving partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) is acyclic if each subgraph \(\langle S_i \rangle\) induced by \(S_i\) (\(1 \leq i \leq k\)) is acyclic in \(G\). The minimum \(k\) for which there is a resolving acyclic \(k\)-partition of \(V(G)\) is the resolving acyclic number \(a_r(G)\) of \(G\). We study connected graphs with prescribed order, diameter, vertex-arboricity, and resolving acyclic number. It is shown that, for each triple \(d,k,n\) of integers with \(2 \leq d \leq n-2\) and \(3 \leq (n-d+1)/2 \leq k \leq n-d+1\), there exists a connected graph of order \(n\) having diameter \(d\) and resolving acyclic number \(k\). Also, for each pair \(a, b\) of integers with \(2 \leq a \leq b-1\), there exists a connected graph with resolving acyclic number \(a\) and vertex-arboricity \(b\). We present a sharp lower bound for the resolving acyclic number of a connected graph in terms of its clique number. The resolving acyclic number of the Cartesian product \(H \times K_2\) of nontrivial connected graph \(H\) and \(K_2\) is studied.

In this paper, we completely solve the problem of finding a maximum packing of any balanced complete multipartite graph \(K_{m}(n)\) with edge-disjoint \(6\)-cycles, and minimum leaves are explicitly given.

Subsequently, we also find a minimum covering of \(K_{m}(n)\).

Orthogonal designs and their special cases, such as weighing matrices and Hadamard matrices, have many applications in combinatorics, statistics, and coding theory, as well as in signal processing. In this paper, we generalize the definition of orthogonal designs, give many constructions for these designs, and prove some multiplication theorems that, most of them, can also be applied in the special case of orthogonal designs. Some necessary conditions for the existence of generalized orthogonal designs are also given.

We prove that the corona graphs \(C_n \circ K_1\) are \(k\)-equitable, as per Cahit’s definition of \(k\)-equitability, for \(k = 2, 3, 4, 5, 6\).

For a vertex \(v\) of a graph \(G = (V, E)\), the domination number \(\gamma(G)\) of \(G\) relative to \(v\) is the minimum cardinality of a dominating set in \(G\) that contains \(v\). The average domination number of \(G\) is \(\gamma_{av}(G) = \frac{1}{|V|} \sum_{v\in V} \gamma_v(G)\). The independent domination number \(i_v(G)\) of \(G\) relative to \(v\) is the minimum cardinality of a maximal independent set in \(G\) that contains \(v\). The average independent domination number of \(G\) is \(\gamma_{av}^i(G) = \frac{1}{|V|} \sum_{v\in V} i_v(G)\). In this paper, we show that a tree \(T\) satisfies \(\gamma_{av}(T) = i_{av}(T)\) if and only if \(A(T) = \vartheta\) or each vertex of \(A(T)\) has degree \(2\) in \(T\), where \(A(T)\) is the set of vertices of \(T\) that are contained in all its minimum dominating sets.

A graph \(G\) is \(K_r\)-covered if each vertex of \(G\) is contained in a clique \(K_r\). Let \(\gamma(G)\) and \(\gamma_t(G)\) respectively denote the domination and the total domination number of \(G\). We prove the following results for any graph \(G\) of order \(n\):

If \(G\) is \(K_6\)-covered, then \(\gamma_t(G) \leq \frac{n}{3}\),

If \(G\) is \(K_r\)-covered with \(r = 3\) or \(4\) and has no component isomorphic to \(K_r\), then \(\gamma_t(G) \leq \frac{2n}{r+1}\),

If \(G\) is \(K_3\)-covered and has no component isomorphic to \(K_3\), then \(\gamma(G) + \gamma_t(G) \leq \frac{7n}{9}\).

Corollaries of the last two results are that every claw-free graph of order \(n\) and minimum degree at least \(3\) satisfies \(\gamma_t(G) \leq \frac{n}{2}\) and \(\gamma(G) + \gamma(G) \leq \frac{7n}{9}\). For general values of \(r\), we give conjectures which would generalise the previous results. They are inspired by conjectures of Henning and Swart related to less classical parameters \(\gamma_{K_r}\) and \(\gamma^t_{K_r}\).

We are interested in linear-fractional transformations \(y,t\) satisfying the relations \(y^6=t^6 = 1\), with a view to studying an action of the subgroup \(H = \) on \({Q}(\sqrt{n}) \cup \{\infty\}\) by using coset diagrams.

For a fixed non-square positive integer \(n\), if an element \(\alpha = \frac{a+\sqrt {n}}{c}\) and its algebraic conjugate have different signs, then \(\alpha\) is called an ambiguous number. They play an important role in the study of action of the group \(H\) on \({Q}(\sqrt{n}) \cup \{\infty\}\). In the action of \(H\) on \({Q}(\sqrt{n}) \cup \{\infty\}\), \(\mathrm{Stab}_\alpha{(H)}\) are the only non-trivial stabilizers and in the orbit \(\alpha H\); there is only one (up to isomorphism). We classify all the ambiguous numbers in the orbit and use this information to see whether the action is transitive or not.

We are studying clique graphs of planar graphs, \(K(\text{Planar})\), this means the graphs which are the intersection of the clique family of some planar graph. In this paper, we characterize the \(K_3\) – free and \(K_4\) – free graphs which are in \(K(\text{Planar})\).

We show that a self-complementary vertex-transitive graph of order \(pq\), where \(p\) and \(q\) are distinct primes, is isomorphic to a circulant graph of order \(pq\). We will also show that if \(\Gamma\) is a self-complementary Cayley graph of the nonabelian group \(G\) of order \(pq\), then \(\Gamma\) and the complement of \(\Gamma\) are not isomorphic by a group automorphism of \(G\).

One of the most important problems of coding theory is to construct codes with the best possible minimum distance. The class of quasi-cyclic codes has proved to be a good source for such codes. In this paper, we use the algebraic structure of quasi-cyclic codes and the BCH type bound introduced in [17] to search for quasi-cyclic codes which improve the minimum distances of the best-known linear codes. We construct \(11\) new linear codes over \(\text{GF}(8)\) where \(3\) of these codes are one unit away from being optimal.

A graph \(G\) is said to be \(locally\) \(hamiltonian\) if the subgraph induced by the neighbourhood of every vertex is hamiltonian. Alabdullatif conjectured that every connected locally hamiltonian graph contains a spanning plane triangulation. We disprove the conjecture. At the end, we raise a problem about the nonexistence of spanning planar triangulation in a class of graphs.

Recently, Babson and Steingrimsson (see \([BS]\)) introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation.

In this paper we study the generating functions for the number of permutations on \(n\) letters avoiding a generalized pattern \(ab-c\) where \((a,b,c) \in S_3\), and containing a prescribed number of occurrences of a generalized pattern \(cd-e\) where \((c,d,e) \in S_3\). As a consequence, we derive all the previously known results for this kind of problem, as well as many new results.

Let \(G = (V,E)\) be a simple graph. For any real valued function \(f:V \to {R}\) and \(S \subset V\), let \(f(S) = \sum_{v\in S} f(u)\). A signed \(k\)-subdominating function is a function \(f: V \to \{-1,1\}\) such that \(f(N[v]) \geq 1\) for at least \(k\) vertices \(v \in V\). The signed \(k\)-subdomination number of a graph \(G\) is \(\gamma_{ks}^{-11}(G) = \min \{f(V) | f \text{ is a signed } k\text{-subdominating function on } G\}\). In this paper, we obtain lower bounds on this parameter and extend some results in other papers.

We give some relationships among the intersection numbers of a distance-regular graph \(\Gamma\) which contains a circuit \((u_1,u_2,u_3,u_4)\) with \(\partial(u_1,u_2) = 1\) and \(\partial(u_2,u_4) = 2\). As an application, we obtain an upper bound of the diameter of \(\Gamma\) when \(k \geq 2b_1\).

We extend results concerning orthogonal edge labeling of constant weight Gray codes. For positive integers \(n\) and \(r\) with \(n > r\), let \(G_{n,r}\) be the graph whose vertices are the \(r\)-sets of \(\{1, \ldots, n\}\), with \(r\)-sets adjacent if they intersect in \(r-1\) elements. The graph \(G_{n,r}\) is Hamiltonian; Hamiltonian cycles of \(G_{n,r}\) are early examples of error-correcting codes, where they came to be known as constant weight Gray codes.

An \(r\)-set \(A\) and a partition \(\pi\) of weight \(r\) are said to be orthogonal if every block of \(\pi\) meets \(A\) in exactly one element. Given a class \(P\) of weight \(r\) partitions of \(X_n\), one would like to know if there exists a \(G_{n,r}\) Hamiltonian cycle \(A_1 A_2 \ldots A_{\binom{n}{r}}\) whose edges admit a labeling \(A_1\pi_1 A_2 \ldots A_{\binom{n}{r}}\pi_{\binom{n}{r}}\) by distinct partitions from \(\mathcal{P}\), such that a partition label of an edge is orthogonal to the vertices that comprise the edge. The answer provides non-trivial information about Hamiltonian cycles in \(G_{n,r}\) and has application to questions pertaining to the efficient generation of finite semigroups.

Let \(r\) be a partition of \(m\) as a sum of \(r\) positive integers. We let \(r\) also refer to the set of all partitions of \(X_n\) whose block sizes comprise the partition \(r\). J. Lehel and the first author have conjectured that for \(n \geq 6\) and partition type \(\pi\) of \(\{1, \ldots, n\}\) of weight \(r\) partitions, there exists a \(r\)-labeled Hamiltonian cycle in \(G_{n,r}\).

In the present paper, for \(n = s + r\), we prove that there exist Hamiltonian cycles in \(G_{n,r}\) which admit orthogonal labelings by the partition types which have \(s\) blocks of size two and \(r – s\) blocks of size one, thereby extending a result of J. Lehel and the first author and completing the work on the conjecture for all partition types with blocks of size at most two.

For distinct vertices \(u\) and \(v\) of a nontrivial connected graph \(G\), the detour distance \(D(u,v)\) between \(u\) and \(v\) is the length of a longest \(u-v\) path in \(G\). For a vertex \(v \in V(G)\), define \(D^-(v) = \min\{D(u,v) : u \in V(G) – \{v\}\}\). A vertex \(u (\neq v)\) is called a detour neighbor of \(v\) if \(D(u,v) = D^-(v)\). A vertex \(v\) is said to detour dominate a vertex \(u\) if \(u = v\) or \(u\) is a detour neighbor of \(v\). A set \(S\) of vertices of \(G\) is called a detour dominating set if every vertex of \(G\) is detour dominated by some vertex in \(S\). A detour dominating set of \(G\) of minimum cardinality is a minimum detour dominating set and this cardinality is the detour domination number \(\gamma_D(G)\). We show that if \(G\) is a connected graph of order \(n \geq 3\), then \(\gamma_D(G) \leq n-2\). Moreover, for every pair \(k,n\) of integers with \(1 \leq k \leq n-2\), there exists a connected graph \(G\) of order \(n\) such that \(\gamma_D(G) = k\). It is also shown that for each pair \(a,b\) of positive integers, there is a connected graph \(G\) with domination number \(\gamma(G) = a\) and \(\gamma_D(G) = b\).

We let \(A(n)\) equal the number of \(n \times n\) alternating sign matrices. From the work of a variety of sources, we know that

\[A(n) = \prod\limits_{t=0}^{n-1} \frac{(3l+1)!}{(n+l)!}\]

We find an efficient method of determining \(ord_p(A(n))\), the highest power of \(p\) which divides \(A(n)\), for a given prime \(p\) and positive integer \(n\), which allows us to efficiently compute the prime factorization of \(A(n)\). We then use our method to show that for any nonnegative integer \(k\), and for any prime \(p > 3\), there are infinitely many positive integers \(n\) such that \(ord_p(A(n)) = k\). We show a similar but weaker theorem for the prime \(p = 3\), and note that the opposite is true for \(p = 2\).

We survey the status of minimal coverings of pairs with block sizes two, three, and four when \(\lambda = 1\), that is, all pairs from a \(v\)-set are covered exactly once. Then we provide a complete solution for the case \(\lambda = 2\).

We derive an alternative rule for generating uniform step magic squares. The compatibility conditions for the proposed rule are simpler than the analogous conditions for the classical uniform step rule. We exploit this fact to enumerate all uniform-step magic squares of every given odd order. Our main result states that if \(p = \prod_{i=1}^l q_i^{r_i}\) is the prime factorization of a positive odd number \(p\), then there exist \(\kappa(p) =\prod _{i=1}^l \kappa(q_i^{r_i})\) uniform step magic squares of order \(p\), where
\(\kappa (q_i^{r_i})=[\tau (q_i^{r_i})]^2-\lambda (q_i^{r_i}),\lambda(q_i^{r_i})=(q_i^{r_i}-q_i^{r_i-1})^2[2(q_i^{2r_i-1}+1)^2/(q_i+1)^2+q_i^{3r_i-1}(q_i^{r_i}-3q_i^{r_i-1})]\) and \(\tau (q_i^{r_i})=(q_i^{r_i}-q_i^{r_i-1})(q_i^{2r_i+1}-2q_i^{2r_i}-q_i^{2r_i-1}+2)/(q_i+1)\) for \(i=1,\ldots,l\)

We show that for a cubic graph on \(n\) nodes, the size of the dominating set found by the greedy algorithm is at most \(\frac{4}{9}n\), and that this bound is tight.

For a standard tableau \(T\) of shape \(\lambda \vdash n\), \(maj(T)\) is the sum of \(i\)’s such that \(i+1\) appears in a row strictly below that of \(i\) in \(T\). We consider the \(g\)-polynomial \(f^\lambda(q) = \sum_\tau q^{ maj(T)}\), which appears in many contexts: as a dimension of an irreducible representation of finite general linear group, as a special case of Kostka-Foulkes polynomials, and so on. In this article, we try to understand `maj’ on a standard tableau \(T\) in relation to `inv’ on a multiset permutation (or a permutation of type \(\lambda\)). We construct an injective map from the set of standard tableaux to the set of permutations of type \(\lambda\) (increasing in each block) such that the `maj’ of the tableau is the `maj’ of the corresponding permutation when \(\lambda\) is a two-part partition. We believe that this helps to understand irreducible unipotent representations of finite general linear groups.

Many results about outer-embeddings (graphs having all their vertices in the same face) have been obtained recently in topological graph theory in recent times. In this paper, we deal with some difficulties appearing in the study of such embeddings. Particularly, we propose several problems concerning outer-embeddings in pseudosurfaces and we prove that two of them are NP-complete.

We also describe some properties about lists of forbidden minors for outer-embeddings in certain kinds of pseudosurfaces.