Let \(T_n\) denote a complete binary tree of depth \(n\). Each internal node \(v\) of \(T_n\) has two children denoted by \(\text{left}(v)\) and \(\text{right}(v)\). Let \(f\) be a function mapping each internal node \(v\) to \(\{\text{left}(v), \text{right}(v)\}\). This naturally defines a path from the root, \(\lambda\), of \(T_n\) to one of its leaves given by

\[\lambda, f(\lambda), f^2(\lambda), \ldots f^n(\lambda).\]

We consider the problem of finding this path via a deterministic algorithm that probes the values of \(f\) in parallel. We show that any algorithm that probes \(k\) values of \(f\) in one round requires \(\frac{n}{\lfloor \log(k+1) \rfloor}\) rounds in the worst case. This indicates that the amount of information that can be extracted in parallel is, at times, strictly less than the amount of information that can be extracted sequentially.

A graph \(G\) is edge-\(L\)-colorable, if for a given edge assignment \(L = \{L(e) : e \in E(G)\}\), there exists a proper edge-coloring \(\phi\) of \(G\) such that \(\phi(e) \in L(e)\) for all \(e \in E(G)\). If \(G\) is edge-\(L\)-colorable for every edge assignment \(L\) with \(|L(e)| \geq k\) for \(e \in E(G)\), then \(G\) is said to be edge-\(k\)-choosable. In this paper, we prove that if \(G\) is a planar graph without chordal \(7\)-cycles, then \(G\) is edge-\(k\)-choosable, where \(k = \max\{8, \Delta(G) + 1\}\).

In this note, we study some properties of the composition operator \(C_\varphi\) on the Fock space \(\mathcal{F}_X^2\) of \(X\)-valued analytic functions in \(\mathbb{C}\). We give a necessary and sufficient condition for a bounded operator on \(\mathcal{F}_X^2\) to be a composition operator and for the adjoint operator of a composition operator to be also a composition operator on \(\mathcal{F}_X^2\). We also give characterizations of normal, unitary, and co-isometric composition operators on \(\mathcal{F}_X^2\).

The competition hypergraph \(C\mathcal{H}(D)\) of a digraph \(D\) is the hypergraph such that the vertex set is the same as \(D\) and \(e \subseteq V(D)\) is a hyperedge if and only if \(e\) contains at least \(2\) vertices and \(e\) coincides with the in-neighborhood of some vertex \(v\) in the digraph \(D\). Any hypergraph with sufficiently many isolated vertices is the competition hypergraph of an acyclic digraph. The hypercompetition number \(hk(\mathcal{H})\) of a hypergraph \(\mathcal{H}\) is defined to be the smallest number of such isolated vertices.

In this paper, we study the hypercompetition numbers of hypergraphs. First, we give two lower bounds for the hypercompetition numbers which hold for any hypergraphs. And then, by using these results, we give the exact hypercompetition numbers for some family of uniform hypergraphs. In particular, we give the exact value of the hypercompetition number of a connected graph.

In this paper, we study the signed and minus total domination problems for two subclasses of bipartite graphs: biconvex bipartite graphs and planar bipartite graphs. We present a unified method to solve the signed and minus total domination problems for biconvex bipartite graphs in \(O(n + m)\) time. We also prove that the decision problem corresponding to the signed (respectively, minus) total domination problem is NP-complete for planar bipartite graphs of maximum degree \(3\) (respectively, maximum degree \(4\)).

The edge versions of Wiener index, which were based on distance between two edges in a connected graph \(G\), were introduced by Iranmanesh et al. in \(2008\). In this paper, we find the edge Wiener indices of the sum of graphs. Then as an application of our results, we find the edge Wiener indices of graphene, \(C_4\)-nanotubes and \(C_4\)-nanotori.

Let \(\kappa(G)\) be the connectivity of \(G\) and \(G \times H\) the direct product of \(G\) and \(H\). We prove that for any graphs \(G\) and \(K\), with \(n \geq 3\),\(\kappa(G \times K_n) = \min\{n\kappa(G), (n-1)\delta(G)\},\) which was conjectured by Guji and Vumar.

