The sums \( S(x, t) \) of the centered remainders \( kt – \lfloor kt \rfloor – 1/2 \) over \( k \leq x \) and corresponding Dirichlet series were studied by A. Ostrowski, E. Hecke, H. Behnke, and S. Lang for fixed real irrational numbers \( t \). Their work was originally inspired by Weyl’s equidistribution results modulo 1 for sequences in number theory.
In a series of former papers, we obtained limit functions which describe scaling properties of the Farey sequence of order \( n \) for \( n \to \infty \) in the vicinity of any fixed fraction \( a/b \) and which are independent of \( a/b \). We extend this theory on the sums \( S(x, t) \) and also obtain a scaling behavior with a new limit function. This method leads to a refinement of results given by Ostrowski and Lang and establishes a new proof for the analytic continuation of related Dirichlet series. We will also present explicit relations to the theory of Farey sequences.
Bulgarian solitaire is played on \( n \) cards divided into several piles; a move consists of picking one card from each pile to form a new pile. This can be seen as a process on the set of integer partitions of \( n \): if sorted configurations are represented by Young diagrams, a move in the solitaire consists of picking all cards in the bottom layer of the diagram and inserting the picked cards as a new column. Here we consider a generalization, \( L \)-solitaire, wherein a fixed set of layers \( L \) (that includes the bottom layer) are picked to form a new column.
\( L \)-solitaire has the property that if a stable configuration of \( n \) cards exists it is unique. Moreover, the Young diagram of a configuration is convex if and only if it is a stable (fixpoint) configuration of some \( L \)-solitaire. If the Young diagrams representing card configurations are scaled down to have unit area, the stable configurations corresponding to an infinite sequence of pick-layer sets \( (L_1, L_2, \ldots) \) may tend to a limit shape \( \phi \). We show that every convex \( \phi \) with certain properties can arise as the limit shape of some sequence of \( L_n \). We conjecture that recurrent configurations have the same limit shapes as stable configurations.
For the special case \( L_n = \{1, 1 + \lfloor 1/q_n \rfloor, 1 + \lfloor 2/q_n \rfloor, \ldots\} \), where the pick layers are approximately equidistant with average distance \( 1/q_n \) for some \( q_n \in (0,1] \), these limit shapes are linear (in case \( nq_n^2 \to 0 \)), exponential (in case \( nq_n^2 \to \infty \)), or interpolating between these shapes (in case \( nq_n^2 \to C > 0 \)).
We introduce a polygonal cylinder \( C_{m,n} \), using the Cartesian product of paths \( P_m \) and \( P_n \) and using topological identification of vertices and edges of two opposite sides of \( P_m \times P_n \), and give its Hosoya polynomial, which, depending on odd and even \( m \), is covered in seven separate cases.
In this paper we find recurrence relations for the asymptotic probability a vertex is \(k\) protected in all Motzkin trees. We use a similar technique to calculate the probabilities for balanced vertices of rank \(k\). From this we calculate upper and lower bounds for the probability a vertex is balanced and upper and lower bounds for the expected rank of balanced vertices.
Binomial coefficients of the form \( \binom{\alpha}{\beta} \) for complex numbers \( \alpha \) and \( \beta \) can be defined in terms of the gamma function, or equivalently the generalized factorial function. Less well-known is the fact that if \( n \) is a natural number, the binomial coefficient \( \binom{n}{x} \) can be defined in terms of elementary functions. This enables us to investigate the function \( \binom{n}{x} \) of the real variable \( x \). The results are completely in line with what one would expect after glancing at the graph of \( \binom{3}{x} \), for example, but the techniques involved in the investigation are not the standard methods of calculus. The analysis is complicated by the existence of removable singularities at all of the integer points in the interval \( [0, n] \), and requires multiplying, rearranging, and differentiating infinite series.
In this paper, we analyze the stochastic properties of some large size (area) polyominoes’ perimeter such that the directed column-convex polyomino, the columnconvex polyomino, the directed diagonally-convex polyomino, the staircase (or parallelogram) polyomino, the escalier polyomino, the wall (orbargraph) polyomino. All polyominoes considered here are made of contiguous, not-empty columns, without holes, such that each column must be adjacent to some cell of the previous column. We compute the asymptotic (for large size n) Gaussian distribution of the perimeter, including the corresponding Markov property of the chain of columns, and the convergence to classical Brownian motions of the perimeter seen as a trajectory according to the successive columns. All polyominoes of size n are considered as equiprobable.
Convolution conditions are discussed for the \(q\)-analogue classes of Janowski starlike, convex and spirallike functions.
we discuss a framework for constructing large subsets of \(\mathbb{R}^n\) and \(K^n\) for non-archimedean local fields \(K\). This framework is applied to obtain new estimates for the Hausdorff dimension of angle-avoiding sets and to provide a counterexample to a limiting version of the Capset problem.
Let \( R \) be a commutative ring with unity and \( M \) be an \( R \)-module. The total graph of \( M \) with respect to the singular submodule \( Z(M) \) of \( M \) is an undirected graph \( T(\Gamma(M)) \) with vertex set as \( M \) and any two distinct vertices \( x \) and \( y \) are adjacent if and only if \( x + y \in Z(M) \). In this paper, the author attempts to study the domination in the graph \( T(\Gamma(M)) \) and investigate the domination number and the bondage number of \( T(\Gamma(M)) \) and its induced subgraphs. Some domination parameters of \( T(\Gamma(M)) \) are also studied. It has been shown that \( T(\Gamma(M)) \) is excellent, domatically full, and well covered under certain conditions.
In this paper, we study a class of sequences of polynomials linked to the sequence of Bell polynomials. Some sequences of this class have applications on the theory of hyperbolic differential equations and other sequences generalize Laguerre polynomials and associated Lah polynomials. We discuss, for these polynomials, their explicit expressions, relations to the successive derivatives of a given function, real zeros and recurrence relations. Some known results are significantly simplified.
We show that if \( G \) is a discrete Abelian group and \( A \subseteq G \) has \( \|1_A\|_{B(G)} \leq M \), then \( A \) is \( O(\exp(\pi M)) \)-stable in the sense of Terry and Wolf.
This paper gives some new results on mutually orthogonal graph squares (MOGS). These generalize mutually orthogonal Latin squares in an interesting way. As such, the topic is quite nice and should have broad appeal. MOGS have strong connections to core fields of finite algebra, cryptography, finite geometry, and design of experiments. We are concerned with the Kronecker product of mutually orthogonal graph squares to get new results of the mutually orthogonal certain graphs squares.
For Cauchy numbers of the first kind \(\{a_n\}_{n \geq 0}\) and Cauchy numbers of the second kind \(\{b_n\}_{n \geq 0}\), we prove that two sequences \(\left\{ \sqrt[n]{|a_n|} \right\}_{n \geq 2}\) and \(\left\{ \sqrt[n]{b_n} \right\}_{n \geq 1}\) are log-concave. In addition, we show that two sequences \(\left\{ \frac{1}{\sqrt[n]{|a_n|}} \right\}_{n \geq 2}\) and \(\left\{ \frac{1}{\sqrt[n]{b_n}} \right\}_{n \geq 1}\) are log-balanced.
Let \( p(x) = a_0 + a_1x + \dots + a_nx^n \) be a polynomial with all roots real and satisfying \( x \leq -\delta \) for some \( 0 < \delta < 1 \). We show that for any \( 0 < \epsilon 0 \). As a corollary, we show that if \( m_k(G) \) is the number of matchings with \( k \) edges in a graph \( G \), then for any \( 0 < \epsilon 0 \) is an absolute constant. We prove a similar result for polynomials with complex roots satisfying \( \Re z \leq -\delta \) and apply it to estimate the number of unbranched subgraphs of \( G \).
Let \( G \) be a graph, a subset \( S \subseteq E(G) \) is called an edge hub set of \( G \) if every pair of edges \( e, f \in E(G) \setminus S \) are connected by a path where all internal edges are from \( S \). The minimum cardinality of an edge hub set is called the edge hub number of \( G \), and is denoted by \( h_e(G) \). If \( G \) is a disconnected graph, then any edge hub set must contain all of the edges in all but one of the components, as well as an edge hub set in the remaining component. In this paper, the edge hub number for several classes of graphs is computed, and bounds in terms of other graph parameters are also determined.
In 1998, D. Callan obtained a binomial identity involving the derangement numbers. In this paper, by using the theory of formal series, we extend such an identity to the generalized derangement numbers. Then, by using the same technique, we obtain other identities of the same kind for the generalized arrangement numbers, the generalized Laguerre polynomials, the generalized Hermite polynomials, the generalized exponential polynomials and the generalized Bell numbers, the hyperharmonic numbers, the Lagrange polynomials and the Gegenbauer polynomials.
In this paper, we present a method to construct a cyclic orthogonal double cover (CODC) of circulant graphs by certain kinds of coronas that model by linear functions.
Following the work of Cano and Díaz, we study continuous binomial coefficients and Catalan numbers. We explore their analytic properties, including integral identities and generalizations of discrete convolutions. We also conduct an in-depth analysis of a continuous analogue of the binomial distribution, including a stochastic representation as a Goldstein-Kac process.
In this paper, we introduce a new operator in order to derive some properties of homogeneous symmetric functions. By making use of the proposed operator, we give some new generating functions for \( k \)-Fibonacci numbers, \( k \)-Pell numbers, and the product of sequences and Chebyshev polynomials of the second kind.
In this paper, we introduce the concept block matrix (B-matrix) of a graph \( G \), and obtain some coefficients of the characteristic polynomial \( \phi(G, \mu) \) of the B-matrix of \( G \). The block energy \( E_B(G) \) is established. Further upper and lower bounds for \( E_B(G) \) are obtained. In addition, we define a uni-block graph. Some properties and new bounds for the block energy of the uni-block graph are presented.
We consider analogs of several classical diophantine equations, such as Fermat’s last theorem and Catalan’s conjecture, for certain classes of analytic functions. We give simple direct proofs avoiding use of deep theorems in complex analysis. As a byproduct of our results, we obtain new proofs for the corresponding results over polynomials.
We define the \( (i, j) \)-liars’ domination number of \( G \), denoted by \( LR(i, j)(G) \), to be the minimum cardinality of a set \( L \subseteq V(G) \) such that detection devices placed at the vertices in \( L \) can precisely determine the set of intruder locations when there are between 1 and \( i \) intruders and at most \( j \) detection devices that might “lie”.
We also define the \( X(c_1, c_2, \ldots, c_t, \ldots) \)-domination number, denoted by \( \gamma _{X(c_1, c_2, \ldots, c_t, \ldots)}(G) \), to be the minimum cardinality of a set \( D \subseteq V(G) \) such that, if \( S \subseteq V(G) \) with \( |S| = k \), then \( |(\bigcup_{v \in S} N[v]) \cap D| \geq c_k \). Thus, \( D \) dominates each set of \( k \) vertices at least \( c_k \) times making \( \gamma_{X(c_1, c_2, \ldots, c_t, \ldots)}(G) \) a set-sized dominating parameter. We consider the relations between these set-sized dominating parameters and the liars’ dominating parameters.
For Cauchy numbers of the first kind \( \{a_n\}{n \geq 0} \) and Cauchy numbers of the second kind \( \{b_n\}{n \geq 0} \), this paper focuses on the log-convexity of some sequences related to \( \{a_n\}{n \geq 0} \) and \( \{b_n\}{n \geq 0} \). For example, we discuss log-convexity of \( \{n|a_n| – |a_{n+1}|\}{n \geq 1} \), \( \{b{n+1} – nb_n\}{n \geq 1} \), \( \{n|a_n|\}{n \geq 1} \), and \( \{(n + 1)b_n\}_{n \geq 0} \). In addition, we investigate log-balancedness of some sequences involving \( a_n \) (or \( b_n \)).
Let \( G \) be a graph. We define the distance \( d \) pebbling number of \( G \) to be the smallest number \( s \) such that if \( s \) pebbles are placed on the vertices of \( G \), then there must exist a sequence of pebbling moves which takes a pebble to a vertex which is at a distance of at least \( d \) from its starting point. In this article, we evaluate the distance \( d \) pebbling numbers for a directed cycle graph with \( n \) vertices.
Let \( G \) be a \( k \)-connected (\( k \geq 2 \)) graph of order \( n \). If \( \gamma(G^c) \geq n – k \), then \( G \) is Hamiltonian or \( K_k \vee K_{k+1}^c \), where \( \gamma(G^c) \) is the domination number of the complement of the graph \( G \).
An \emph{Italian dominating function} on a digraph \( D \) with vertex set \( V(D) \) is defined as a function \( f : V(D) \to \{0, 1, 2\} \) such that every vertex \( v \in V(D) \) with \( f(v) = 0 \) has at least two in-neighbors assigned 1 under \( f \) or one in-neighbor \( w \) with \( f(w) = 2 \). The weight of an Italian dominating function is the sum \( \sum_{v \in V(D)} f(v) \), and the minimum weight of an Italian dominating function \( f \) is the \emph{Italian domination number}, denoted by \( \gamma_I(D) \). We initiate the study of the Italian domination number for digraphs, and we present different sharp bounds on \( \gamma_I(D) \). In addition, we determine the Italian domination number of some classes of digraphs. As applications of the bounds and properties on the Italian domination number in digraphs, we give some new and some known results of the Italian domination number in graphs.
A hypergraph \( H \) with vertex set \( V \) and edge set \( E \) is called bipartite if \( V \) can be partitioned into two subsets \( V_1 \) and \( V_2 \) such that \( e \cap V_1 \neq \phi \) and \( e \cap V_2 \neq \phi \) for any \( e \in E \). A bipartite self-complementary 3-uniform hypergraph \( H \) with partition \( (V_1, V_2) \) of a vertex set \( V \) such that \( |V_1| = m \) and \( |V_2| = n \) exists if and only if either (i) \( m = n \) or (ii) \( m \neq n \) and either \( m \) or \( n \) is congruent to 0 modulo 4 or (iii) \( m \neq n \) and both \( m \) and \( n \) are congruent to 1 or 2 modulo 4.
In this paper we prove that, there exists a regular bipartite self-complementary 3-uniform hypergraph \( H(V_1, V_2) \) with \( |V_1| = m, |V_2| = n, m + n > 3 \) if and only if \( m = n \) and \( n \) is congruent to 0 or 1 modulo 4. Further we prove that, there exists a quasi-regular bipartite self-complementary 3-uniform hypergraph \( H(V_1, V_2) \) with \( |V_1| = m, |V_2| = n, m + n > 3 \) if and only if either \( m = 3, n = 4 \) or \( m = n \) and \( n \) is congruent to 2 or 3 modulo 4.
Neighborhood-prime labeling is a variation of prime labeling. A labeling \( f : V(G) \to [|V(G)|] \) is a neighborhood-prime labeling if for each vertex \( v \in V(G) \) with degree greater than 1, the greatest common divisor of the set of labels in the neighborhood of \( v \) is 1. In this paper, we introduce techniques for finding neighborhood-prime labelings based on the Hamiltonicity of the graph, by using conditions on possible degrees of vertices, and by examining a neighborhood graph. In particular, classes of graphs shown to be neighborhood-prime include all generalized Petersen graphs, grid graphs of any size, and lobsters given restrictions on the degree of the vertices. In addition, we show that almost all graphs and almost all regular graphs have neighborhood-prime, and we find all graphs of this type.
Let \( A(n, d, w) \) denote the maximum size of a binary code with length \( n \), minimum distance \( d \), and constant weight \( w \). The following lower bounds are here obtained in computer searches for codes with prescribed automorphisms: \( A(16, 4, 6) \geq 624 \), \( A(19, 4, 8) \geq 4698 \), \( A(20, 4, 8) \geq 7830 \), \( A(21, 4, 6) \geq 2880 \), \( A(22, 6, 6) \geq 343 \), \( A(24, 4, 5) \geq 1920 \), \( A(24, 6, 9) \geq 3080 \), \( A(24, 6, 11) \geq 5376 \), \( A(24, 6, 12) \geq 5558 \), \( A(25, 4, 5) \geq 2380 \), \( A(25, 6, 10) \geq 6600 \), \( A(26, 4, 5) \geq 2816 \), and \( A(27, 4, 5) \geq 3456 \).
For a finite simple graph \( G \), say \( G \) is of dimension \( n \), and write \( \text{dim}(G) = n \), if \( n \) is the smallest integer such that \( G \) can be represented as a unit-distance graph in \( \mathbb{R}^n \). Define \( G \) to be \emph{dimension-critical} if every proper subgraph of \( G \) has dimension less than \( G \). In this article, we determine exactly which complete multipartite graphs are dimension-critical. It is then shown that for each \( n \geq 2 \), there is an arbitrarily large dimension-critical graph \( G \) with \( \text{dim}(G) = n \). We close with a few observations and questions that may aid in future work.
Let \( G \) be a simple and finite graph. A graph is said to be decomposed into subgraphs \( H_1 \) and \( H_2 \) which is denoted by \( G = H_1 \oplus H_2 \), if \( G \) is the edge disjoint union of \( H_1 \) and \( H_2 \). If \( G = H_1 \oplus H_2 \oplus \cdots \oplus H_k \), where \( H_1, H_2, \ldots, H_k \) are all isomorphic to \( H \), then \( G \) is said to be \( H \)-decomposable. Furthermore, if \( H \) is a cycle of length \( m \), then we say that \( G \) is \( C_m \)-decomposable and this can be written as \( C_m \mid G \). Where \( G \times H \) denotes the tensor product of graphs \( G \) and \( H \), in this paper, we prove that the necessary conditions for the existence of \( C_6 \)-decomposition of \( K_m \times K_n \) are sufficient. Using these conditions it can be shown that every even regular complete multipartite graph \( G \) is \( C_6 \)-decomposable if the number of edges of \( G \) is divisible by 6.
Let \( F, G \) and \( H \) be graphs. A \( (G, H) \)-decomposition of \( F \) is a partition of the edge set of \( F \) into copies of \( G \) and copies of \( H \) with at least one copy of \( G \) and at least one copy of \( H \). For \( L \subseteq F \), a \( (G, H) \)-packing of \( F \) with leave \( L \) is a \( (G, H) \)-decomposition of \( F – E(L) \). A \( (G, H) \)-packing of \( F \) with the largest cardinality is a maximum \( (G, H) \)-packing. This paper gives the solution of finding the maximum \( (C_k, S_k) \)-packing of the crown \( C_{n, n-1} \).
Rautenbach and Volkmann [Appl. Math. Lett. 20 (2007), 98–102] gave an upper bound for the \( k \)-domination number and \( k \)-tuple domination number of a graph. Hansberg and Volkmann, [Discrete Appl. Math. 157 (2009), 1634–1639] gave upper bounds for the \( k \)-domination number and Roman \( k \)-domination number of a graph. In this note, using the probabilistic method and the known Caro-Wei Theorem on the size of the independence number of a graph, we improve the above bounds on the \( k \)-domination number, the \( k \)-tuple domination number and the Roman \( k \)-domination number in a graph for any integer \( k \geq 1 \). The special case \( k = 1 \) of our bounds improve the known bounds of Arnautov and Payan [V.I. Arnautov, Prikl. Mat. Programm. 11 (1974), 3–8 (in Russian); C. Payan, Cahiers Centre Études Recherche Opér. 17 (1975) 307–317] and Cockayne et al. [Discrete Math. 278 (2004), 11–22].
Addressing a problem posed by Chellali, Haynes, and Hedetniemi (Discrete Appl. Math. 178 (2014) 27–32), we prove \( \gamma_{r2}(G) \leq 2\gamma_r(G) \) for every graph \( G \), where \( \gamma_{r2}(G) \) and \( \gamma_r(G) \) denote the 2-rainbow domination number and the weak Roman domination number of \( G \), respectively. We characterize the extremal graphs for this inequality that are \( \{K_4, K_4 – e\} \)-free, and show that the recognition of the \( K_5 \)-free extremal graphs is NP-hard.
For a graph \( H \), let \( \delta_t(H) = \min\{|\bigcup_{i=1}^t N_H(v_i)| : |v_1, \dots, v_t| \text{ are } t \text{ vertices in } H\} \). We show that for a given number \( \epsilon \) and given integers \( p \geq 2 \) and \( k \in \{2, 3\} \), the family of \( k \)-connected Hamiltonian claw-free graphs \( H \) of sufficiently large order \( n \) with \( \delta(H) \geq 3 \) and \( \delta_k(H) \geq t(n + \epsilon)/p \) has a finite obstruction set in which each member is a \( k \)-edge-connected \( K_3 \)-free graph of order at most \( \max\{p/t + 2t, 3p/t + 2t – 7\} \) and without spanning closed trails. We found the best possible values of \( p \) and \( \epsilon \) for some \( t \geq 2 \) when the obstruction set is empty or has the Petersen graph only. In particular, we prove the following for such graphs \( H \):
These bounds on \( \delta_t(H) \) are sharp. Since the number of graphs of orders at most \( \max\{p/t + 2t, 3p/t + 2t – 7\} \) is finite for given \( p \) and \( t \), improvements to (a), (b), or (c) by increasing the value of \( p \) are possible with the help of a computer.
Any dominating set of vertices in a triangle-free graph can be used to specify a graph coloring with at most one color class more than the number of vertices in the dominating set. This bound is sharp for many graphs. Properties of graphs for which this bound is achieved are presented.
A graph \( G \) is quasi-claw-free if it satisfies the property: \( d(x, y) = 2 \) implies there exists \( u \in N(x) \cap N(y) \) such that \( N[u] \subseteq N[x] \cup N[y] \). The matching number of a graph \( G \) is the size of a maximum matching in the graph. In this note, we present a sufficient condition involving the matching number for the Hamiltonicity of quasi-claw-free graphs.
Let \( S \) be an orthogonal polygon and let \( A_1, \ldots, A_n \) represent pairwise disjoint sets, each the connected interior of an orthogonal polygon, \( A_i \subseteq S, 1 \leq i \leq n \). Define \( T = S \setminus (A_1 \cup \ldots \cup A_n) \). We have the following Krasnosel’skii-type result: Set \( T \) is staircase star-shaped if and only if \( S \) is staircase star-shaped and every \( 4n \) points of \( T \) see via staircase paths in \( T \) a common point of \( \text{Ker } S \). Moreover, the proof offers a procedure to select a particular collection of \( 4n \) points of \( T \) such that the subset of \( \text{Ker } S \) seen by these \( 4n \) points is exactly \( \text{Ker } T \). When \( n = 1 \), the number 4 is best possible.
The \( p \)-competition graph \( C_p(D) \) of a digraph \( D = (V, A) \) is a graph with \( V(C_p(D)) = V(D) \), where an edge between distinct vertices \( x \) and \( y \) if and only if there exist \( p \) distinct vertices \( v_1, v_2, \ldots, v_p \in V \) such that \( x \to v_i, y \to v_i \) are arcs of the digraph \( D \) for each \( i = 1, 2, \ldots, p \). In this paper, we prove that double stars \( DS_m \) (\( m \geq 2 \)) are \( p \)-competition graphs. We also show that full regular \( m \)-ary trees \( T_{m,n} \) with height \( n \) are \( p \)-competition graphs, where \( p \leq \frac{m – 1}{2} \).
Let \( G \) be a graph with at least half of the vertices having degree at least \( k \). For a tree \( T \) with \( k \) edges, Loebl, Komlós, and Sós conjectured that \( G \) contains \( T \). It is known that if the length of a longest path in \( T \) (i.e., the diameter of \( T \)) is at most 5, then \( G \) contains \( T \). Since \( T \) is a bipartite graph, let \( \ell \) be the number of vertices in the smaller (or equal) part. Clearly \( 1 \leq \ell \leq \frac{1}{2}(k + 1) \). In our main theorem, we prove that if \( 1 \leq \ell \leq \frac{1}{6}k + 1 \), then the graph \( G \) contains \( T \). Notice that this includes certain trees of diameter up to \( \frac{1}{3}k + 2 \).
If a tree \( T \) consists of only a path and vertices that are connected to the path by an edge, then the tree \( T \) is a caterpillar. Let \( P \) be the path obtained from the caterpillar \( T \) by removing each leaf of \( T \), where \( P = a_1, \ldots, a_r \). The path \( P \) is the spine of the caterpillar \( T \), and each vertex on the spine of \( T \) with degree at least 3 in \( T \) is a joint. It is known that the graph \( G \) contains certain caterpillars having at most two joints. If only odd-indexed vertices on the spine \( P \) are joints, then the caterpillar \( T \) is an odd caterpillar. If the spine \( P \) has at most \( \lceil \frac{1}{2}k \rceil \) vertices, then \( T \) is a short caterpillar. We prove that the graph \( G \) contains every short, odd caterpillar with \( k \) edges.
The decision problems of the existence of a Hamiltonian cycle or of a Hamiltonian path in a given graph, and of the existence of a truth assignment satisfying a given Boolean formula C, are well-known NP-complete problems. Here we study the problems of the uniqueness of a Hamiltonian cycle or path in an undirected, directed or oriented graph, and show that they have the same complexity, up to polynomials, as the problem U-SAT of the uniqueness of an assignment satisfying C. As a consequence, these Hamiltonian problems are NP-hard and belong to the class DP, like U-SAT.
A graph \( G \) is \( k \)-frugal colorable if there exists a proper vertex coloring of \( G \) such that every color appears at most \( k – 1 \) times in the neighborhood of \( v \). The \( k \)-frugal chromatic number, denoted by \( \chi_k(G) \), is the smallest integer \( l \) such that \( G \) is \( k \)-frugal colorable with \( l \) colors. A graph \( G \) is \( L \)-list colorable if there exists a coloring \( c \) of \( G \) for a given list assignment \( L = \{L(v) : v \in V(G)\} \) such that \( c(v) \in L(v) \) for all \( v \in V(G) \). If \( G \) is \( k \)-frugal \( L \)-colorable for any list assignment \( L \) with \( |L(v)| \geq l \) for all \( v \in V(G) \), then \( G \) is said to be \( k \)-frugal \( l \)-list-colorable. The smallest integer \( l \) such that the graph \( G \) is \( k \)-frugal \( l \)-list-colorable is called the \( k \)-frugal list chromatic number, denoted by \( \text{ch}_k(G) \). It is clear that \( \text{ch}_k(G) \geq \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 1 \) for any graph \( G \) with maximum degree \( \Delta(G) \). In this paper, we prove that for any integer \( k \geq 4 \), if \( G \) is a planar graph with maximum degree \( \Delta(G) \geq 13k – 11 \) and girth \( g \geq 6 \), then \( \text{ch}_k(G) = \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 1; \) and if \( G \) is a planar graph with girth \( g \geq 6 \), then \(\text{ch}_k(G) \leq \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 2.\)
In 1987, Alavi, Boals, Chartrand, Erdös, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). In previous papers, we showed that all tournaments of order congruent to 1, 2, or 3 mod 6 have an ASD. In this paper, we will consider the case where the tournament has order congruent to 5 mod 6.
An \( H \)-decomposition of a graph \( G \) is a partition of the edges of \( G \) into copies isomorphic to \( H \). When the decomposition is not feasible, one looks for the best possible by minimizing: the number of unused edges (leave of a packing), or the number of reused edges (padding of a covering). We consider the \( H \)-decomposition, packing, and covering of the complete graphs and complete bipartite graphs, where \( H \) is a 4-cycle with three pendant edges.
We introduce a new bivariate polynomial
\[
J(G; x, y) := \sum_{W \subseteq V(G)} x^{|W|} y^{|N[W]| – |W|}
\]
which contains the standard domination polynomial of the graph \( G \) in two different ways. We build methods for efficient calculation of this polynomial and prove that there are still some families of graphs which have the same bivariate polynomial.
Let \( G \) be a \( (p, q) \) graph. Let \( f : V(G) \to \{1, 2, \ldots, k\} \) be a map where \( k \) is an integer \( 2 \leq k \leq p \). For each edge \( uv \), assign the label \( |f(u) – f(v)| \). \( f \) is called \( k \)-difference cordial labeling of \( G \) if \( |v_f(i) – v_f(j)| \leq 1 \) and \( |e_f(0) – e_f(1)| \leq 1 \), where \( v_f(x) \) denotes the number of vertices labeled with \( x \), \( e_f(1) \) and \( e_f(0) \) respectively denote the number of edges labeled with 1 and not labeled with 1. A graph with a \( k \)-difference cordial labeling is called a \( k \)-difference cordial graph. In this paper, we investigate 3-difference cordial labeling behavior of slanting ladder, book with triangular pages, middle graph of a path, shadow graph of a path, triangular ladder, and the armed crown.
In this paper, we consider the sequences \( \{F(n, k)\}_{n \geq k} \) (\(k \geq 1\)) defined by\( F(n, k) = (n – 2)F(n – 1, k) + F(n – 1, k – 1), \quad F(n, 1) = \frac{n!}{2}, \quad F(n, n) = 1. \) We mainly study the log-convexity of \( \{F(n, k)\}{n \geq k} \) (\(k \geq 1\)) when \( k \) is fixed. We prove that \( \{F(n, 3)\}{n \geq 3}, \{F(n, 4)\}{n \geq 5}, \) and \( \{F(n, 5)\}{n \geq 6} \) are log-convex. In addition, we discuss the log-behavior of some sequences related to \( F(n, k) \).
\end{abstract}
Let \( G = C_n \oplus C_n \) with \( n \geq 3 \) and \( S \) be a sequence with elements of \( G \). Let \( \Sigma(S) \subseteq G \) denote the set of group elements which can be expressed as a sum of a nonempty subsequence of \( S \). In this note, we show that if \( S \) contains \( 2n – 3 \) elements of \( G \), then either \( 0 \in \Sigma(S) \) or \( |\Sigma(S)| \geq n^2 – n – 1 \). Moreover, we determine the structures of the sequence \( S \) over \( G \) with length \( |S| = 2n – 3 \) such that \( 0 \notin \Sigma(S) \) and \( |\Sigma(S)| = n^2 – n – 1 \).
Let \(G\) be a finite and simple graph with vertex set \(V(G)\). A nonnegative signed Roman dominating function (NNSRDF) on a graph \(G\) is a function \(f:V(G)\to \{-1,1,2\}\) satisfying the conditions that (i) \(\sum_{x\in N[v]}f(x)\ge 0\) for each \(v \in V(G)\), where \(N[v]\) is the closed neighborhood of \(v\) and (ii)every vertex u for which \(f(u)=-1\) has a neighbor v for which \(f(v)=2\). The weight of an NNSRDF \(f\) is \(\omega(f) = \sum_{v\in V(G)} f(v)\). The nonnegative signed Roman domination number \(\gamma_{sR}^{NN} (G)\) of \(G\) is the minimum weight of an NNSRDF \(G\) In this paper, we initiate the study of the nonnegative signed Roman domination number of a graph and we present different bounds on \(\gamma _{sR}^{NN}(G) \ge (8n-12m)/7\). In addition, if \(G\) is a bipartite graph of order \(n\), then we prove that \(\gamma _{sR}^{NN}(G) \ge^\frac{3}{2}(\sqrt{4n+9}-3)-n\), and we characterize the external graphs.
We consider inverse-conjugate compositions of a positive integer \(n\) in which the parts belong to the residue class of 1 modulo an integer \(m > 0\). It is proved that such compositions exist only for values of \(n\) that belong to the residue class of 1 modulo 2m. An enumerations results is provided using the properties of inverse-conjugate compositions. This work extends recent results for inverse-conjugate compositions with odd parts.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.