We study the spectral radius of graphs with \(n\) vertices and a \(k\)-vertex cut and describe the graph which has the maximal spectral radius in this class. We also discuss the limit point of the maximal spectral radius.

Consider lattice paths in \(\mathbb{Z}^2\) taking unit steps north (N) and east (E). Fix positive integers \(r,s\) and put an equivalence relation on points of \(\mathbb{Z}^2\) by letting \(v,w\) be equivalent if \(v-w = \ell(r,s)\) for some \(k \in \mathbb{Z}\). Call a lattice path \({valid}\) if whenever it enters a point \(v\) with an E-step, then any further points of the path in the equivalence class of \(v\) are also entered with an E-step. Loehr and Warrington conjectured that the number of valid paths from \((0,0)\) to \((nr,ns)\) is \({\binom{r+s}{nr}}^n\). We prove this conjecture when \(s=2\).

Given integers \(m \geq 2, r \geq 2\), let \(q_m(n), q_0^{(m)}(n), b_r^{(m)}(n)\) denote respectively the number of \(m\)-colored partitions of \(n\) into: distinct parts, distinct odd parts, and parts not divisible by \(r\).We obtain recurrences for each of the above-mentioned types of partition functions.

A reflection of a regular map on a Riemann surface fixes some simple closed curves, which are called \({mirrors}\). Each mirror passes through some of the geometric points (vertices, face-centers and edge-centers) of the map such that these points form a periodic sequence which we call the \({pattern}\) of the mirror. For every mirror there exist two particular conformal automorphisms of the map that fix the mirror setwise and rotate it in opposite directions. We call these automorphisms the \({rotary\; automorphisms}\) of the mirror. In this paper, we first introduce the notion of pattern and then describe the patterns of mirrors on surfaces. We also determine the rotary automorphisms of mirrors. Finally, we give some necessary conditions under which all reflections of a regular map are conjugate.

We prove the non-existence of maximal partial spreads of size \(76\) in \(\text{PG}(3,9)\). Relying on the classification of the minimal blocking sets of size 15 in \(\text{PG}(2,9)\) \([22]\), we show that there are only two possibilities for the set of holes of such a maximal partial spread. The weight argument of Blokhuis and Metsch \([3]\) then shows that these sets cannot be the set of holes of a maximal partial spread of size \(76\). In \([17]\), the non-existence of maximal partial spreads of size \(75\) in \(\text{PG}(3,9)\) is proven. This altogether proves that the largest maximal partial spreads, different from a spread, in \(\text{PG}(3,q = 9)\) have size \(q^2 – q + 2 = 74\).

A weakly connected dominating set \(W\) of a graph \(G\) is a dominating set such that the subgraph consisting of \(V(G)\) and all edges incident on vertices in \(W\) is connected. In this paper, we generalize it to \([r, R]\)-dominating set which means a distance \(r\)-dominating set that can be connected by adding paths with length within \(R\). We present an algorithm for finding \([r, R]\)-dominating set with performance ratio not exceeding \(ln \Delta_r + \lceil \frac{2r+1}{R}\rceil – 1\), where \(\Delta_r\) is the maximum number of vertices that are at distance at most \(r\) from a vertex in the graph. The bound for size of minimum \([r, R]\)-dominating set is also obtained.

For \(n \in \mathbb{N}\), let \(a_n\) count the number of ternary strings of length \(n\) that contain no consecutive \(1\)s. We find that \(a_n = \left(\frac{1}{2}+\frac{\sqrt{3}}{3}\right)\left(1 + \sqrt{3}\right)^n – \left(\frac{1}{2}-\frac{\sqrt{3}}{3}\right)\left(1 – \sqrt{3}\right)^n\). For a given \(n \geq 0\), we then determine the following for these \(a_n\) ternary strings:
(1)the number of \(0’\)s, \(1’\)s, and \(2’\)s;(2)the number of runs;(3) the number of rises, levels, and descents; and
(4)the sum obtained when these strings are considered as base \(3\) integers.

Following this, we consider the special case for those ternary strings (among the \(a_n\) strings we first considered) that are palindromes, and determine formulas comparable to those in (1) – (4) above for this special case.