The main aim of this paper is to construct an extension of Appell’s hypergeometric functions by means of modified Beta functions \(B(x, y; p)\). We give integral representations for these functions and obtain some relations for these functions and extended Gauss hypergeometric function via decomposition operators defined by Burchnall and Chaundy. Furthermore, we present some transformation formulas for the first and second kind of extended Appell’s hypergeometric functions. Also, we give some relations between the first kind of extended Appell’s hypergeometric functions, Whittaker, and Modified Bessel functions.

Informally, a \(\epsilon\)-switchable \(G\)-design is a decomposition of the complete graph into subgraphs of isomorphic copies of \(G\) which have the property that they remain a \(G\)-decomposition when \(\epsilon\)-edge switches are made to the subgraphs. This paper determines the spectrum of \(\epsilon\)-switchable \(G\)-designs where \(G\) is a kite (a triangle with an edge attached) and \(\epsilon\) takes \(t\)-edge, \(h\)-edge, and \(l\)-edge.

In this paper, we use a simple method to derive different recurrence relations on the Tribonacci numbers and their sums. By using the companion matrices and generating matrices, we obtain more identities on the Tribonacci numbers and their sums, which are more general than those given in the literature [E. Kilic, Tribonacci Sequences with Certain Indices and Their Sum, Ats Combinatoria \(86 (2008),13-22]\).

A \((2,1)\)-total labeling of a graph \(G\) is a labeling of vertices and edges, such that:(1) any two adjacent vertices of \(G\) receive distinct integers,(2) any two adjacent edges receive distinct integers, and (3) a vertex and its incident edges receive integers that differ by at least 2 in absolute value.The span of a \((2,1)\)-total labeling is the difference between the maximum label and the minimum label.We note the minimum span \(\lambda_2^T(G)\).In this paper, we prove that if \(G\) is a planar graph with \(\Delta \leq 3\) and girth \(g \geq 18\), then \(\lambda_2^T(G) \leq 5\). If \(G\) is a planar graph with \(\Delta \leq 4\) and girth \(g \geq 12\), then \(\lambda_2^T(G) \leq 7\).

If \(X\) is a geodesic metric space and \(x_1, x_2, x_3 \in X\), a geodesic triangle \(T = \{x_1, x_2, x_3\}\) is the union of the three geodesics \([x_1 x_2], [x_2 x_3]\) and \([x_3 x_1]\) in \(X\). The space \(X\) is \(\delta\)-hyperbolic (in the Gromov sense) if any side of \(T\) is contained in a \(\delta\)-neighborhood of the union of the two other sides, for every geodesic triangle \(T\) in \(X\). We denote by \(\delta(X)\) the sharp hyperbolicity constant of \(X\), i.e. \(\delta(X) := \inf\{\delta \geq 0: X \text{ is } \delta\text{-hyperbolic}\}\). In this paper, we find some relations between the hyperbolicity constant of a graph and its order, girth, cycles, and edges. In particular, if \(g\) denotes the girth, we prove \(\delta(G) \geq g(G)/4\) for every (finite or infinite) graph; if \(G\) is a graph of order \(n\) and edges with length \(k\) (possibly with loops and multiple edges), then \(\delta(G) \leq nk/4\). We find a large family of graphs for which the first (non-strict) inequality is in fact an equality; besides, we characterize the set of graphs with \(\delta(G) = nk/4\). Furthermore, we characterize the graphs with edges of length \(k\) with \(\delta(G) < k\).

A proper edge coloring \(c\) of a graph \(G\) is said to be acyclic if \(G\) has no bicolored cycle with respect to \(c\). It is proved that every triangle-free toroidal graph \(G\) admits an acyclic edge coloring with \((\Delta(G) + 5)\) colors. This generalizes a theorem from \([8]\).

Let \(\mathcal{J}_n\) be the set of tricyclic graphs of order \(n\). In this paper, we use a new proof to determine the unique graph with maximal spectral radius among all graphs in \(\mathcal{J}_n\) for each \(n \geq 4\). Also, we determine the unique graph with minimal least eigenvalue among all graphs in this class for each \(n \geq 52\). We can observe that the graph with maximal spectral radius is not the same as the one with minimal least eigenvalue in \(\mathcal{J}_n\), which is different from those on the unicyclic and bicyclic graphs.

