For \(r=1,2,…, 6\), we obtain generating functions \(F^{(r)}_{k}(y)\) for words over the alphabet \([k]\), where \(y\) tracks the number of parts and \([y^n]\) is the total number of distinct adjacent \(r\)-tuples in words with \(n\) parts. In order to develop these generating functions for \(1\le r\le 3\), we make use of intuitive decompositions but for larger values of \(r\), we switch to the cluster analysis method for decorated texts that was introduced by Bassino et al. Finally, we account for the coefficients of these generating functions in terms of Stirling set numbers. This is done by putting forward the full triangle of coefficients for all the sub-cases where \(r=5\) and 6. This latter is shown to depend on both periodicity and number of letters used in the \(r\)-tuples.
We consider the following variant of the round-robin scheduling problem: \(2n\) people play a number of rounds in which two opposing teams of \(n\) players are reassembled in each round. Each two players should play at least once in the same team, and each two players should play at least once in opposing teams. We provide an explicit formula for calculating the minimal numbers of rounds needed to satisfy both conditions. Moreover, we also show how one can construct the corresponding playing schedules.
Two binary structures \(\mathfrak{R}\) and \(\mathfrak{R’}\) on the same vertex set \(V\) are \((\leq k)\)-hypomorphic for a positive integer \(k\) if, for every set \(K\) of at most \(k\) vertices, the two binary structures induced by \(\mathfrak{R}\) and \(\mathfrak{R’}\) on \(K\) are isomorphic. A binary structure \(\mathfrak{R}\) is \((\leq k)\)-reconstructible if every binary
structure \(\mathfrak{R’}\) that is \((\leq k)\)-hypomorphic to \(\mathfrak{R}\) is isomorphic to \(\mathfrak{R}\). In this paper, we describe the pairs of \((\leq 3)\)-hypomorphic posets and the pairs of \((\leq 3)\)-hypomorphic bichains. As a consequence, we characterize the \((\leq 3)\)-reconstructible posets and the \((\leq 3)\)-reconstructible bichains. This answers a question suggested by Y. Boudabbous and C. Delhommé during a personal communication.
A tremendous amount of drug experiments revealed that there exists a strong inherent relation between the molecular structures of drugs and their biomedical and pharmacology characteristics. Due to the effectiveness for pharmaceutical and medical scientists of their ability to grasp the biological and chemical characteristics of new drugs, analysis of the bond incident degree (BID) indices is significant of testing the chemical and pharmacological characteristics of drug molecular structures that can make up the defects of chemical and medicine experiments and can provide the theoretical basis for the manufacturing of drugs in pharmaceutical engineering. Such tricks are widely welcomed in developing areas where enough money is lacked to afford sufficient equipment, relevant chemical reagents, and human resources which are required to investigate the performance and the side effects of existing new drugs. This work is devoted to establishing a general expression for calculating the bond incident degree (BID) indices of the line graphs of various well-known chemical structures in drugs, based on the drug molecular structure analysis and edge dividing technique, which is quite common in drug molecular graphs.
In this paper, we introduce a graph structure, called component intersection graph, on a finite dimensional vector space \(\mathbb{V}\). The connectivity, diameter, maximal independent sets, clique number, chromatic number of component intersection graph have been studied.
A linear system is a pair \((P,\mathcal{L})\) where \(\mathcal{L}\) is a finite family of subsets on a finite ground set \(P\) such that any two subsets of \(\mathcal{L}\) share at most one element. Furthermore, if for every two subsets of \(\mathcal{L}\) share exactly one element, the linear system is called intersecting. A linear system \((P,\mathcal{L})\) has rank \(r\) if the maximum size of any element of \(\mathcal{L}\) is \(r\). By \(\gamma(P,\mathcal{L})\) and \(\nu_2(P,\mathcal{L})\) we denote the size of the minimum dominating set and the maximum 2-packing of a linear system \((P,\mathcal{L})\), respectively. It is known that any intersecting linear system \((P,\mathcal{L})\) of rank \(r\) is such that \(\gamma(P,\mathcal{L})\leq r-1\). Li et al. in [S. Li, L. Kang, E. Shan and Y. Dong, The finite projective plane and the 5-Uniform linear intersecting hypergraphs with domination number four, Graphs and 34 Combinatorics (2018) , no.~5, 931–945.] proved that every intersecting linear system of rank 5 satisfying \(\gamma(P,\mathcal{L})=4\) can be constructed from a 4-uniform intersecting linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of the projective plane of order 3 satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=4\), where \(\tau(P^\prime,\mathcal{L}^\prime)\) is the transversal number of \((P^\prime,\mathcal{L}^\prime)\). In this paper, we give an alternative proof of this result given by Li et al., giving a complete characterization of these 4-uniform intersecting linear subsystems. Moreover, we prove a general case, that is, we prove if $q$ is an odd prime power and \((P,\mathcal{L})\) is an intersecting linear system of rank \((q+2)\) satisfying \(\gamma(P,\mathcal{L})=q+1\), then this linear system can be constructed from a spanning \((q+1)\)-uniform intersecting linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of the projective plane of order \(q\) satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=q+1\).
We classify all near hexagons of order \((3,t)\) that contain a big quad. We show that, up to isomorphism, there are ten such near hexagons.
Let \(G=(V,E)\) be a simple graph. A vertex \(v\in V(G)\) ve-dominates every edge \(uv\) incident to \(v\), as well as every edge adjacent to these incident edges. A set
\(D\subseteq V(G)\) is a vertex-edge dominating set if every edge of \(E(G)\) is ve-dominated by a vertex of \(D.\) The MINIMUM VERTEX-EDGE DOMINATION problem is to find a vertex-edge dominating set of minimum cardinality. A linear time algorithm to find the minimum vertex-edge dominating set for proper interval graphs is proposed. The vertex-edge domination problem is proved to be APX-complete for bounded-free graphs and NP-Complete for Chordal bipartite and Undirected Path graphs.
In this paper, we investigate the \((d,1)\)-total labelling of generalized Petersen graphs \(P(n,k)\) for \(d\geq 3\). We find that the \((d,1)\)-total number of \(P(n,k)\) with \(d\geq 3\) is \(d+3\) for even \(n\) and odd \(k\) or even \(n\) and \(k=\frac{n}{2}\), and \(d+4\) for all other cases.
By employing Kummer and Thomae transformations, we examine four classes of nonterminating \(_3F_2\)(1)-series with five integer parameters. Several new summation formulae are established in closed form.
Achieving accurate prediction of financial market fluctuations is beneficial for investors to make decisions, while machine learning algorithms can utilize a large amount of data for training and learning, which has good effect on predicting financial market fluctuations. The article first analyzes the financial dataset, and then constructs a feature selection model by combining Boruta and SHAP to screen the financial data features. Based on the LSTM model, a new Dropout layer and fully connected layer are designed to construct the AMP-LSTM model to realize the prediction of financial market fluctuations. The Boruta SHAP algorithm has a RMSPE of 0.242, which is good for screening. The prediction performance of the AMP-LSTM model is significantly better than that of the traditional LSTM (p<0.01), and the predicted values are closer to the actual values. The method in this paper performs better than MLP, RNN and other methods in general in terms of error performance when predicting indicators such as WTI, Brent, LGO, etc., and is able to realize the prediction of financial market volatility in the digital economy environment.
Let \(G=(V,\,E)\) be a simple graph with vertex set \(V(G)\) and edge set \(E(G)\). The Lanzhou index of a graph \(G\) is defined by \(Lz(G)=\sum\limits_{u \in V(G)} d_u^2\overline{d}_u\), where \(d_u\) (\(\overline{d}_u \) resp.) denotes the degree of the vertex \(u\) in \(G\) (\(\overline{G}\), the complement graph of \(G\) resp.). It has predictive powers to provide insights of chemical relevant properties of chemical graph structures. In this paper we discuss some properties of Lanzhou index. Several inequalities having lower and upper bound for the Lanzhou index in terms of first, second and third Zagreb indices, radius of graph, eccentric connectivity index, Schultz index, inverse sum indeg index and symmetric division deg index, are discussed. At the end the Lanzhou index of corona and join of graphs have been derived.
We define an extremal \((r|\chi)\)-graph as an \(r\)-regular graph with chromatic number \(\chi\) of minimum order. We show that the Turán graphs \(T_{ak,k}\), the antihole graphs and the graphs \(K_k\times K_2\) are extremal in this sense. We also study extremal Cayley \((r|\chi)\)-graphs and we exhibit several \((r|\chi)\)-graph constructions arising from Turán graphs.
A dominating broadcast of a graph \(G\) is a function \(f : V(G) \rightarrow \lbrace 0, 1, 2, \dots ,\text{diam}(G)\rbrace\) such that \(f(v) \leqslant e(v)\) for all \(v \in V(G)\), where \(e(v)\) is the eccentricity of \(v\), and for every vertex \(u \in V(G)\), there exists a vertex \(v\) with \(f(v) > 0\) and \(\text{d}(u,v) \leqslant f(v)\). The cost of \(f\) is \(\sum_{v \in V(G)} f(v)\). The minimum of costs over all the dominating broadcasts of \(G\) is called the broadcast domination number \(\gamma_{b}(G)\) of \(G\). A graph $G$ is said to be radial if \(\gamma_{b}(G)=\text{rad}(G)\). In this article, we give tight upper and lower bounds for the broadcast domination number of the line graph \(L(G)\) of \(G\), in terms of \(\gamma_{b}(G)\), and improve the upper bound of the same for the line graphs of trees. We present a necessary and sufficient condition for radial line graphs of central trees, and exhibit constructions of infinitely many central trees \(T\) for which \(L(T)\) is radial. We give a characterization for radial line graphs of trees, and show that the line graphs of the \(i\)-subdivision graph of \(K_{1,n}\) and a subclass of caterpillars are radial. Also, we show that \(\gamma_{b}(L(C))=\gamma(L(C))\) for any caterpillar \(C\).
In this paper we introduce the concept of independent fixed connected geodetic number and investigate its behaviours on some standard graphs. Lower and upper bounds are found for the above number and we characterize the suitable graphs achieving these bounds. We also define two new parameters connected geo-independent number and upper connected geo-independent number of a graph. Few characterization and realization results are formulated for the new parameters. Finally an open problem is posed.
Let \(E(H)\) and \(V(H)\) denote the edge set and the vertex set of the simple connected graph \(H\), respectively. The mixed metric dimension of the graph \(H\) is the graph invariant, which is the mixture of two important graph parameters, the edge metric dimension and the metric dimension. In this article, we compute the mixed metric dimension for the two families of the plane graphs viz., the Web graph \(\mathbb{W}_{n}\) and the Prism allied graph \(\mathbb{D}_{n}^{t}\). We show that the mixed metric dimension is non-constant unbounded for these two families of the plane graph. Moreover, for the Web graph \(\mathbb{W}_{n}\) and the Prism allied graph \(\mathbb{D}_{n}^{t}\), we unveil that the mixed metric basis set \(M_{G}^{m}\) is independent.
Consider a total labeling \(\xi\) of a graph \(G\). For every two different edges \(e\) and \(f\) of \(G\), let \(wt(e) \neq wt(f)\) where weight of \(e = xy\) is defined as \(wt(e)=|\xi(e) – \xi(x) – \xi(y)|\). Then \(\xi\) is called edge irregular total absolute difference \(k\)-labeling of \(G\). Let \(k\) be the minimum integer for which there is a graph \(G\) with edge irregular total absolute difference labeling. This \(k\) is called the total absolute difference edge irregularity strength of the graph \(G\), denoted \(tades(G)\). We compute \(tades\) of \(SC_{n}\), disjoint union of grid and zigzag graph.
A total dominator coloring of \(G\) without isolated vertex is a proper coloring of the vertices of \(G\) in which each vertex of \(G\) is adjacent to every vertex of some color class. The total dominator chromatic number \(\chi^t_d(G)\) of \(G\) is the minimum number of colors among all total dominator coloring of \(G\). In this paper, we will give the polynomial time algorithms to computing the total dominator coloring number for \(P_4\)-reducible and \(P_4\)-tidy graphs.
An \(H\)-(a,d)-antimagic labeling in a \(H\)-decomposable graph \(G\) is a bijection \(f: V(G)\cup E(G)\rightarrow {\{1,2,…,p+q\}}\) such that \(\sum f(H_1),\sum f(H_2),\cdots, \sum f(H_h)\) forms an arithmetic progression with difference \(d\) and first element \(a\). \(f\) is said to be \(H\)-\(V\)-super-\((a,d)\)-antimagic if \(f(V(G))={\{1,2,…,p\}}\). Suppose that \(V(G)=U(G) \cup W(G)\) with \(|U(G)|=m\) and \(|W(G)|=n\). Then \(f\) is said to be \(H\)-\(V\)-super-strong-\((a,d)\)-antimagic labeling if \(f(U(G))={\{1,2,…,m\}}\) and \(f(W(G))={\{m+1,m+2,…,(m+n=p)\}}\). A graph that admits a \(H\)-\(V\)-super-strong-\((a,d)\)-antimagic labeling is called a \(H\)-\(V\)-super-strong-\((a,d)\)-antimagic decomposable graph. In this paper, we prove that complete bipartite graphs \(K_{m,n}\) are \(H\)-\(V\)-super-strong-\((a,d)\)-antimagic decomposable with both \(m\) and \(n\) are even.
A Grundy \(k\)-coloring of a graph \(G\) is a proper \(k\)-coloring of vertices in \(G\) using colors \(\{1, 2, \cdots, k\}\) such that for any two colors \(x\) and \(y\), \(x<y\), any vertex colored \(y\) is adjacent to some vertex colored \(x\). The First-Fit or Grundy chromatic number (or simply Grundy number) of a graph \(G\), denoted by \(\Gamma \left(G\right)\), is the largest integer \(k\), such that there exists a Grundy \(k\)-coloring for \(G\). It can be easily seen that \(\Gamma \left(G\right)\) equals to the maximum number of colors used by the greedy (or First-Fit) coloring of \(G\). In this paper, we obtain the Grundy chromatic number of Cartesian Product of path graph, complete graph, cycle graph, complete graph, wheel graph and star graph.
Determining the Tutte polynomial \(T(G;x,y)\) of a graph network \(G\) is a challenging problem for mathematicians, physicians, and statisticians. This paper investigates a self-similar network model \(M(t)\) and derives its Tutte polynomial. In addition, we evaluate exact explicit formulas for the number of acyclic orientations and spanning trees of it as applications of the Tutte polynomial. Finally, we use the derived \(T(M(t);x,y)\) to obtain the Tutte polynomial of another self-similar model \(N(t)\) presented in [1] and correct the main result discussed in [1] by Ma et al. and test our result numerically by using Matlab.
A vertex-colouring of a graph \(\Gamma\) is rainbow vertex connected if every pair of vertices \((u,v)\) in \(\Gamma\) there is a \(u-v\) path whose internal vertices have different colours. The rainbow vertex connection number of a graph \(\Gamma\), is the minimum number of colours needed to make \(\Gamma\) rainbow vertex connected, denoted by \(rvc(\Gamma)\). Here, we study the rainbow vertex connection numbers of middle and total graphs. A total-colouring of a graph \(\Gamma\) is total rainbow connected if every pair of vertices \((u,v)\) in \(\Gamma\) there is a \(u-v\) path whose edges and internal vertices have different colours. The total rainbow connection number of \(\Gamma\), is the minimum number of colours required to colour the edges and vertices of \(\Gamma\) in order to make \(\Gamma\) total rainbow connected, denoted by \(trc(\Gamma)\). In this paper, we also research the total rainbow connection numbers of middle and total graphs.
The harmonic index \(H(G)\) of a graph \(G\) is defined as the sum of the weights \(\frac{2}{d_{u}+ d_{v}}\) of all edges \(uv\) of \(G\), where \(d_{u}\) denotes the degree of a vertex \(u\). Delorme et al. [1] (2002) put forward a conjecture concerning the minimum Randić index among all connected graphs with \(n\) vertices and the minimum degree at least \(k\). Motivated by this paper, a conjecture related to the minimum harmonic index among all connected graphs with \(n\) vertices and the minimum degree at least \(k\) was posed in [2]. In this work, we show that the conjecture is true for a connected graph on $n$ vertices with \(k\) vertices of degree \(n-1\), and it is also true for a \(k\)-tree. Moreover, we give a shorter proof of Liu’s result [3].
Let \(L\) be a unital ring with characteristic different from \(2\) and \(\mathcal{O}(L)\) be an algebra of Octonion over \(L\). In the present article, our attempt is to present the characterization as well as the matrix representation of some variants of derivations on \(\mathcal{O}(L)\). The matrix representation of Lie derivation of \(\mathcal{O}(L)\) and its decomposition in terms of Lie derivation and Jordan derivation of \(L\) and inner derivation of \(\mathcal{O}\) is presented. The result about the decomposition of Lie centralizer of \(\mathcal{O}\) in terms of Lie centralizer and Jordan centralizer of \(L\) is given. Moreover, the matrix representation of generalized Lie derivation (also known as \(D\)-Lie derivation) of \(\mathcal{O}(L)\) is computed.
A sum divisor cordial labeling of a graph \(G\) with vertex set \(V(G)\) is a bijection \(f\) from \(V(G)\) to \(\{1,2,\cdots,|V(G)|\}\) such that an edge \(uv\) is assigned the label \(1\) if \(2\) divides \(f(u)+f(v)\) and \(0\) otherwise; and the number of edges labeled with \(1\) and the number of edges labeled with \(0\) differ by at most \(1\). A graph with a sum divisor cordial labeling is called a sum divisor cordial graph. In this paper, we discuss the sum divisor cordial labeling of transformed tree related graphs.
For a graph \(G\) and a positive integer \(k\), a royal \(k\)-edge coloring of \(G\) is an assignment of nonempty subsets of the set \(\{1, 2, \ldots, k\}\) to the edges of \(G\) that gives rise to a proper vertex coloring in which the color assigned to each vertex \(v\) is the union of the sets of colors of the edges incident with \(v\). If the resulting vertex coloring is vertex-distinguishing, then the edge coloring is a strong royal \(k\) coloring. The minimum positive integer \(k\) for which a graph has a strong royal \(k\)-coloring is the strong royal index of the graph. The primary emphasis here is on strong royal colorings of trees.
The coloring of all the edges of a graph \(G\) with the minimum number of colors, such that the adjacent edges are allotted a different color is known as the proper edge coloring. It is said to be equitable, if the number of edges in any two color classes differ by atmost one. In this paper, we obtain the equitable edge coloring of splitting graph of \(W_n\), \(DW_n\) and \(G_n\) by determining its edge chromatic number.
Let us consider a~simple connected undirected graph \(G=(V,E)\). For a~graph \(G\) we define a~\(k\)-labeling \(\phi: V(G)\to \{1,2, \dots, k\}\) to be a~distance irregular vertex \(k\)-labeling of the graph \(G\) if for every two different vertices \(u\) and \(v\) of \(G\), one has \(wt(u) \ne wt(v),\) where the weight of a~vertex \(u\) in the labeling \(\phi\) is \(wt(u)=\sum\limits_{v\in N(u)}\phi(v),\) where \(N(u)\) is the set of neighbors of \(u\). The minimum \(k\) for which the graph \(G\) has a~distance irregular vertex \(k\)-labeling is known as distance irregularity strength of \(G,\) it is denoted as \(dis(G)\). In this paper, we determine the exact value of the distance irregularity strength of corona product of cycle and path with complete graph of order \(1,\) friendship graph, Jahangir graph and helm graph. For future research, we suggest some open problems for researchers of the same domain of study.
Elimination ideals are monomial ideals associated to simple graphs, not necessarily square–free, was introduced by Anwar and Khalid. These ideals are Borel type. In this paper, we obtain sharp combinatorial upper bounds of the Castelnuovo–Mumford regularity of elimination ideals corresponding to certain family of graphs.
Let \(G\) be a simple connected graph with vertex set \(V\) and diameter \(d\). An injective function \(c: V\rightarrow \{1,2,3,\ldots\}\) is called a radio labeling of \(G\) if \({|c(x) c(y)|+d(x,y)\geq d+1}\) for all distinct \(x,y\in V\), where \(d(x,y)\) is the distance between vertices \(x\) and \(y\). The largest number in the range of \(c\) is called the span of the labeling \(c\). The radio number of \(G\) is the minimum span taken over all radio labelings of \(G\). For a fixed vertex \(z\) of \(G\), the sequence \((l_1,l_2,\ldots,l_r)\) is called the level tuple of \(G\), where \(l_i\) is the number of vertices whose distance from \(z\) is \(i\). Let\(J^k(l_1,l_2,\ldots,l_r)\) be the wedge sum (i.e. one vertex union) of \(k\geq2\) graphs having same level tuple \((l_1,l_2,\ldots,l_r)\). Let \(J(\frac{l_1}{l’_1},\frac{l_2}{l’_2},\ldots,\frac{l_r} {l’_r})\) be the wedge sum of two graphs of same order, having level tuples \((l_1,l_2,\ldots,l_r)\) and \((l’_1,l’_2,\ldots,l’_r)\). In this paper, we compute the radio number for some sub-families of \(J^k(l_1,l_2,\ldots,l_r)\) and \(J(\frac{l_1}{l’_1},\frac{l_2}{l’_2},\ldots,\frac{l_r}{l’_r})\).
An antipodal labeling is a function \(f\ \)from the vertices of \(G\) to the set of natural numbers such that it satisfies the condition \(d(u,v) + \left| f(u) – f(v) \right| \geq d\), where d is the diameter of \(G\ \)and \(d(u,v)\) is the shortest distance between every pair of distinct vertices \(u\) and \(v\) of \(G.\) The span of an antipodal labeling \(f\ \)is \(sp(f) = \max\{|f(u) – \ f\ (v)|:u,\ v\, \in \, V(G)\}.\) The antipodal number of~G, denoted by~an(G), is the minimum span of all antipodal labeling of~G. In this paper, we determine the antipodal number of Mongolian tent and Torus grid.
Two graphs are defined to be adjointly equivalent if their complements are chromatically equivalent. Recently, we introduced a new invariant of a graph \(G\), denoted as \(R_5(G)\). Using this invariant and the properties of the adjoint polynomials, we completely determine the adjoint equivalence class of \(\psi_n^3({n-3,1})\). According to the relations between adjoint polynomial and chromatic polynomial, we also simultaneously determine the chromatic equivalence class of \(\psi_n^3({n-3,1})\).
In this article, we prove a conjecture about the equality of two generating functions described in “From Parking Functions to Gelfand Pairs” (Aker, Can, 2012) attached to two sets whose cardinalities are given by Catalan numbers. We establish a combinatorial bijection between the two sets on which the two generating functions were based.
Let \(G\) be a finite cyclic group. Every sequence \(S\) of length \(l\) over \(G\) can be written in the form \(S = (x_1g) + \cdots + (x_lg)\), where \(g \in G\) and \(x_1, \ldots, x_l \in [1, ord(g)]\), and the index \(ind(S)\) of \(S\) is defined to be the minimum of \((x_1 + \cdots + x_l)/ord(g)\) over all possible \(g \in G\) such that \(\langle g \rangle = G\). Recently, the second and third authors determined the index of any minimal zero-sum sequence \(S\) of length \(5\) over a cyclic group of a prime order where \(S =g^2 \cdot (x_2g)\cdot (x_3g)\cdot (x_4g)\). In this paper, we determine the index of any minimal zero-sum sequence \(S\) of length \(5\) over a cyclic group of a prime power order. It is shown that if \(G = \langle g \rangle\) is a cyclic group of prime power order \(n = p^{\mu}\) with \(p \geq 7\) and \(\mu \geq 2\), and \(S = (x_1g) \cdot (x_2g) \cdot (x_3g) \cdot (x_4g) \cdot (x_5g)\) with \(x_1 = x_2\) is a minimal zero-sum sequence with \(\gcd(n, x_1, x_2, x_3, x_4, x_5) = 1\), then \(ind(S) = 2\) if and only if \(S = (mg) \cdot (mg) \cdot (m\frac{n-1}{2}g) \cdot (m\frac{n+3}{2}g) \cdot (m(n-3)g)\) where \(m\) is a positive integer such that \(\gcd(m,n) = 1\).
Let \(G\) be a graph with vertex set \(V(G)\). For any integer \(k \geq 1\), a signed \(k\)-dominating function is a function \(f: V(G) \rightarrow \{-1, 1\}\) satisfying \(\sum_{x \in N[v]} f(t) \geq k\) for every \(v \in V(G)\), where \(N[v]\) is the closed neighborhood of \(v\). The minimum of the values \(\sum_{v \in V(G)} f(v)\), taken over all signed \(k\)-dominating functions \(f\), is called the signed \(k\)-domination number. In this note, we present some new lower bounds on the signed \(k\)-domination number of a graph. Some of our results improve known bounds.
In this paper, we define and study the \(k\)-order Gaussian Fibonacci and Lucas numbers with boundary conditions. We identify and prove the generating functions, the Binet formulas, the summation formulas, matrix representation of \(k\)-order Gaussian Fibonacci numbers, and some significant relationships between \(k\)-order Gaussian Fibonacci and \(k\)-order Lucas numbers, connecting them with usual \(k\)-order Fibonacci numbers.
A vertex-colored path is vertex-rainbow if its internal vertices have distinct colors. For a connected graph \(G\) with connectivity \(\kappa(G)\) and an integer \(k\) with \(1 \leq k \leq \kappa(G)\), the rainbow vertex \(k\)-connectivity of \(G\) is the minimum number of colors required to color the vertices of \(G\) such that any two vertices of \(G\) are connected by \(k\) internally vertex-disjoint vertex-rainbow paths. In this paper, we determine the rainbow vertex \(k\)-connectivities of all small cubic graphs of order \(8\) or less.
For a simple graph \(G = (V, E)\), a vertex labeling \(\alpha: V \rightarrow \{1, 2, \ldots, k\}\) is called a \(k\)-labeling. The weight of an edge \(xy\) in \(G\), denoted by \(w_\phi(xy)\), is the sum of the labels of end vertices \(x\) and \(y\), i.e., \(w_\phi(xy) = \phi(x) + \phi(y)\). A vertex \(k\)-labeling is defined to be an edge irregular \(k\)-labeling of the graph \(G\) if for every two different edges \(e\) and \(f\) there is \(w_\phi(e) \neq w_\phi(f)\). The minimum \(k\) for which the graph \(G\) has an edge irregular \(k\)-labeling is called the edge irregularity strength of \(G\), denoted by \(\mathrm{es}(G)\). In this paper, we determine the exact value for certain families of graphs with path \(P_2\).
We give a \(q\)-analogue of some Dixon-like summation formulas obtained by Gould and Quaintance [Fibonacci Quart. 48 (2010), 56-61] and Chu [Integral Transforms Spec. Funct. 23 (2012), 251-261], respectively. For example, we prove that
\(\sum\limits_{k=0}^{2m} (-1)^{m-k} q^{\binom{m-k}{2}} \binom{2m} {k} \binom{x+k} {2m+r}\binom{x+2m-k} {2m+r}\) = \(\frac{q^{m(x-m-r)}\binom{2m}{m}}{\binom{2m+r}{m}}\binom{x}{m+r}\binom{x+m}{m+r}\) where \(\binom{x}{k}\) denotes the \(q\)-binomial coefficient.
A pentangulation is a simple plane graph such that each face is bounded by a cycle of length \(5\). We consider two diagonal transformations in pentangulations, called \(\mathcal{A}\) and \(\mathcal{B}\). In this paper, we shall prove that any two pentangulations with the same number of vertices can be transformed into each other by \(\mathcal{A}\) and \(\mathcal{B}\). In particular, if they are not isomorphic to a special pentangulation, then we do not need \(\mathcal{B}\).
The harmonic index \(H(G)\) of a graph \(G\) is defined as the sum of the weights of all edges \(uv\) of \(G\), where the weight of \(uv\) is \(\frac{2}{d(u) + d(v)}\), with \(d(u)\) denoting the degree of the vertex \(u\) in \(G\). In this work, we compute the harmonic index of a graph with a cut-vertex and with more than one cut-vertex. As an application, this topological index is computed for Bethe trees and dendrimer trees. Also, the harmonic indices of Fasciagraph and a special type of trees, namely, polytree, are computed.
Let \(G^{\sigma}\) be an oriented graph obtained by assigning an orientation \(\sigma\) to the edge set of a simple undirected graph \(G\). Let \(S(G^{\sigma})\) be the skew adjacency matrix of \(G^{\sigma}\). The skew energy of \(G^{\sigma}\) is defined as the sum of the absolute values of all eigenvalues of \(S(G^{\sigma})\). In this paper, we give the skew energy order of a family of digraphs and determine the oriented bicyclic graphs of order \(n \geq 13\) with the first five largest skew energies, which extends the results of the paper [X. Shen, Y. Hou, C. Zhang, Bicyclic digraphs with extremal skew energy, Electron. J. Linear Algebra 23 (2012) 340-355].
Let \(P_n\) denote the \(n\)-th Catalan-Larcombe-French number. Recently, the \(2\)-log-convexity of the Catalan-Larcombe-French sequence was proved by Sun and Wu. Moreover, they also conjectured that the quotient sequence \(\{\frac{P_{n}}{P_{n-1}}\}_{n= 0}^\infty\) of the Catalan-Larcombe-French sequence is log-concave. In this paper, this conjecture is confirmed by utilizing the upper and lower bounds for \(\frac{P_{n}}{P_{n-1}}\) and finding a middle function \(f(n)\).
It is claimed in [13] that the metric dimension of the Möbius ladder \(M_n\) is \(3\) when \(n \not\equiv 2 \pmod{8}\), but it is wrong; we give a counterexample when \(n \equiv 6 \pmod{8}\). In this paper, we not only give the correct metric dimension in this case but also solve the open problem regarding the metric dimension of \(M_n\) when \(n \equiv 2 \pmod{8}\). Moreover, we conclude that \(M_n\) has two subfamilies with constant metric dimensions.
An edge-colored graph \(G\) is (strong) rainbow connected if any two vertices are connected by a (geodesic) path whose edges have distinct colors. The (strong) rainbow connection number of a connected graph \(G\), denoted by \(\mathrm{src}(G)\) (resp. \(\mathrm{rc}(G)\)), is the smallest number of colors that are needed in order to make \(G\) (strong) rainbow connected. The join \(P_m \vee P_n\) of \(P_m\) and \(P_n\) is the graph consisting of \(P_m\cup P_n\), and all edges between every vertex of \(P_m\) and every vertex of \(P_n\), where \(P_m\) (resp. \(P_n\)) is a path of \(m\) (resp. \(n\)) vertices. In this paper, the precise values of \(\mathrm{rc}(P_m \vee P_n)\) and \(\mathrm{src}(P_m \vee P_n)\) are given for any positive integers \(m\) and \(n\).
Let \(MG(i,n)\) be a connected molecular graph without multiple edges on \(n\)vertices whose minimum degree of vertices is \(i\), where \(i \leq i \leq 4\). One of the newest topological indices is the first Geometric-Arithmetic index. In this paper, we determine the graph with the minimum and the maximum value of the first Geometric-Arithmetic index in the family of graphs \(M{G}(i,n)\),\(l\leq i \leq 3\).
Two graphs are said to be Tutte-equivalent if their Tutte polynomials are equal. In this paper, we provide several different constructions for Tutte-equivalent graphs, including some that are not self-complementary but Tutte-equivalent to their complements (the Akiyama-Harary problem) and some “large” Tutte-equivalent graphs obtained from “small” Tutte-equivalent graphs by \(2\)-sum operations.
Let \(s(n, k) = \binom{6k}{3k} \binom{3k}{k} (\binom{3(n-k)}{n-k} / (2n-1) \binom{3n}{n})\). Recently, Guo confirmed a conjecture of \(Z.-W\). Sun by showing that \(s(n, k)\) is an integer for \(k = 0, 1, \ldots, n\). Let \(d = (3n + 2) / \gcd(3n + 2, 2n – 1)\). In this paper, we prove that \(s(n, k)\) is a multiple of the odd part of \(d\) for \(k = 0, 1, \ldots, n\). Furthermore, if \(\gcd(k, n) = 1\), then \(s(n, k)\) is also a multiple of \(n\). We also show that the \(2\)-adic order of \(s(n, k)\) is at least the sum of the digits in the binary expansion of \(3n\).
For any non-trivial abelian group \(A\) under addition, a graph \(G\) is said to be strong \(A\)-magic if there exists a labeling \(f\) of the edges of \(G\) with non-zero elements of \(A\) such that the vertex labeling \(f^+\) defined as \(f^+(v) = \sum f(uv)\) taken over all edges \(uv\) incident at \(v\) is a constant, and the constant is same for all possible values of \(|V(G)|\). A graph is said to be strong \(A\)-magic if it admits strong \(A\)-magic labeling. In this paper, we consider \((\mathbb{Z}_4, +)\) as an abelian group and we prove strong \(\mathbb{Z}_4\)-magic labeling for various graphs and generalize strong \(\mathbb{Z}_{4p}\)-magic labeling for those graphs. The graphs which admit strong \(\mathbb{Z}_{4p}\)-magic labeling are called as strong \(\mathbb{Z}_{4p}\)-magic graphs.
The well-known Mantel’s Theorem states that a graph on \(n\) vertices and \(m\) edges contains a triangle if \(m > \frac{n^2}{4}\). Nosal proved that every graph on \(m\) edges contains a triangle if the spectral radius \(\lambda_1 > \sqrt{m}\), which is a spectral analog of Mantel’s Theorem. Furthermore, by using Motzkin-Straus Inequality, Nikiforov sharpened Nosal’s result and characterized the extremal graphs when the equality holds. Our first contribution in this note is to give two new proofs of the spectral concise Mantel’s Theorem due to Nikiforov (without help of Motzkin-Straus Inequality). Nikiforov also obtained some results concerning the existence of consecutive cycles and spectral radius. Second, we prove a theorem concerning the existence of consecutive even cycles and spectral radius, which slightly improves a result of Nikiforov. At last, we focus on spectral radius inequalities. Hong proved his famous bound for spectral radius. Later, Hong, Shu, and Fang generalized Hong’s bound to connected graphs with given minimum degree. By using quite different techniques, Nikiforov proved Hong et al.’s bound for general graphs independently. In this note, we prove a new spectral inequality by applying the technique of Nikiforov. Our result extends Stanley’s spectral inequality.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.