Topological indices of nanotubes are numerical descriptors that are derived from the graph of chemical compounds. Such indices, based on the distances in the graph, are widely used for establishing relationships between the structure of nanotubes and their physico-chemical properties. The Szeged index is obtained as a bond additive quantity, where bond contributions are given as the product of the number of atoms closer to each of the two end points of each bond. In this paper, we find an exact expression for the Szeged index of an armchair polyhex nanotube \((TUAC_6{[p,k]}\)).

It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS(\(p, q, \lambda, \delta\)) graph as a connected, separable graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers \((a, b, c, d)\) is called CS(\(p, q, A, 5\)) realizable if there is a CS(\(p, q, \lambda, \delta\)) graph with \(p = a, q = b, \lambda = c\) and \(\delta= d\). Necessary and sufficient conditions for a quadruple to be CS(\(p, q,\lambda, \delta\)) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta), (p, q, \lambda, \Delta), (p, q, \delta, \Delta), (p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(A\) denotes the maximum degree for all points in a graph and \(\lambda\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa), (p, q, \lambda), (p, q, \delta), (p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.

We use \(k\)-trees to generalize the sequence of Motzkin numbers and show that Baxter’s generalization of Temperley-Lieb operators is a special case of our generalization of Motzkin numbers. We also obtain a recursive summation formula for the terms of \(3\)-Motzkin numbers and investigate some asymptotic properties of the terms of \(k\)-Motzkin numbers.

In this article, defining the matrix extensions of the Fibonacci and Lucas numbers, we start a new approach to derive formulas for some integer numbers which have appeared, often surprisingly, as answers to intricate problems, in conventional and in recreational Mathematics. Our approach provides a new way of looking at integer sequences from the perspective of matrix algebra, showing how several of these integer sequences relate to each other.

For a finite group \(G\) the commutativity degree,

\[d(G)=\frac{|\{(x,y)|x,y \in G, xy=yx\}|}{|G|^2}\]

is defined and studied by several authors and when \(d(G) \geq \frac{1}{2}\) it is proved by P. Lescot in 1995 that \(G\) is abelian , or \(\frac{G}{Z(G)}\) is elementary abelian with \(|G’| = 2\), or \(G\) is isoclinic with \(S_3\) and \(d(G) = 1\). The case when \(d(G) < \frac{1}{2}\) is of interest to study. In this paper we study certain infinite classes of finite groups and give explicit formulas for \(d(G)\). In some cases the groups satisfy \(\frac{1}{4} < d(G) < \frac{1}{2}\). Some of the groups under study are nilpotent of high nilpotency classes.

In this paper, we construct a new infinite family of balanced binary sequences of length \(N = 4p\), \(p \equiv 5 \pmod{8}\) with optimal autocorrelation magnitude \(\{N, 0, \pm 4\}\).

The cocircuits of a splitting matroid \(M_{i,j}\) are described in terms of the cocircuits of the original matroid \(M\).

Let \(G\) be a graph with vertex set \(V(G)\) and let \(f\) be a nonnegative integer-valued function defined on \(V(G)\). A spanning subgraph \(F\) of \(G\) is called an \(f\)-factor if \(d_F(x) = f(x)\) for every \(x \in V(F)\). In this paper, we present some sufficient conditions for the existence of \(f\)-factors and connected \((f-2, f)\)-factors in \(K_{1,n}\)-free graphs. The conditions involve the minimum degree, the stability number, and the connectivity of graph \(G\).

We classify the minimal blocking sets of size 15 in \(\mathrm{PG}(2,9)\). We show that the only examples are the projective triangle and the sporadic example arising from the secants to the unique complete 6-arc in \(\mathrm{PG}(2,9)\). This classification was used to solve the open problem of the existence of maximal partial spreads of size 76 in \(\mathrm{PG}(3,9)\). No such maximal partial spreads exist \([13]\). In \([14]\), also the non-existence of maximal partial spreads of size 75 in \(\mathrm{PG}(3,9)\) has been proven. So, the result presented here contributes to the proof that the largest maximal partial spreads in \(\mathrm{PG}(3,q=9)\) have size \(q^2-q+2=74\).

Our work in this paper is concerned with a new kind of fuzzy ideal of a \(K\)-algebra called an \((\in, \in \vee_q)\)-fuzzy ideal. We investigate some interesting properties of \((\in, \in \vee_q)\)-fuzzy ideals of \(K\)-algebras. We study fuzzy ideals with thresholds which is a generalization of both fuzzy ideals and \((\in, \in \vee_q)\)-fuzzy ideals. We also present characterization theorems of implication-based fuzzy ideals.

Let \(G\) be a digraph. For two vertices \(u\) and \(v\) in \(G\), the distance \(d(u,v)\) from \(u\) to \(v\) in \(G\) is the length of the shortest directed path from \(u\) to \(v\). The eccentricity \(e(v)\) of \(v\) is the maximum distance of \(v\) to any other vertex of \(G\). A vertex \(u\) is an eccentric vertex of \(v\) if the distance from \(v\) to \(u\) is equal to the eccentricity of \(v\). The eccentric digraph \(ED(G)\) of \(G\) is the digraph that has the same vertex set as \(G\) and the arc set defined by: there is an arc from \(u\) to \(v\) if and only if \(v\) is an eccentric vertex of \(u\). In this paper, we determine the eccentric digraphs of digraphs for various families of digraphs and we get some new results on the eccentric digraphs of the digraphs.

We present \(3\) open challenges in the field of Costas arrays. They are: a) the determination of the number of dots on the main diagonal of a Welch array, and especially the maximal such number for a Welch array of a given order; b) the conjecture that the fraction of Welch arrays without dots on the main diagonal behaves asymptotically as the fraction of permutations without fixed points and hence approaches \(1/e\) and c) the determination of the parity populations of Golomb arrays generated in fields of characteristic \(2\).