Let \(G\) be a connected simple graph. The hyper-Wiener index \(WW(G)\) is defined as \(WW(G) = \sum_{u,v \in V(G)} (d(u, v) + d^2(u,v)),\) with the summation going over all pairs of vertices in \(G\). In this paper, we determine the extremal unicyclic graphs with given matching number and minimal hyper-Wiener index.

Robertson \(([5])\) and independently, Bondy \(([1])\) proved that the generalized Petersen graph \(P(n, 2)\) is non-hamiltonian if \(n \equiv 5 \pmod{6}\), while Thomason \([7]\) proved that it has precisely \(3\) hamiltonian cycles if \(n \equiv 3 \pmod{6}\). The hamiltonian cycles in the remaining generalized Petersen graphs were enumerated by Schwenk \([6]\). In this note we give a short unified proof of these results using Grinberg’s theorem.

Let \(v \equiv k-1, 0, \text{ or } 1 \pmod{k}\). An \(\text{RMP}(k, \lambda, v)\) (resp. \(\text{RMC}(k, \lambda, v)\)) is a resolvable packing (resp. covering) with maximum (resp. minimum) possible number \(m(v)\) of parallel classes which are mutually distinct, each parallel class consists of \(\left\lfloor \frac{v – k + 1}{k} \right\rfloor\) blocks of size \(k\) and one block of size \(v – k \left\lfloor \frac{v – k + 1}{k} \right\rfloor\), and its leave (resp. excess) is a simple graph. Such designs were first introduced by Fang and Yin. They have proved that these designs can be used to construct certain uniform designs which have been widely applied in industry, system engineering, pharmaceutics, and natural science. In this paper, direct and recursive constructions are discussed for such designs. The existence of an \(\text{RMP}(3, 3, v)\) and an \(\text{RMC}(3, 3, v)\) is proved for any admissible \(v\).

A digraph \(D\) is said to be \({super-mixed-connected}\) if every minimum general cut of \(D\) is a local cut. In this paper, we characterize non-super-mixed-connected line digraphs. As a consequence, if \(D\) is a super-arc-connected digraph with \(\delta(D) \geq 3\), then the \(n\)-th iterated line digraph of \(D\) is super-mixed-connected for any positive integer \(n\). In particular, the Kautz network \(K(d,n)\) is super-mixed-connected for \(d \neq 2\), and the de Bruijn network \(B(d,n)\) is always super-mixed-connected.

Let \(G\) be an even degree multigraph and let \(deg(v)\) and \(p(uv, G)\) denote the degree of vertex \(v\) in \(G\) and the multiplicity of edge \((u, v)\) respectively in \(G\). A decomposition of \(G\) into multigraphs \(G_1\) and \(G_2\) is said to be a \({well-spread \;halving}\) of \(G\) into two halves \(G_1\) and \(G_2\), if for each vertex \(v\), \(deg(v, G_1) = deg(v, G_2) = \frac{1}{2}deg(v, G)\), and \(|\mu(uv, G_1) – \mu(uv, G_2)| \leq 1\) for each edge \((u,v) \in E(G)\). A sufficient condition was given in \([7]\) under which there exists a well-spread halving of \(G\) if we allow the addition/removal of a Hamilton cycle to/from \(G\). Analogous to \([7]\), in this paper we define a well-spread halving of a directed multigraph \(D\) and give a sufficient condition under which there exists a well-spread halving of \(D\) if we allow the addition/removal of a particular type of Hamilton cycle to/from \(D\).

In this paper, we study linear transformations preserving log-convexity, when the triangular array satisfies some ordinary convolution. As applications, we show that the Stirling transformations of two kinds, the Lah transformation, the generalized Stirling transformation of the second kind, and the Dowling transformations of two kinds preserve the log-convexity.

For \(r \geq 3\), a \({clique-extension}\) of order \(r + 1\) is a connected graph that consists of a \(K_r\), plus another vertex adjacent to at most \(r – 1\) vertices of \(K_r\). In this paper, we consider the problem of finding the smallest number \(t\) such that any graph \(G\) of order \(n\) admits a decomposition into edge-disjoint copies of a fixed graph \(H\) and single edges with at most \(\tau\) elements. Here, we solve the case when \(H\) is a fixed clique-extension of order \(r + 1\), for all \(r \geq 3\), and will also obtain all extremal graphs. This work extends results proved by Bollobás [Math. Proc. Cambridge Philos. Soc. \(79 (1976) 19-24]\) for cliques.