Let \(G\) be the graph obtained from \(K_{3,3}\) by deleting an edge. We find a list assignment with \(|L(v)| = 2\) for each vertex \(v\) of \(G\), such that \(G\) is uniquely \(L\)-colorable, and show that for any list assignment \(L’\) of \(G\), if \(|Z'(v)| \geq 2\) for all \(v \in V(G)\) and there exists a vertex \(v_0\) with \(|L'(v_0)| > 2\), then \(G\) is not uniquely \(L’\)-colorable. However, \(G\) is not \(2\)-choosable. This disproves a conjecture of Akbari, Mirrokni, and Sadjad (Problem \(404\) in Discrete Math. \(266(2003) 441-451)\).

A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. In this note, we show that the vertex set of every graph with minimum degree at least two and with no component that is a \(5\)-cycle can be partitioned into a dominating set and a total dominating set.

Let \(G\) be an undirected graph, \(A\) be an (additive) Abelian group and \(A^* = A – \{0\}\). A graph \(G\) is \(A\)-connected if \(G\) has an orientation such that for every function \(b: V(G) \longmapsto A\) satisfying \(\sum_{v\in V(G)} b(v) = 0\), there is a function \(f: E(G) \longmapsto A^*\) such that at each vertex \(v\in V(G)\) the net flow out of \(v\) equals \(b(v)\). We investigate the group connectivity number \(\Lambda_g(G) = \min\{n; G \text{ is } A\text{-connected for every Abelian group with } |A| \geq n\}\) for complete bipartite graphs, chordal graphs, and biwheels.

Various enumeration problems for classes of simply generated families of trees have been the object of investigation in the past. We mention the enumeration of independent subsets, connected subsets or matchings for instance. The aim of this paper is to show how combinatorial problems of this type can also be solved for rooted trees and trees, which enables us to take better account of isomorphisms. As an example, we will determine the average number of independent vertex subsets of trees and binary rooted trees (every node has outdegree \(\leq 2\)).

In this paper, first we introduce the concept of a \({connected}\) graph homomorphism as a homomorphism for which the inverse image of any edge is either empty or a connected graph, and then we concentrate on chromatically connected (resp. chromatically disconnected) graphs such as \(G\) for which any \(\chi(G)\)-colouring is a connected (resp. disconnected) homomorphism to \(K_{\chi(G)}\).

In this regard, we consider the relationships of the new concept to some other notions as uniquely-colourability. Also, we specify some classes of chromatically disconnected graphs such as Kneser graphs \(KG(m,n)\) for which \(m\) is sufficiently larger than \(n\), and the line graphs of non-complete class II graphs.

Moreover, we prove that the existence problem for connected homomorphisms to any fixed complete graph is an NP-complete problem.

We show that every \(2\)-connected cubic graph of order \(n > 8\) admits a \(P_3\)-packing of at least \(\frac{9n}{11}n\) vertices. The proof is constructive, implying an \(O(M(n))\) time algorithm for constructing such a packing, where \(M(n)\) is the time complexity of the perfect matching problem for \(2\)-connected cubic graphs.

The locally twisted cube \(LTQ_n\) is a newly introduced interconnection network for parallel computing. As a variant of the hypercube \(Q_n\), \(LTQ_n\) has better properties than \(Q_n\) with the same number of links and processors. Yang, Megson and Evans Evans [Locally twisted cubes are \(4\)-pancyclic, Applied Mathematics Letters, \(17 (2004), 919-925]\) showed that \(LTQ_n\) contains a cycle of every length from \(4\) to \(2^n\). In this note, we improve this result by showing that every edge of \(LTQ_n\) lies on a cycle of every length from \(4\) to \(2^n\) inclusive.

Necessary and sufficient conditions are given for the existence of a \((K_3 + e, \lambda)\)-group divisible design of type \(g^tu^1\).

A \(\lambda\)-design on \(v\) points is a set of \(v\) subsets (blocks) of a \(v\)-set such that any two distinct blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that all \(4\)-designs can be obtained from symmetric designs by a complementation procedure. In this paper, we establish feasibility criteria for the existence of \(\lambda\)-designs with two block sizes in the form of integrality conditions, equations, inequalities, and Diophantine equations involving various parameters of the designs. We use these criteria and a computer to prove that the \(\lambda\)-design conjecture is true for all \(\lambda\)-designs with two block sizes with \(v \leq 90\) and \(\lambda \neq 45\).

In this paper, we consider the relationships between the sums of the Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.

We define extended orthogonal sets of \(d\)-cubes and show that they are equivalent to a class of orthogonal arrays, to geometric nets and a class of codes. As a corollary, an upper bound for the maximal number of \(d\)-cubes in an orthogonal set is obtained.

For two given graphs \(G_1\) and \(G_2\), the \({Ramsey\; number}\) \(R(G_1, G_2)\) is the smallest integer \(n\) such that for any graph \(G\) of order \(n\), either \(G\) contains \(G_1\) or the complement of \(G\) contains \(G_2\). Let \(P_n\) denote a path of order \(n\) and \(W_{m}\) a wheel of order \(m+1\). Chen et al. determined all values of \(R(P_n, W_{m})\) for \(n \geq m-1\). In this paper, we establish the best possible upper bound and determine some exact values for \(R(P_n, W_{m})\) with \(n \leq m-2\).

A container \(C(x,y)\) is a set of vertex-disjoint paths between vertices \(z\) and \(y\) in a graph \(G\). The width \(w(C(x,y))\) and length \(L(C(x,y))\) are defined to be \(|C(x,y)|\) and the length of the longest path in \(C(x,y)\) respectively. The \(w\)-wide distance \(d_w(x,y)\) between \(x\) and \(y\) is the minimum of \(L(C(x,y))\) for all containers \(C(x,y)\) with width \(w\). The \(w\)-wide diameter \(d_w(G)\) of \(G\) is the maximum of \(d_w(x,y)\) among all pairs of vertices \(x,y\) in \(G\), \(x \neq y\). In this paper, we investigate some problems on the relations between \(d_w(G)\) and diameter \(d(G)\) which were raised by D.F. Hsu \([1]\). Some results about graph equation of \(d_w(G)\) are proved.

Greedy defining sets have been studied for the first time by the author for graphs. In this paper, we consider greedy defining sets for Latin squares and study the structure of these sets in Latin squares. We give a general bound for greedy defining numbers and linear bounds for greedy defining numbers of some infinite families of Latin squares. Greedy defining sets of circulant Latin squares are also discussed in the paper.