A path in an edge-coloring graph \(G\), where adjacent edges may be colored the same, is called a \({rainbow\; path}\) if no two edges of \(G\) are colored the same. A nontrivial connected graph \(G\) is \({rainbow\; connected}\) if for any two vertices of \(G\) there is a rainbow path connecting them. The \({rainbow\; connection \;number}\) of \(G\), denoted \(\text{rc}(G)\), is defined as the minimum number of colors by using which there is coloring such that \(G\) is rainbow connected. In this paper, we study the rainbow connection numbers of line graphs of triangle-free graphs, and particularly, of \(2\)-connected triangle-free graphs according to their ear decompositions.

A construction based on Legendre sequences is presented for a doubly-extended binary linear code of length \(2p + 2\) and dimension \(p + 1\). This code has a double circulant structure. For \(p = 4k + 3\), we obtain a doubly-even self-dual code. Another construction is given for a class of triply extended rate \(1/3\) codes of length \(3p + 3\) and dimension \(p + 1\). For \(p = 4k + 1\), these codes are doubly-even self-orthogonal.

A cograph is a \(P_4\)-free graph. We first give a short proof of the fact that \(0\) (\(-1\)) belongs to the spectrum of a connected cograph (with at least two vertices) if and only if it contains duplicate (resp. coduplicate) vertices. As a consequence, we next prove that the polynomial reconstruction of graphs whose vertex-deleted subgraphs have the second largest eigenvalue not exceeding \(\frac{\sqrt{5}-1}{2}\) is unique.

In this paper, we describe Cayley graphs of rectangular bands and normal bands, which are the strong semilattice of rectangular bands, respectively. In particular, we give the structure of Cayley graphs of rectangular bands and normal bands, and we determine which graphs are Cayley graphs of rectangular bands and normal bands.

The generalized Petersen graph \(P(n, k)\) is the graph whose vertex set is \(U \cup W\), where \(U = \{u_0, u_1, \ldots, u_{n-1}\}\), \(W = \{v_0, v_1, \ldots, v_{n-1}\}\); and whose edge set is \(\{u_iu_{i+1},u_iv_{i}, v_iv_{i+k} \mid i = 0, 1, \ldots, n-1\}\), where \(n, k\) are positive integers, addition is modulo \(n\), and \(2 < k < n/2\). G. Exoo, F. Harary, and J. Kabell have determined the crossing number of \(P(n, 2)\); Richter and Salazar have determined the crossing number of the generalized Petersen graph \(P(n, 3)\). In this paper, the crossing number of the generalized Petersen graph \(P(3k, k)\) (\(k \geq 4\)) is studied, and it is proved that \(\text{cr}(P(3k,k)) = k\) (\(k \geq 4\)).

In this paper, we apply the concept of fundamental relation on \(\Gamma\)-hyperrings and obtain some related results. Specially, we show that there is a covariant functor between the category of \(\Gamma\)-hyperrings and the category of fundamental \(\Gamma’/\beta^*\)-rings.

The Merrifield-Simmons index \(\sigma(G)\) of a (molecular) graph \(G\) is defined as the number of independent-vertex sets of \(G\). By \(G(n, l, k)\) we denote the set of unicyclic graphs with girth \(l\) and the number of pendent vertices being \(k\) respectively. Let \(S_n^l\) be the graph obtained by identifying the center of the star \(S_{n-l+1}\) with any vertex of \(C_l\). By \(S^{l,k}_n*\) we denote the graph obtained by identifying one pendent vertex of the path \(P_{n-l-k+1}\) with one pendent vertex of \(S_{l+k}^l\). In this paper, we first investigate the Merrifield-Simmons index for all unicyclic graphs in \(G(n,l,k)\) and \(S^{l,k}_n*\) is shown to be the unique unicyclic graph with maximum Merrifield-Simmons index among all unicyclic graphs in \(G(n, l, k)\) for fixed \(l\) and \(k\). Moreover, we proved that:

1. When \(k = n – 3\), \(S^{3,k}_n\) has the maximum Merrifield-Simmons index among all graphs in \(G(n, k)\); When \(k = 1, n-4\), \(S^{4,k}_n\) or \(S^{n-k,k}_n\) has the maximum Merrifield-Simmons index among all graphs in \(G(n,k)\)
2. When \(2 \leq k \leq n-5\), \(S^{n-k,k}_n\) and \(S^{4,k}_n\) are respectively unicyclic graphs having maximum and second-maximum Merrifield-Simmons indices among all unicyclic graphs in \(G(n, k)\), where \(G(n, k)\) denotes the set of unicyclic graphs with \(n\) vertices and \(k\) pendent vertices.

In this paper, we give a complete solution to the Hamilton-Waterloo problem for the case of Hamilton cycles and \(C_{4k}\)-factors for all positive integers \(k\).

In this paper, we study the edge deletion preserving the diameter of the Johnson graph \(J(n,k)\). Let \(un^-(G)\) be the maximum number of edges of a graph \(G\) whose removal maintains its diameter. For Johnson graph \(J(n,k)\), we give upper and lower bounds to the number \(un^-(J(n,k))\), namely:\(\binom{k}{2}\binom{n}{k+1} \leq un^-(J(n,k)) \leq \binom{k+1}{2} \binom{n}{k+1} + \lceil(1+\frac{1}{2k})(\binom{n}{k} – 1\rceil,\) for \(n \geq 2k \geq 2\).

In this paper, we study the global behavior of the nonnegative equilibrium points of the difference equation

\[x_{n+1} = \frac{ax_{n-k}}{bcx_{n-k}^rx_{n-(2k+1)}^s}, \quad n=0,1,\ldots\]

where \(a, b, c, d, e\) are nonnegative parameters, initial conditions are nonnegative real numbers, \(k\) is a nonnegative integer, and \(r, s \geq 1\).

Let \(\mathcal{I}_X\) be the symmetric inverse semigroup on a finite nonempty set \(X\), and let \(A\) be a subset of \(\mathcal{I}^*_X = \mathcal{I}_X \setminus \{0\}\). Let \(\text{Cay}(\mathcal{I}^*_X, A)\) be the graph obtained by deleting vertex \(0\) from the Cayley graph \(\text{Cay}(\mathcal{I}_X, A)\). We obtain conditions on \(\text{Cay}(\mathcal{I}^*_X, A)\) for it to be \(\text{ColAut}_A(\mathcal{I}^*_X)\)-vertex-transitive and \(\text{Aut}_A(\mathcal{I}^*_X)\)-vertex-transitive. The basic structure of vertex-transitive \(\text{Cay}(\mathcal{I}^*_X, A)\) is characterized. We also investigate the undirected Cayley graphs of symmetric inverse semigroups, and prove that the generalized Petersen graph can be constructed as a connected component of a Cayley graph of a symmetric inverse semigroup, by choosing an appropriate connecting set.

A join graph is the complete union of two arbitrary graphs. An edge cover coloring is a coloring of edges of \(E(G)\) such that each color appears at each vertex \(v \in V(G)\) at least one time. The maximum number of colors needed to edge cover color \(G\) is called the edge cover chromatic index of \(G\) and denoted by \(\chi’C(G)\). It is well known that any simple graph \(G\) has the edge cover chromatic index equal to \(\delta(G)\) or \(\delta(G) – 1\), where \(\delta(G)\) is the minimum degree of \(G\). If \(\chi’C(G) = \delta(G)\), then \(G\) is of C1-Class , otherwise \(G\) is of C2-Class . In this paper, we give some sufficient conditions for a join graph to be of C1-Class.

Let \(G = (V, E)\) be a simple connected graph with vertex set \(V\) and edge set \(E\). The Wiener index of \(G\) is defined by \(W(G) = \sum_{x,y \subseteq V} d(x,y),\) where \(d(x,y)\) is the length of the shortest path from \(x\) to \(y\). The Szeged index of \(G\) is defined by \(S_z(G) = \sum_{e =uv\in E} n_u(e|G) n_v(e|G),\) where \(n_u(e|G)\) (resp. \(n_v(e|G)\)) is the number of vertices of \(G\) closer to \(u\) (resp. \(v\)) than \(v\) (resp. \(u\)). The Padmakar-Ivan index of \(G\) is defined by \(PI(G) = \sum_{e =uv \in E} [n_{eu}(e|G) + n_{ev}(e|G)],\) where \(n_{eu}(e|G)\) (resp. \(n_{ev}(e|G)\)) is the number of edges of \(G\) closer to \(u\) (resp. \(v\)) than \(v\) (resp. \(u\)). In this paper, we will consider the graph of a certain nanostar dendrimer consisting of a chain of hexagons and find its topological indices such as the Wiener, Szeged, and \(PI\) index.

In this paper, we introduce a class of digraphs called \((l,m)\)-walk-regular digraphs, a common generalization of both weakly distance-regular digraphs \([1]\) and \(k\)-walk-regular digraphs \([3]\), and give several characterizations of them about their regularity properties that are related to distance and about the number of walks of given length between vertices at a given distance.

A graph is said to be cordial if it has a 0-1 labeling that satisfies certain properties. A wheel \(W_n\) is the graph obtained from the join of the cycle \(C_n\) (\(n \geq 3\)) and the null graph \(N_1\). In this paper, we investigate the cordiality of the join and the union of pairs of wheels and graphs consisting of a wheel and a path or a cycle.

In this paper, we show new proofs of some important formulas by means of Liu’s expansion formula. Our results include a new proof of the identity for sums of two squares, a new proof of Gauss’s identity, a new proof of Euler’s identity, and a new proof of the identity for sums of four squares.

We explicitly evaluate the generating functions for joint distributions of pairs of the permutation statistics \(\text{inv}, {maj}\), and \({ch}\) over the symmetric group when both variables are set to \(-1\). We give a combinatorial proof by means of a sign-reversing involution that specializing the variables to \(-1\) in these bimahonian generating functions gives the number of two-colored permutations up to sign.

General methods for the construction of magic squares of any order have been searched for centuries. Several `standard strategies’ have been found for this purpose, such as the `knight movement’, or the construction of bordered magic squares, which played an important role in the development of general methods.

What we try to do here is to give a general and comprehensive approach to the construction of magic borders, capable of assuming methods produced in the past as particular cases. This general approach consists of a transformation of the problem of constructing magic borders to a simpler – almost trivial – form. In the first section, we give some definitions and notation. The second section consists of the exposition and proof of our method for the different cases that appear (Theorems 1 and 2). As an application of this method, in the third section we characterize magic borders of even order, giving therefore a first general result for bordered magic squares.

Although methods for the construction of bordered magic squares have always been presented as individual successful attempts to solve the problem, we will see that a common pattern underlies the fundamental mechanisms that lead to the construction of such squares. This approach provides techniques for constructing many magic bordered squares of any order, which is a first step to construct all of them, and finally know how many bordered squares are for any order. These may be the first elements of a general theory on bordered magic squares.

The main purpose of this paper is to define a pair of Konhauser matrix polynomials and obtain some properties, such as recurrence relations and matrix differential equations, for Konhauser matrix polynomials.

Studying expressions of the form \((f(z)D)^n\), where \(D = \frac{d}{dx}\) is the derivation operator, goes back to Scherk’s Ph.D. thesis in 1823. We show that this can be extended as
\(\sum{\gamma_{p;a}}(f^{(0)})^{a(0)+1}(f^{(1)})^{a(1)}\ldots (f^{(p-1)})^{a(p-1)}D^{p-\sum_i ia(i)},\) where the summation is taken over the \(p\)-tuples \((a_0, a_1, \ldots, a_{p-1})\), satisfying \(\sum_ia(i)=p-1 + ,\sum_iia(i) < p\), \(f^{(i)} = D^if\), and \(\gamma_{p;a}\) is the number of increasing trees on the vertex set \([0, p]\) having \(a(0) + 1\) leaves and having \(a(i)\) vertices with \(i\) children for \(0 < i < p\). Thus, previously known results about increasing trees lead us to some equalities containing coefficients \(\gamma_{p;a}\). In the sequel, we consider the expansion of \({(x^kD)}^p\) and coefficients appearing there, which are called generalized Stirling numbers by physicists. Some results about these coefficients and their inverses are discussed through bijective methods. Particularly, we introduce and use the notion of \((p,k)\)-forest in these arguments.