Recent zbMATH articles in MSC 05https://zbmath.org/atom/cc/052021-01-08T12:24:00+00:00WerkzeugA note on the Laplacian resolvent energy, Kirchhoff index and their relations.https://zbmath.org/1449.051832021-01-08T12:24:00+00:00"Zogić, Emir"https://zbmath.org/authors/?q=ai:zogic.emir"Glogić, Edin"https://zbmath.org/authors/?q=ai:glogic.edinSummary: Let \(G\) be a simple graph of order \(n\) and let \(L\) be its Laplacian matrix. Eigenvalues of the matrix \(L\) are denoted by \(\mu_1, \mu_2,\dots, \mu_n\) and it is assumed that \(\mu_1\ge \mu_2\ge \dots\ge \mu_n\). The Laplacian resolvent energy and Kirchhoff index of the graph \(G\) are defined as \(\mathrm{RL}(G) = \sum^n_{i=1} \frac{1}{n+1-\mu_i}\) and \(\mathrm{Kf}(G) = n \sum_{n-1}^{n-1}\frac{1}{\mu_i}\), respectively. In this paper, we derive some bounds on the invariant \(\mathrm{RL}(G)\) and establish a relation between \(\mathrm{RL}(G)\) and \(\mathrm{Kf}(G)\).Network public opinion propagation model based on interest matching in multiple relationship social network.https://zbmath.org/1449.910862021-01-08T12:24:00+00:00"Sun, Gengxin"https://zbmath.org/authors/?q=ai:sun.gengxin"Bin, Sheng"https://zbmath.org/authors/?q=ai:bin.shengSummary: The relationship between user profiles and the data of microblog content in Sina microblog was obtained by programming and web crawler, and a variety of explicit or implicit relationships between microblog users were discovered by using data mining. On the basis of this, a semi-supervised user interest matching prediction algorithm was proposed. According to the individual state division method of compartment model, a network public opinion propagation model is constructed based on user interest matching through state transition analysis and inference of state transition probability. The results show that the model can well describe the laws of public opinion propagation in social networks, and reproduce the real propagation process of network public opinion in the social network from the perspective of complex networks.Reciprocal matrices: properties and approximation by a transitive matrix.https://zbmath.org/1449.150812021-01-08T12:24:00+00:00"Bebiano, Natália"https://zbmath.org/authors/?q=ai:bebiano.natalia"Fernandes, Rosário"https://zbmath.org/authors/?q=ai:fernandes.rosario"Furtado, Susana"https://zbmath.org/authors/?q=ai:furtado.susanaSummary: Reciprocal matrices and, in particular, transitive matrices, appear in several applied areas. Among other applications, they have an important role in decision theory in the context of the analytical hierarchical process, introduced by \textit{T. L. Saaty} [J. Math. Psychol. 15, 234--281 (1977; Zbl 0372.62084)]. In this paper, we study the possible ranks of a reciprocal matrix and give a procedure to construct a reciprocal matrix with the rank and the off-diagonal entries of an arbitrary row (column) prescribed. We apply some techniques from graph theory to the study of transitive matrices, namely to determine the maximum number of equal entries, and distinct from \(\pm 1\), in a transitive matrix. We then focus on the \(n\)-by-\(n\) reciprocal matrix, denoted by \(C(n, x)\), with all entries above the main diagonal equal to \(x>0\). We show that there is a Toeplitz transitive matrix and a transitive matrix preserving the maximum possible number of entries of \(C(n, x)\), whose distances to \(C(n, x)\), measured in the Frobenius norm, are smaller than the one of the transitive matrix proposed by Saaty, constructed from the right Perron eigenvector of \(C(n, x)\). We illustrate our results with some numerical examples.Some properties of the neighborhood first Zagreb index.https://zbmath.org/1449.050662021-01-08T12:24:00+00:00"Réti, Tamás"https://zbmath.org/authors/?q=ai:reti.tamas"Ali, Akbar"https://zbmath.org/authors/?q=ai:ali.akbar.1|ali.akbar"Varga, Péter"https://zbmath.org/authors/?q=ai:varga.peter"Bitay, Enikő"https://zbmath.org/authors/?q=ai:bitay.enikoSummary: The neighborhood first Zagreb index \((N M_1)\) has been recently introduced for characterizing the topological structure of molecular graphs. In this study, we present some sharp bounds on the index \(NM_1\) and establish its relations with the first and second Zagreb indices in case of some special graphs. It is verified and demonstrated on examples that in several cases, the index \(NM_1\) outperforms the discriminating performance of the majority of traditional degree-based molecular descriptors (for example, Randić connectivity index, the sum-connectivity index, the harmonic index, the geometric-arithmetic index, etc.).On the general zeroth-order Randić index of bargraphs.https://zbmath.org/1449.050512021-01-08T12:24:00+00:00"Elumalai, Suresh"https://zbmath.org/authors/?q=ai:elumalai.suresh"Mansour, Toufik"https://zbmath.org/authors/?q=ai:mansour.toufikSummary: In this paper, we study the bargraphs in the perspective of a well-known topological index, namely the general zeroth-order Randić index. More precisely, we show that the expected value of the general zeroth-order Randić index over all bargraphs with \(n\) cells is \(\frac{n}{3}(3^{\alpha +1}+ 2^{\alpha} + 3 \cdot 2^{2\alpha -1})\) when \(n\) is large enough, where \(\alpha\) is a non-zero real number.Semi-polytope decomposition of a generalized permutohedron.https://zbmath.org/1449.050192021-01-08T12:24:00+00:00"Oh, Suho"https://zbmath.org/authors/?q=ai:oh.suhoSummary: In this short note, we show explicitly how to decompose a generalized permutohedron into semi-polytopes.Staircase tableaux and an alternative matrix formula for steady state probabilities in the asymmetric exclusion process \((q=1)\).https://zbmath.org/1449.050092021-01-08T12:24:00+00:00"Gonzales, Ken Joffaniel M."https://zbmath.org/authors/?q=ai:gonzales.ken-joffaniel-m"Celeste, Richell O."https://zbmath.org/authors/?q=ai:celeste.richell-o"Corcino, Roberto B."https://zbmath.org/authors/?q=ai:corcino.roberto-bagsarsaSummary: We derive an alternative matrix formula for steady state probabilities in the asymmetric exclusion process where particles hop at equal rates inside a one-dimensional finite lattice. The result is derived using the combinatorial properties of staircase tableaux and alternative tableaux.The structure of Eta graph with \(|V (g)| + 4\) maximum matchings.https://zbmath.org/1449.052182021-01-08T12:24:00+00:00"Yang, Chunxia"https://zbmath.org/authors/?q=ai:yang.chunxia"Wu, Lihao"https://zbmath.org/authors/?q=ai:wu.lihaoSummary: Eta graph is a graph got by adding two odd pending paths on an odd cycle. Starting from the construction of the Eta graph, we get ten types of structures of Eta graphs with \(|V (G)| + 4\) maximum matchings.On graph associated to co-ideals of commutative semirings.https://zbmath.org/1449.160992021-01-08T12:24:00+00:00"Talebi, Yahya"https://zbmath.org/authors/?q=ai:talebi.yahya"Darzi, Atefeh"https://zbmath.org/authors/?q=ai:darzi.atefehSummary: Let \(R\) be a commutative semiring with non-zero identity. In this paper, we introduce and study the graph \(\Omega(R)\) whose vertices are all elements of \(R\) and two distinct vertices \(x\) and \(y\) are adjacent if and only if the product of the co-ideals generated by \(x\) and \(y\) is \(R\). Also, we study the interplay between the graph-theoretic properties of this graph and some algebraic properties of semirings. Finally, we present some relationships between the zero-divisor graph \(\Gamma(R)\) and \(\Omega(R)\).On strongly regular graphs with \(m_2 = qm_3\) and \(m_3 = qm_2\) for \(q = 5,6,7,8\).https://zbmath.org/1449.051682021-01-08T12:24:00+00:00"Lepović, Mirko"https://zbmath.org/authors/?q=ai:lepovic.mirkoSummary: We say that a regular graph \(G\) of order \(n\) and degree \(r \geq 1\) (which is not the complete graph) is strongly regular if there exist non-negative integers \(\tau\) and \(\theta\) such that \(|S_i \cap S_j|= \tau\) for any two adjacent vertices \(i\) and \(j\), and \(|S_i \cap S_j|= \theta\) for any two distinct non-adjacent vertices \(i\) and \(j\), where \(S_k\) denotes the neighborhood of the vertex \(k\). Let \(\lambda_1=r\), \(\lambda_2\) and \(\lambda 3\) be the distinct eigenvalues of a connected strongly regular graph. Let \(m_1=1\), \(m_2\) and \(m_3\) denote the multiplicity of \(r\), \( \lambda_2\) and \(\lambda_3\), respectively. We describe the parameters \(n\), \(r\), \( \tau\) and \(\theta\) for strongly regular graphs with \(m_2=qm_3\) and \(m_3=qm_2\) for \(q=5,6,7,8\).Identities generated from the genus theory of real quadratic fields.https://zbmath.org/1449.050292021-01-08T12:24:00+00:00"Shen, Lichien"https://zbmath.org/authors/?q=ai:shen.lichienSummary: Applying the genus theory of Gauss on the real quadratic fields, we derive identities involving quadratic forms and genus characters.Normalized Laplacian spectrum of two classes of hexagonal systems and their applications.https://zbmath.org/1449.051722021-01-08T12:24:00+00:00"Shi, Yinfang"https://zbmath.org/authors/?q=ai:shi.yinfang"Zhang, You"https://zbmath.org/authors/?q=ai:zhang.you"Wen, Fei"https://zbmath.org/authors/?q=ai:wen.feiSummary: Let \({F_n}\) and \({M_n}\) be hexacyclic system graph and Möbius hexacyclic system graph with \(n\) hexagons, respectively. Firstly, with the help of characteristic root and the determinant of cyclic matrix, the normalized Laplacian polynomials of graphs \({F_n}\) and \({M_n}\) were given. Secondly, the normalized Laplacian spectra of graphs \({F_n}\) and \({M_n}\) were obtained. Finally, we gave the Randić energies of graphs \({F_n}\) and \({M_n}\) and a sharp upper bound of RE (\({F_n}\)) and RE (\({M_n}\)), and also determined the number of spanning trees of the two graphs.Solving Ramsey number algorithm based on set theory.https://zbmath.org/1449.681442021-01-08T12:24:00+00:00"Bai, Yunxiao"https://zbmath.org/authors/?q=ai:bai.yunxiaoSummary: Aiming at the problem of low efficiency, high time-consuming and large error in solving Ramsey number by the traditional single-core DNA computer algorithm, the author proposed a Ramsey number algorithm based on set theory. The algorithm was based on the Phoenix++ system of the MapReduce model based on set theory. The author designed and optimized the Ramsey number algorithm for the complete graph under the single-core CPU. Data preprocessing, efficient task segmentation and key-value pair planning were performed during optimization. The parallel algorithm based on set theory in Phoenix++ system was obtained. The Ramsey number was solved by DNA computer algorithm and its numerical value was verified to solve the Ramsey number. The experimental results show that the number of image processed by the program increases with the increase of the vertices. The proposed method has high accuracy in solving the Ramsey number, better maximum acceleration ratio and execution efficiency, and strong computational performance.Stability of two-dimensional complex oscillator networks with time delay.https://zbmath.org/1449.342462021-01-08T12:24:00+00:00"Li, Xue"https://zbmath.org/authors/?q=ai:li.xue"Xu, Xu"https://zbmath.org/authors/?q=ai:xu.xu.2|xu.xuSummary: We consider the stability of two-dimensional complex oscillator network systems with time delay. By analyzing the stability switching criteria, we discuss the difference of the stability switching between complex and real systems. Extending the ring structure to the two-dimensional case makes it possible to generate or the storage visual patterns.Upper bound of quasi-Laplacian energy of \(H\)-join graphs.https://zbmath.org/1449.051822021-01-08T12:24:00+00:00"Zhou, Kunqiang"https://zbmath.org/authors/?q=ai:zhou.kunqiang"Wang, Weizhong"https://zbmath.org/authors/?q=ai:wang.weizhongSummary: Let \(\{1, 2, \dots, k\}\) be the vertex set of graph \(H\), the \(H\)-join graph (denoted by \({\vee_H} ({G_1}, {G_2}, \dots, {G_k})\)) is obtained on the basis of disjoint graphs \({G_1}, {G_2}, \dots, {G_k}\) and by joining each vertex of \({G_i}\) to each vertex of \({G_j}\) whenever \(i\) is adjacent to \(j\) in \(H\). Particularly, if \(H = {P_2}\), \({\vee_{P_2}} ({G_1}, {G_2})\) is the ordinary join graph \({G_1} \vee {G_2}\). By using the property of the Laplacian spectrum of \(H\)-join graphs, we mainly characterize the upper bound of the Laplacian-energy-like invariant energy of \(H\)-join graphs under certain restrictions for \(H\).Commuting conjugacy class graph of finite CA-groups.https://zbmath.org/1449.200062021-01-08T12:24:00+00:00"Salahshour, Mohammad Ali"https://zbmath.org/authors/?q=ai:salahshour.mohammad-ali"Ashrafi, Ali Reza"https://zbmath.org/authors/?q=ai:ashrafi.ali-rezaSummary: Let \(G\) be a finite nonabelian group. The commuting conjugacy class graph \(\Gamma(G)\) is a simple graph with the noncentral conjugacy classes of \(G\) as its vertex set and two distinct vertices \(X\) and \(Y\) in \(\Gamma(G)\) are adjacent if and only if there are \(x \in X\) and \(y \in Y\) with this property that \(xy = yx\). The aim of this paper is to obtain the structure of the commuting conjugacy class graph of finite CA-groups. It is proved that this graph is a union of some complete graphs. The commuting conjugacy class graph of certain groups are also computed.General vertex-distinguishing total colorings of corona graph of \(2{K_2} \vee {K_1}\).https://zbmath.org/1449.051032021-01-08T12:24:00+00:00"Li, Ting"https://zbmath.org/authors/?q=ai:li.ting"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangen"Wang, Zhiwen"https://zbmath.org/authors/?q=ai:wang.zhiwenSummary: With the help of the general vertex-distinguishing total colorings of a star, we discussed the general vertex-distinguishing total colorings of the corona graph of \(2{K_2} \vee {K_1}\). Under the general vertex-distinguishing total colorings of the star, the colorings of pendent edges of the star were in an ascending order and finally they expanded into the general vertex-distinguishing total colorings method of the corona graph of \(2{K_2} \vee {K_1}\). The general vertex-distinguishing total chromatic numbers of the corona graph depending on the number of pendent edges were got.Parallel algorithm for overlapping community detection in complex networks.https://zbmath.org/1449.910872021-01-08T12:24:00+00:00"Teng, Fei"https://zbmath.org/authors/?q=ai:teng.fei"Dai, Rongjie"https://zbmath.org/authors/?q=ai:dai.rongjie"Ren, Xiaochun"https://zbmath.org/authors/?q=ai:ren.xiaochunSummary: With the increasing size of complex networks, traditional detection methods are difficult to scale to larger networks. This paper proposes a parallel hierarchical link (PHLink) algorithm to discover overlapping communities. By studying the power-law degree distribution of complex networks, we distinguish the motivations of why two nodes intend to establish a connection so that the complexity for community detection can be reduced. PHLink is implemented using distributed computing for large-scale networks via graph segmentation and redundant storage. Experiments validate that PHLink can accurately discover network communities and the overlaps between them. For scale-free networks, removing 0.1\% of the hub nodes reduces the computation time by 94\%. Meanwhile, PHLink demonstrates good speed-up and scale-up on Hadoop, which can scale to very large complex networks with millions of edges.Oriented graphs of the bipartite graph under degree.https://zbmath.org/1449.051252021-01-08T12:24:00+00:00"Zhang, Xuefei"https://zbmath.org/authors/?q=ai:zhang.xuefei"Zheng, Suwen"https://zbmath.org/authors/?q=ai:zheng.suwen"Xia, Jing"https://zbmath.org/authors/?q=ai:xia.jing"Cao, Yipeng"https://zbmath.org/authors/?q=ai:cao.yipeng"Xu, Fei"https://zbmath.org/authors/?q=ai:xu.fei.3|xu.fei.2|xu.feiSummary: A graph is bipartite if its vertex set can be partitioned into two subsets \(X\) and \(Y\) such that every edge has one end in \(X\) and one end in \(Y\), such a partition \( (X,Y)\) is called a bipartition of the graph. A simple bipartite graph with bipartition \( (X,Y)\) is called a complete bipartite graph if every vertex in \(X\) is adjacent to every vertex in \(Y\). Furthermore, the complete bipartite graph is denoted by \({K_{m,n}}\) if \(|X| = m\) and \(|Y| = n\). It is known that if the in-degree of each vertex in an oriented graph of \({K_{n,n}}\) is \(a\) or \(b\), where \(a\) and \(b\) are two non-negative integers, then there exist two non-negative integers \(s\) and \(t\) satisfying the equations \(s + t = 2n\) and \(as + bt = {n^2}\). This paper investigates oriented graphs of \({K_{n,n}}\), and proves the following results. Let \(s\) and \(t\) be two arbitrary non-negative integers. For two non-negative integers \(a\) and \(b\) satisfying the equations \(s + t = 2n\) and \(as + bt = {n^2}\), there exists an oriented graph of \({K_{n,n}}\) such that the in-degree of each vertex is \(a\) or \(b\). This paper shows that the necessary condition is also sufficient for a complete bipartite graph \({K_{n,n}}\).Simulation research on ``The Belt and Road'' network game based on structural model of decision-making rules.https://zbmath.org/1449.910332021-01-08T12:24:00+00:00"Zhao, Changping"https://zbmath.org/authors/?q=ai:zhao.changping"Li, Rui"https://zbmath.org/authors/?q=ai:li.rui.1|li.rui.4|li.rui.3|li.rui.2|li.rui"Qi, Jianhua"https://zbmath.org/authors/?q=ai:qi.jianhua"Fan, Houming"https://zbmath.org/authors/?q=ai:fan.houmingSummary: Based on the bilateral trade data of ``The Belt and Road'' countries, the economic and trade cooperation network of ``The Belt and Road'' was established. On this basis, the structural model of decision-making rules was introduced to construct the quantitative model of network game combined with the actual situation of ``The Belt and Road'' national cooperation. Then, the following aspects were analyzed in this paper, including the influence of the type of decision-making structure, proportion of perceived non-Nash equilibrium, the noise perceived from others' choices, the noise of the participants' own choice, the neighbors' reward and the pressure on the betrayal from the network on the choice of ``The Belt and Road'' national game strategy. The relevant conclusions were tested by simulation method and the China's coping strategy was further discussed.Connectivity of minimum non-5-injectively colorable planar cubic graphs.https://zbmath.org/1449.051002021-01-08T12:24:00+00:00"Jin, Jing"https://zbmath.org/authors/?q=ai:jin.jing"Xu, Bao-Gang"https://zbmath.org/authors/?q=ai:xu.baogangSummary: Suppose that \(G\) is a planar cubic graph with \(\chi_i(G)>5\). We show that if \(\chi_i(H)<\chi_i(G)\) for each planar cubic graph \(H\) of order less than \(G\), then \(G\) is either a 3-connected simple planar cubic graph, or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings. This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.The classification of finite simple groups with some conditions.https://zbmath.org/1449.200072021-01-08T12:24:00+00:00"Wang, Lingli"https://zbmath.org/authors/?q=ai:wang.lingli"Zhang, Liangcai"https://zbmath.org/authors/?q=ai:zhang.liangcaiSummary: The prime graph of the finite nonabelain simple group is further investigated and the influence of vertex degrees on the structure was considered. Using number theory, the classification of complete prime graph and the adjacency criterion for the prime graph of the finite nonabelain simple groups, the classification of the finite nonabelain simple group \(G\) with complete prime graph components satisfying \(|G| < {10^{10}}\), \(7 \in \pi (G)\) and \({d_G} (7) = 1\) is obtained. The classification problem further completed the information of prime graph. And using this method, the classification of the finite nonabelain simple group with the other prime can also be solved.Rainbow mean colorings of graphs.https://zbmath.org/1449.050892021-01-08T12:24:00+00:00"Chartrand, Gary"https://zbmath.org/authors/?q=ai:chartrand.gary"Hallas, James"https://zbmath.org/authors/?q=ai:hallas.james"Salehi, Ebrahim"https://zbmath.org/authors/?q=ai:salehi.ebrahim"Zhang, Ping"https://zbmath.org/authors/?q=ai:zhang.ping.1|zhang.ping.6Summary: A mean coloring of a connected graph \(G\) of order 3 or more is an edge coloring \(c\) of \(G\) with positive integers where the average of the colors of the edges incident with each vertex \(v\) of \(G\) is an integer. This average is the chromatic mean of \(v\). If distinct vertices have distinct chromatic means, then \(c\) is called a rainbow mean coloring of \(G\). The maximum vertex color in a rainbow mean coloring \(c\) of \(G\) is the rainbow chromatic mean index of \(c\) and the rainbow chromatic mean index of the graph \(G\) is the minimum chromatic mean index among all rainbow mean colorings of \(G\). It is shown that the rainbow chromatic mean index exists for every connected graph of order 3 or more. The rainbow chromatic mean index is determined for paths, cycles, complete graphs, and stars.Structure evolution analysis based on role discovery in dynamic information networks.https://zbmath.org/1449.680542021-01-08T12:24:00+00:00"Feng, Bingqing"https://zbmath.org/authors/?q=ai:feng.bingqing"Hu, Shaolin"https://zbmath.org/authors/?q=ai:hu.shaolin"Guo, Dong"https://zbmath.org/authors/?q=ai:guo.dong"Zhong, Xiaoge"https://zbmath.org/authors/?q=ai:zhong.xiaoge"Li, Peiyu"https://zbmath.org/authors/?q=ai:li.peiyuSummary: Dynamic information network is a new challenging problem in the field of current complex networks. Research on network evolution contributes to analyzing the network structure, understanding the characteristics of the network, and finding hidden network evolution rules, which has important theoretical significance and application value. The study of the network structure evolution is of great importance in getting a comprehensive understanding of the behavior trend of complex systems. However, the network structure is difficult to represent and quantify. And the evolution of dynamic networks is temporal, complex, and changeable, which increases the difficulty in analysis. This study introduces ``role'' to quantify the structure of dynamic networks and proposes a role-based model, which provides a new idea for the evolution analysis and prediction of network structure. As for the model, two methods to explain the role are given. To predict the role distributions of dynamic network nodes in future time, this study transforms the problem of dynamic network structure prediction into role prediction, which can represent the structural feature. The model extracts properties from historical snapshots of sub-network as the training data and predicts the future role's distributions of dynamic network by using the vector autoregressive method. This study also proposes the method of dynamic network structure prediction based on latent roles (LR-DNSP). This method not only overcomes the drawback of existing methods based on transfer matrix while ignoring the time factor, but also takes into account of possible dependencies between multiple forecast targets. Experimental results show that the LR-DNSP outperforms existing methods in prediction accuracy.The bounds of Merrifield-Simmons indices of the \(n\)-hypercube.https://zbmath.org/1449.052042021-01-08T12:24:00+00:00"Sheng, Jiming"https://zbmath.org/authors/?q=ai:sheng.jiming"Shen, Yanjun"https://zbmath.org/authors/?q=ai:shen.yanjunSummary: In this paper, using the isomorphic relation between the hypercube and the Hasse diagram of the power set of a finite set, we continue to study the upper and lower bounds of Merrifield-Simmons indices of the \(n\)-hypercube. When \(k > 5\), the upper and lower bounds of the \(k\)-independent sets of the \(n\)-hypercube are obtained.Generalized public transportation scheduling using max-plus algebra.https://zbmath.org/1449.150662021-01-08T12:24:00+00:00"Subiono"https://zbmath.org/authors/?q=ai:subiono.s"Fahim, Kistosil"https://zbmath.org/authors/?q=ai:fahim.kistosil"Adzkiya, Dieky"https://zbmath.org/authors/?q=ai:adzkiya.diekySummary: In this paper, we discuss the scheduling of a wide class of transportation systems. In particular, we derive an algorithm to generate a regular schedule by using max-plus algebra. Inputs of this algorithm are a graph representing the road network of public transportation systems and the number of public vehicles in each route. The graph has to be strongly connected, which means there is a path from any vertex to every vertex. Let us remark that the algorithm is general in the sense that we can allocate any number of vehicles in each route. The algorithm itself consists of two main steps. In the first step, we use a novel procedure to construct the model. Then in the second step, we compute a regular schedule by using the power algorithm. We describe our proposed framework for an example.Self-orthogonal codes from row orbit matrices of strongly regular graphs.https://zbmath.org/1449.940772021-01-08T12:24:00+00:00"Maksimović, Marija"https://zbmath.org/authors/?q=ai:maksimovic.marijaSummary: We show that under certain conditions submatrices of row orbit matrices of strongly regular graphs span self-orthogonal codes. In order to demonstrate this method of construction, we construct self-orthogonal ternary linear codes from orbit matrices of the strongly regular graphs with parameters \((70,27,12,9)\). Also we construct non self-orthogonal binary linear codes from these orbit matrices. Further, we obtain strongly regular graphs and block designs from codewords of the constructed codes.Recursive method for perfect matching numbers by matching vertex classification.https://zbmath.org/1449.052112021-01-08T12:24:00+00:00"Tang, Baoxiang"https://zbmath.org/authors/?q=ai:tang.baoxiang"Ren, Han"https://zbmath.org/authors/?q=ai:ren.hanSummary: Firstly, the perfect matching of the graph \(2 - n{Z_6}, 2 - nX{T_3}\) was classified by matching a certain vertex, and a recursive relation of a set of perfect matching numbers was obtained. Then the formulas for calculating the perfect matching numbers of two types of graphs were given by these recursive relations.Cordial labeling of the corona of cycles and kite graphs.https://zbmath.org/1449.052222021-01-08T12:24:00+00:00"Hefnawy, A."https://zbmath.org/authors/?q=ai:hefnawy.a-iSummary: A graph is said to be cordial if it has a 0-1 labeling that satisfies certain conditions. A kite graph, \(C_n\circledcirc P_m\), is formed by a cycle, \(C_n\), with a path, \(P_m\), and joining them by an edge \(uv\), where \(u\) is an arbitrary vertex of \(C_n\) and \(v\) is a vertex of degree one of \(P_m\). In this paper, we study the cordiality of kite graphs. We also investigate the conditions under which the corona of cycles and kite graphs are cordial.Recursive method for the number of 1-factors in graphs.https://zbmath.org/1449.052142021-01-08T12:24:00+00:00"Tang, Baoxiang"https://zbmath.org/authors/?q=ai:tang.baoxiang"Ren, Han"https://zbmath.org/authors/?q=ai:ren.hanSummary: Firstly, we classify the 1-factor of the graph, find the recurrence relation of the number of 1-factors of each class, and sum the recursive numbers of 1-factor numbers of each class to obtain a set of interconnected recursive relations. Then, with the relationship between these recursive formulas, we eliminate the unnecessary recurrence relations and obtain the recurrence relation of the 1-factor number of this graph. Finally we derive the formula solution of this recurrence formula.New sufficient conditions on \(k\)-path-coverable graphs.https://zbmath.org/1449.052092021-01-08T12:24:00+00:00"Jia, Huicai"https://zbmath.org/authors/?q=ai:jia.huicaiSummary: Let \(G\) be a simple connected graph of order \(n\). A graph \(G\) is \(k\)-path-coverable if its vertex set \(V (G)\) can be covered by \(k\) or fewer vertex-disjoint paths. In this paper, we give some new sufficient conditions for a graph to be \(k\)-path-coverable in terms of the distance spectral radius, the distance signless Laplacian spectral radius, Wiener index and Harary index of the graph or its complement, respectively.The linear arboricity of planar graphs with 6-cycles containing at most one chord.https://zbmath.org/1449.051092021-01-08T12:24:00+00:00"Luo, Zhaoyang"https://zbmath.org/authors/?q=ai:luo.zhaoyang"Sun, Lin"https://zbmath.org/authors/?q=ai:sun.linSummary: The linear arboricity \(\operatorname{la}(G)\) of a graph \(G\) is the minimum number of linear forests which partition the edges of \(G\). In this paper, using the discharging method, it is proved that for a planar graph \(G\), \(\operatorname{la} (G) = \lceil {\frac{\Delta (G)}{2}} \rceil \) if \(\Delta (G) \ge 7\) and every 6-cycle of \(G\) contains at most one chord.The adjacent vertex strongly distinguishing VI-total colorings of crown graphs of \({S_n} \circ {P_m}\) and \({S_n} \circ {C_m}\).https://zbmath.org/1449.051072021-01-08T12:24:00+00:00"Liu, Xiuli"https://zbmath.org/authors/?q=ai:liu.xiuliSummary: The adjacent vertex strongly distinguishing VI-total colorings of two crown graphs of \({S_n} \circ {P_m}\) and \({S_n} \circ {C_m}\) are studied. By constructing the function from \(V (G) \cup E (G)\) to \(\{1,2,\dots, k\}\), we gave a new coloring method according to the feature of these graphs, and obtained the adjacent vertex strongly distinguishing VI-total chromatic number of them.Preliminary study on the presentation of fuzzy transversal matroids.https://zbmath.org/1449.050442021-01-08T12:24:00+00:00"Wu, Deyin"https://zbmath.org/authors/?q=ai:wu.deyinSummary: The paper firstly discussed the condition under which all fuzzy partial transversal of a fuzzy set family forms a fuzzy transversal matroid. The first sufficient and necessary condition was described by the truncations of family of fuzzy sets. Another sufficient and necessary condition was described by the compatibility of injective mappings of partial transversal index sets. Then, this paper studied representations of fuzzy transversal matroids, and got three conclusions. The first conclusion is that any fuzzy transversal matroid has ``simplified representation''. The method of constructing simplified representations has also been provided. The second conclusion is that the number of fuzzy sets in one presentation is not less than the maximum rank of induced matroids. The third conclusion is that any uniform fuzzy transversal matroid has ``minimum representation''. The way of finding out the minimum representation from a representation of uniform fuzzy transversal matroid was given.On a graph of homogenous submodules of graded modules.https://zbmath.org/1449.051352021-01-08T12:24:00+00:00"Roshan-Shekalgourabi, H."https://zbmath.org/authors/?q=ai:roshan-shekalgourabi.hajar"Hassanzadeh-Lelekaami, D."https://zbmath.org/authors/?q=ai:hassanzadeh-lelekaami.dawoudSummary: In this paper, we introduce a graph associated to a graded module over a graded ring and study the relationship between the algebraic properties of these modules and their associated graphs. In particular, the modules whose associated graph is complete, complete bipartite or star are studied and several characterizations are given.Good neighbor connectivity of directed Kautz digraphs.https://zbmath.org/1449.051222021-01-08T12:24:00+00:00"Li, Meilian"https://zbmath.org/authors/?q=ai:li.meilian"Lin, Shangwei"https://zbmath.org/authors/?q=ai:lin.shangweiSummary: Directed Kautz digraphs are a kind of important networks in parallel computing systems. According to the faults distribution of parallel computing systems in practical application, the concept of good neighbor connectivity of directed digraphs was presented, which was a more accurate indicator for network reliability than the traditional connectivity. It was proved that the good neighbor connectivity of the directed Kautz digraph \(K (d, n)\) is \(2d - 2\).On interval and indifference graphs.https://zbmath.org/1449.050782021-01-08T12:24:00+00:00"Krzywkowski, Marcin"https://zbmath.org/authors/?q=ai:krzywkowski.marcin"Topp, Jerzy"https://zbmath.org/authors/?q=ai:topp.jerzySummary: Skrien characterized all graphs whose line graphs are interval graphs and indifference graphs. We determine all graphs whose middle graphs (total graphs, respectively) are interval graphs and indifference graphs.Embedded connectivity of \( (n, k)\)-star graphs.https://zbmath.org/1449.051572021-01-08T12:24:00+00:00"Mijit, Asiya"https://zbmath.org/authors/?q=ai:mijit.asiya"Vumar, Elkin"https://zbmath.org/authors/?q=ai:vumar.elkinSummary: The \(h\)-embedded connectivity \({\zeta_h} (S_{n,k})\) (resp. \(h\)-embedded edge-connectivity \({\eta_h} (S_{n,k})\)) of \({S_{n,k}}\) is defined as the cardinality of a minimum subset of vertices (resp. edges), if any, whose deletion disconnects \({S_{n,k}}\) and each vertex of the remaining components lies in an \(h\)-dimensional subnetwork \({S_{h,l}}\) for \(0 \le h \le n-2\) and \(l \le k\). In this paper, we investigate the \(h\)-embedded (edge) connectivity of \({S_{n,k}}\) and determine values of \({\zeta_h} (S_{n,k})\) and \({\eta_h} (S_{n,k})\) for \(k = 2, 3\) and \(0 \le h \le n-2\).The bicyclic graph with the minimum distance Laplacian spectral radius.https://zbmath.org/1449.051662021-01-08T12:24:00+00:00"Fan, Dandan"https://zbmath.org/authors/?q=ai:fan.dandan"Niu, Aihong"https://zbmath.org/authors/?q=ai:niu.aihong"Wang, Guoping"https://zbmath.org/authors/?q=ai:wang.guopingSummary: The largest eigenvalue of the distance Laplacian matrix of a connected graph \(G\) is called the distance Laplacian spectral radius of the graph \(G\). In this paper we obtain a sharp lower bound of distance Laplacian spectral radius, and then using the bound we determine the unique graph which has the minimum distance Laplacian spectral radius among all unicyclic graphs. Finally, by using the bound again as well as the characteristics polynomial of a distance Laplacian matrix, we characterize the unique graph with the minimum distance Laplacian spectral radius among all bicyclic graphs.Strong rainbow connectivity of undirected double loop networks.https://zbmath.org/1449.051052021-01-08T12:24:00+00:00"Liu, Jie"https://zbmath.org/authors/?q=ai:liu.jie.3|liu.jie.1|liu.jie|liu.jie.4|liu.jie.2|liu.jie.7|liu.jie.5"Chen, Baoxing"https://zbmath.org/authors/?q=ai:chen.baoxingSummary: Let \(n, {s_1}, {s_2}\) be positive integers such that \(1 \le {s_1} < {s_2} < n/2\) and \({\mathrm{gcd}} (n, {s_1}, {s_2}) = 1\). An undirected double loop network \(G (n; \pm {s_1}, \pm {s_2})\) is a graph \( (V (G), E (G))\), where \(V (G) = \{0, 1, \dots, n - 1\}\), and \(E (G) = \{i \to i + {s_1} \pmod n, i \to i - {s_1} \pmod n, i \to i + {s_2} \pmod n, i \to i - {s_2} \pmod n| i = 0, 1, 2, \dots, n - 1\}\).
In this paper, the shortest path between any two points in an undirected double loop network \(G (n; \pm {s_1}, \pm {s_2})\) is characterized, and a strong rainbow-connected edge color scheme for this network is proposed. Thus an upper bound of the strong rainbow connection number for \(G (n; \pm {s_1}, \pm {s_2})\) is obtained and is primarily represented by four parameters of the smallest non-negative solution and the smallest cross solution of the equation \(x{s_1} + y{s_2} \equiv 0 \pmod n\).The existence of \({\mathrm{MGDD}}_\lambda (3,4,ng)\) of type \({g^n}\).https://zbmath.org/1449.050332021-01-08T12:24:00+00:00"Cheng, Meihui"https://zbmath.org/authors/?q=ai:cheng.meihui"Song, Hongbo"https://zbmath.org/authors/?q=ai:song.hongboSummary: Group divisible 3-design is a kind of important combinatorial design, which is useful in the research of 3-wise balanced designs. Mendelsohn group divisible 3-design is an ordered extension of group divisible 3-design, which is also useful in the research of ordered 3-designs. In this paper, we mainly investigate the existence of Mendelsohn group divisible 3-design. By direct and recursive constructions, we prove that there is an \({\mathrm{MGDD}}_\lambda (3, 4, ng)\) of type \({g^n}\) if and only if \(\lambda n (n - 1) (n - 2){g^3} \equiv 0 \pmod 4\) and \(n \ge 4\), except for \(n = 5\), \(\lambda \equiv 1 \pmod 2\), \(g \equiv 1 \pmod 2\).On problem of recognition of pre-fractal graph.https://zbmath.org/1449.052352021-01-08T12:24:00+00:00"Naĭmanova, I. Kh."https://zbmath.org/authors/?q=ai:naimanova.i-kh"Kochkarov, A. M."https://zbmath.org/authors/?q=ai:kochkarov.a-mSummary: The problem of recognition of pre-fractal graphs with non-crossing old edges is considered. The regular \(n\)-point graph of \(s=n-2\) degree acts as example.Vertex-flames in countable rooted digraphs preserving an Erdős-Menger separation for each vertex.https://zbmath.org/1449.051212021-01-08T12:24:00+00:00"Joó, Attila"https://zbmath.org/authors/?q=ai:joo.attilaThe main result of this paper is a generalization of Lovász theorem to countable digraphs. Let \(D = (V,A)\) be a finite digraph. It follows from a theorem of Lovász that if \(r\in V\), then there is a spanning subdigraph \(E\) of \(D\) such that for every vertex \(v\) different from \(r\), the following quantities are equal: the local connectivity from \(r\) to \(v\in D\), the local connectivity from \(r\) to \(v\in E\) and the indegree of \(v\in E\).
This paper is structured in four sections. In Section 1, the Lovász theorem, the author's theorem (a generalization of the Lovász theorem to countable digraphs) without proof, the proof methods that work for finite digraphs and the author's proof strategy for countable digraphs are presented. At the end of the first section, the author introduces some further notation. The author states key lemmas without proofs and derive the main result in Section 2. Section 3 is devoted to the proofs of the key lemmas and in Section 4, the author discusses some open problems.
Reviewer: Eleonor Ciurea (Braşov)The perfect matching number of three types of graphs based on the recursive method of matching a certain vertex classification.https://zbmath.org/1449.052152021-01-08T12:24:00+00:00"Tang, Baoxiang"https://zbmath.org/authors/?q=ai:tang.baoxiang"Ren, Han"https://zbmath.org/authors/?q=ai:ren.hanSummary: Three new types of graphs \(2-2n{N_2}\), \(2-n{X_4}\) and \(3-n{D_4}\) are constructed. The three recursive relations of the perfect matching numbers of graphs \(2-2n{N_2}\), \(2-n{X_4}\) and \(3-n{D_4}\) are obtained by a recursive method, and then the three recursive general solutions are solved. Thus, the formula for calculating the perfect matching number of these three types of graphs is obtained.Fuzzy forcing set on fuzzy graphs. Definition and its application in social networks.https://zbmath.org/1449.052192021-01-08T12:24:00+00:00"Aliahmadipour, Layia"https://zbmath.org/authors/?q=ai:aliahmadipour.layia"Rashidi, Saeedeh"https://zbmath.org/authors/?q=ai:rashidi.saeedehSummary: The investigation of the impact of fuzzy sets on the zero forcing set is the main aim of this paper. According to this, results lead us to a new concept which we introduce it as fuzzy zero forcing set (FZFS). We propose this concept and suggest a polynomial time algorithm to construct FZFS. Furthermore, we compute the propagation time of FZFS on fuzzy graphs. This concept can be more efficient to model the opinion formation problem and the independent cascade model in social networks. Some examples are provided to illustrate constructing FZFS on special fuzzy graphs. Also, we utilize the FZFS in a social network to model opinion formation problem.Proof of chromaticity of the complete tripartite graphs \(K (n-k, n-3, n)\).https://zbmath.org/1449.051142021-01-08T12:24:00+00:00"Xu, Limin"https://zbmath.org/authors/?q=ai:xu.limin"Yang, Zhilin"https://zbmath.org/authors/?q=ai:yang.zhilinSummary: Let \(P (G, \lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P (H, \lambda) = P (G, \lambda)\) implies \(G \cong H\). Here, by comparing the number of the triangular subgraphs and the number of the quadrangular subgraphs without chords, the chromatic uniqueness problem of the complete tripartite graphs \(K (n-k, n-3, n)\) was completely solved. It was proved that \(K (n-k, n-3, n)\) is chromatically unique if \(n \ge k + 2 \ge 5\).Maximum Balaban index and sum-Balaban index of cacti.https://zbmath.org/1449.050572021-01-08T12:24:00+00:00"Fang, Wei"https://zbmath.org/authors/?q=ai:fang.wei"Yu, Hongjie"https://zbmath.org/authors/?q=ai:yu.hongjie.1"Gao, Yubin"https://zbmath.org/authors/?q=ai:gao.yubin"Jing, Guangming"https://zbmath.org/authors/?q=ai:jing.guangming"Li, Xiaoxin"https://zbmath.org/authors/?q=ai:li.xiaoxinSummary: The Balaban index and sum-Balaban index were used in various quantitative structure property relationship and quantitative structure activity relationship studies. Here the upper bounds of Balaban index and sum-Balaban index among all cacti were given and the cacti that attain the bounds were characterized.The strong Menger connectivity of balanced hypercube with conditional faults.https://zbmath.org/1449.051612021-01-08T12:24:00+00:00"Zhai, Dengxin"https://zbmath.org/authors/?q=ai:zhai.dengxin"Aygul, Mamut"https://zbmath.org/authors/?q=ai:aygul.mamutSummary: The balanced hypercube is a common topology in computer systems. In this paper, we prove that the \(n\)-dimensional balanced hypercube \(BH_n\) \((n \ge 4)\) with at most \(2n-2\) vertex faults \(F\) is strong Menger-connected. Furthermore, we prove that the \(n\)-dimensional balanced hypercube \(BH_n\) \((n \ge 2)\) with at most \(2n-4 (2n-2)\) vertex (edge) faults \(F\) is strong Menger-connected (edge-connected) with conditional faults.A generalization of a perturbation theorem on the least \(Q\)-eigenvalue and its application.https://zbmath.org/1449.051802021-01-08T12:24:00+00:00"Zhang, Rong"https://zbmath.org/authors/?q=ai:zhang.rong"Guo, Shuguang"https://zbmath.org/authors/?q=ai:guo.shuguangSummary: We investigate how the least \(Q\)-eigenvalue \(\kappa (G)\) of a graph \(G\) changes when some bipartite branches attached at some vertices are relocated to other vertices, and generalize the perturbation theorems on \(\kappa (G)\) of the literature. As an application, we construct a class of connected non-bipartite graphs and for any graph \(G\) in this class we construct a subset \(\mathcal{E}\) of \(E (G)\) such that \(\kappa (G) = \kappa (G - S)\) for any subset \(S\) of \(\mathcal{E}\).Open conjectures on congruences.https://zbmath.org/1449.110012021-01-08T12:24:00+00:00"Sun, Zhiwei"https://zbmath.org/authors/?q=ai:sun.zhiwei|sun.zhi-wei.1|sun.zhi-weiSummary: We collect here 100 open conjectures on congruences made by the author, some of which have never been published. This is a new edition of the author's preprint [\url{arXiv:0911.5665}] with those confirmed conjectures removed and some new conjectures added. Many congruences here are related to representations of primes by binary quadratic forms or series for powers of \(\pi\); for example, we mention two new conjectural identities
\[\sum_{n=0}^\infty {\frac{12n+1}{100^n}} \binom{2n}{n} \sum_{k=0}^n \binom{2k}{k}^2 \binom{2(n-k)}{n-k}\left (\frac{9}{4}\right)^{n-k} = \frac{75}{4\pi}\]
and
\[\sum_{k=1}^\infty \frac{3H_{k-1}^2 + 4H_{k-1}/k}{k^2\binom{2k}{k}} = \frac{\pi^4}{360} { with }H_{K-1}: = \sum_{0 < j \le k-1} \frac{1}{j}\]
and include related congruences. We hope that this paper will interest number theorists and stimulate further research.An analytical approach to degree profile of a random tree.https://zbmath.org/1449.620342021-01-08T12:24:00+00:00"Feng, Qunqiang"https://zbmath.org/authors/?q=ai:feng.qunqiang"Zheng, Boze"https://zbmath.org/authors/?q=ai:zheng.bozeSummary: The degree profile in a random planted plane tree was considered. For any \(d \ge 1\), it was proven that under suitable normalization, the number of vertices of degree \(d\) in a random planted plane tree with \(n\) edges has asymptotic normality, as \(n\) goes to infinity. The asymptotic formulae for the expectation and variance of this random variable were also given. An analytical method was employed in the proof.Reconstruction of rooted directed trees.https://zbmath.org/1449.680532021-01-08T12:24:00+00:00"Bartha, Dénes"https://zbmath.org/authors/?q=ai:bartha.denesSummary: Let \(T\) be a rooted directed tree on \(n\) vertices, rooted at \(v\). The rooted subtree frequency vector (RSTF-vector) of \(T\) with root \(v\), denoted by \(\operatorname{rstf}(T, v)\) is a vector of length \(n\) whose entry at position \(k\) is the number of subtrees of \(T\) that contain \(v\) and have exactly \(k\) vertices. In this paper we present an algorithm for reconstructing rooted directed trees from their rooted subtree frequencies (up to isomorphism). We show that there are examples of nonisomorphic pairs of rooted directed trees that are RSTF-equivalent, s.t. they share the same rooted subtree frequency vectors. We have found all such pairs (groups) for small sizes by using exhaustive computer search. We show that infinitely many nonisomorphic RSTF-equivalent pairs of trees exist by constructing infinite families of examples.Characteristic polynomials of generic arrangements.https://zbmath.org/1449.050402021-01-08T12:24:00+00:00"Sun, Ying"https://zbmath.org/authors/?q=ai:sun.ying"Gao, Ruimei"https://zbmath.org/authors/?q=ai:gao.ruimeiSummary: Firstly, we gave the definition of the generalized general position arrangement, and studied the relationships among the general position arrangements, generalized general position arrangements and generic arrangements. Secondly, by establishing the relationships between arrangements and the simple graphs, we gave the necessary and sufficient condition for linear independence of the subarrangements of generic threshold arrangements and the characteristic polynomials of the subarrangements of generic threshold arrangements.Szeged index of a class of unicyclic graphs.https://zbmath.org/1449.050652021-01-08T12:24:00+00:00"Qi, Xuli"https://zbmath.org/authors/?q=ai:qi.xuliSummary: The Szeged index is a modification of the Wiener index to cyclic molecules. The Szeged index of a connected graph \(G\) is defined as \(Sz(G)=\sum_{e\in E(G)}n_1(e\vert G)n_2(e\vert G)\), where \(E(G)\) is the edge set of \(G\), and for any \(e=uv\in E(G)\), \(n_1(e\vert G)\) is the number of vertices of \(G\) lying closer to vertex \(u\) than to vertex \(v\), and \(n_2(e\vert G)\) is the number of vertices of \(G\) lying closer to vertex \(v\) than to vertex \(u\). In this paper, we determine the \(n\)-vertex unicyclic graphs whose vertices on the unique cycle have degree at least three with the first, the second and the third smallest as well as largest Szeged indices for \(n\ge 6\), \(n\ge 7\) and \(n\ge 8\), respectively.Evaluation of a class of terminating \(_3F_2(\frac{4}{3})\)-series.https://zbmath.org/1449.330082021-01-08T12:24:00+00:00"Chen, X."https://zbmath.org/authors/?q=ai:chen.xiuyang|chen.xiaojiao|chen.xuemiao|chen.xiangtuo|chen.xueyuan|chen.xiaoying|chen.xuejun|chen.xibi|chen.xueqin|chen.xiaole|chen.xingtong|chen.xianfu|chen.xiaosong|chen.xuzong|chen.xing|chen.xinmng|chen.xintong|chen.xiyu|chen.xiaotong|chen.xumin|chen.xiaohong.3|chen.xiaochao|chen.xuechun|chen.xuqi|chen.xuejing|chen.xiangning|chen.xiaoyong|chen.xi.2|chen.xueyou|chen.xiuqin|chen.xiuping|chen.xinxin|chen.xiuidong|chen.xiaoyou|chen.xin.1|chen.xian|chen.xinghua|chen.xinxiang|chen.xuemin.2|chen.xiandong|chen.xinjiao|chen.xuerong|chen.xigeng|chen.xianyong|chen.ximeng|chen.xiangzhi|chen.xinhong|chen.xingmin|chen.xiaoming|chen.xiaolei|chen.xieyuanli|chen.xiaoqun|chen.xiaoxu|chen.xiangfu|chen.xiankang|chen.xiongda|chen.xisong|chen.xinyi|chen.xiaoqian|chen.xiangzhen|chen.xichun|chen.xiaoli|chen.xiao|chen.xiaohe|chen.xueyan|chen.xiaobiao|chen.xiaofa|chen.xuyong|chen.xianjia|chen.xudong|chen.xida|chen.xiaoshuang|chen.xianwei|chen.xinjia|chen.xiaobo|chen.xingqian|chen.xueping|chen.xueyun|chen.xueying|chen.xianzhe|chen.xihan|chen.xiuming|chen.xinzhong|chen.xuling|chen.xiaoou|chen.xuechen|chen.xueqiang|chen.xiangchuan|chen.xun|chen.xiaogen|chen.xianqiang|chen.xiaoxing|chen.xinguo|chen.xiaoyi|chen.xiyuan|chen.xiaojing|chen.xingyu|chen.xiaming|chen.xi|chen.xuerui|chen.xiaopeng|chen.xinguang|chen.xiongwen|chen.xianzhang|chen.xianming|chen.xujin|chen.xiaojuan|chen.xuzhou|chen.xiubo|chen.xue|chen.xiancheng|chen.xueling|chen.xianglian|chen.xia|chen.xu-yan|chen.xueli|chen.xianchu|chen.xiaorong|chen.xiangrui|chen.xinying|chen.xiaoru|chen.xiaoxian|chen.xiaofeng|chen.xiuqiong|chen.xiqiong|chen.xiancun|chen.xuesheng|chen.xiangwang|chen.xinjie|chen.xuzhi|chen.xihnian|chen.xiaozhu|chen.xianhua|chen.xurong|chen.xinzhao|chen.xiexiong|chen.xinlei|chen.xinquan|chen.xunchao|chen.xiqiu|chen.xiuwan|chen.xufeng|chen.xiaoqin|chen.xuemei|chen.xianyu|chen.xiuwei|chen.xiaotao|chen.xiaolin|chen.xiaoqiu|chen.xiaoyan|chen.xuanqing|chen.xiaoguang|chen.xianqing|chen.xiaojun|chen.xiaocen|chen.xuefeng|chen.xuegong|chen.xiaoxi|chen.xiwei|chen.xingshu|chen.xuwen|chen.xiaoxin|chen.xuezhang|chen.xuning|chen.xiaokun|chen.xiaoke|chen.xiangen|chen.xiaoni|chen.xiaozhi|chen.xianglan|chen.xumei|chen.xioushu|chen.xinfang|chen.xinshuang|chen.xingran|chen.xingping|chen.xinyun|chen.xuezhou|chen.xiaolong|chen.xiaosu|chen.xiangping|chen.xingfu|chen.xingguo|chen.xihao|chen.xuan|chen.xilong|chen.xiangyun|chen.xiaomei|chen.xuelin|chen.xingchi|chen.xizhen|chen.xiaohua|chen.xiumei|chen.xujun|chen.xinchu|chen.xinmeng|chen.xiangfei|chen.xinyuan|chen.xiangying|chen.xingwen|chen.xiuyuan|chen.xiaoyang|chen.xiaoji|chen.xiangguang|chen.xiuxiong|chen.xiong|chen.xiaoping|chen.xiangyu|chen.xiangsong|chen.xingfa|chen.xugunag|chen.xiaoning|chen.xiangbing|chen.xiliang|chen.xiuqing|chen.xiaoyu|chen.xi.1|chen.xinliang|chen.xianyan|chen.xiaonan|chen.xueqian|chen.xiaodong|chen.ximing|chen.xusheng|chen.xinli|chen.xibin|chen.xuming|chen.xiangyong|chen.xueguang|chen.xiuqiu|chen.xinglin|chen.xuehua|chen.xuelong|chen.xiaoman|chen.xingru|chen.xuenong|chen.xiangqing|chen.xiangyi|chen.xingyi|chen.xiaohuai|chen.xuyun|chen.xiaoheng|chen.xiangwei|chen.xiaowu|chen.xiuhua|chen.xikang|chen.xiangxian|chen.xiqing|chen.xingxing|chen.xingfan|chen.xinming|chen.xingdi|chen.xiaowu.1|chen.xiangling|chen.xiai|chen.xiaobing|chen.xiao.1|chen.xubing|chen.xianghong.1|chen.xuemin.1|chen.xuesong|chen.xianzhong|chen.xianqiao|chen.xuanyi|chen.xianmin|chen.xuejuan|chen.xuejin|chen.xiaopan|chen.xianshun|chen.xiang|chen.xugao|chen.xingguang|chen.xianjin|chen.xiaofei|chen.xiebin|chen.xuewen|chen.xingjiang|chen.xia.1|chen.xie|chen.xuhui|chen.xiangrong|chen.xiaochun|chen.xiangjian|chen.xingang|chen.xiusu|chen.xiqun|chen.xiaokai|chen.xiyang|chen.xinfu|chen.xirong|chen.xianjiang|chen.xiaowen|chen.xiaofang|chen.xinyue|chen.xioahong|chen.xueyao|chen.xueer|chen.xiaojun.1|chen.xiaoming.1|chen.xiaozhou|chen.xindu|chen.xiuyin|chen.xide|chen.xuegang|chen.xiaoyuan|chen.xiaoqing|chen.xinjian|chen.xuehui|chen.xiaogang|chen.xiazhong|chen.xiping|chen.xiqian|chen.xiangfeng|chen.xiaozheng|chen.xinxing|chen.xiangtang|chen.xubin|chen.xiaoe|chen.xuewu|chen.xiaokang|chen.xidi|chen.xianyi|chen.xuelei|chen.xiufang|chen.xinyiao|chen.xinren|chen.xiu|chen.xinjuan|chen.xinkai|chen.xuyang|chen.xinlong|chen.xiaoyun|chen.xiaobao|chen.xiuli|chen.xinglong|chen.xingyuan|chen.xiuhong|chen.xuechang|chen.xiaohui|chen.xiulong|chen.xiaoqiang|chen.xinyu|chen.xilin|chen.xizhong|chen.xiaohan|chen.xiangyang|chen.xueyong|chen.xuekun|chen.xiangjun|chen.xiaoxuan|chen.xiaojiang|chen.xingxin|chen.xuebo|chen.xiaoling|chen.xiaoxiang|chen.xinwei|chen.xiexong|chen.xixi|chen.xiongshan|chen.xi.4|chen.xiujuan|chen.xiaojie|chen.xin|chen.xuebing|chen.xiaoshi|chen.xiaoyue|chen.xuedong|chen.xianghui|chen.xianli|chen.xinbei|chen.xiaocui|chen.xianping|chen.xingding|chen.xiru|chen.xiudong|chen.xixian|chen.xiaoliang|chen.xiaoshan|chen.xiaopei|chen.xihong|chen.xiyou|chen.xingyue|chen.xu|chen.xueen|chen.xiaoting|chen.xiuhuan|chen.xiaoxia|chen.xingwang|chen.xingyong|chen.xijun|chen.xueqing|chen.xiongzhi|chen.xiying|chen.xiaozhao|chen.xuzhong|chen.xiangqun|chen.xianghong|chen.xiaoguo|chen.xiaoxiao|chen.xianze|chen.xingzhen|chen.xianfeng|chen.xiangdong|chen.xinmei|chen.xinghuan|chen.xiaotian|chen.xiangxun|chen.xucan|chen.xueqi|chen.xuanguang|chen.xiaomin|chen.xueru|chen.xinhai|chen.xi.5|chen.xueye|chen.xingrong|chen.xiaorui|chen.xianyao|chen.xiaodan|chen.xiaolan|chen.xiuzhen|chen.xuefei|chen.xinrun|chen.xiaowei"Chu, W."https://zbmath.org/authors/?q=ai:chu.weijiang|chu.wenchang|chu.wensong|chu.weijuan|chu.wanghuan|chu.weipan|chu.weiwei|chu.wenten|chu.wangli|wang.tan-chu|chu.wenqing|chu.wei|chu.wang|chu.weiqi|chu.wanglin|chu.wanmingThe authors define and study a large class of terminating \(_3F_2(\frac{4}{3})\)-series. They involve two extra integer parameters. The signs of these parameters need special treatment. At the end of the paper numerous examples are calculated for the demonstration of the results.
Reviewer: István Mező (Nanjing)Some applications of the \( (f,g)\)-inversion.https://zbmath.org/1449.050282021-01-08T12:24:00+00:00"Mu, Yanping"https://zbmath.org/authors/?q=ai:mu.yanping"Tong, Xiaozhou"https://zbmath.org/authors/?q=ai:tong.xiaozhouSummary: We present three kinds of applications of the \( (f, g)\)-inversion. By taking explicit functions and sequences in the \( (f, g)\)-inversion, we derive identities involving hypergeometric series and harmonic numbers. Then we give several inversion relations involving \(q\)-hypergeometric terms. Finally, we combine the \( (f, g)\)-inversion and the \(q\)-differential operators to derive some \(q\)-series identities.The commuting graphs of finite rings.https://zbmath.org/1449.160452021-01-08T12:24:00+00:00"Dolžan, David"https://zbmath.org/authors/?q=ai:dolzan.davidSummary: In this paper, we investigate connectivity and diameters of commuting graphs of finite rings. In case of a directly decomposable ring, we calculate the diameter depending on the diameters of commuting graphs of direct summands. If the ring is indecomposable, we examine the connectedness of the commuting graph according to the number of isomorphic minimal idempotents.The factorizations of adjoint polynomials of graphs of shape as \(P_\lambda^{ES}\) and chromatically equivalence of their complements.https://zbmath.org/1449.051452021-01-08T12:24:00+00:00"Xiong, Pengfei"https://zbmath.org/authors/?q=ai:xiong.pengfei"Zhang, Bingru"https://zbmath.org/authors/?q=ai:zhang.bingruSummary: Let \({P_n}\) be a path with \(n\) vertices and let \({C_n}\) be a cycle with \(n\) vertices, and \(nG\) be the union of \(n\) graphs \(G\) without common vertex. We denote by \(S_{r (m+1)+1}^\ast\) the graph consisting of \(rP_{m+2}\) and by coinciding \(r\) vertices of degree 1 of \(rP_{m+2}\). Let \(E_{ (r+1)m+r}^{S^\ast}\) be the graph consisting of \({P_m}\) and \(S_{r (m+1)+1}^\ast\) by coinciding a vertex of degree 1 of \({P_m}\) with the vertex of degree \(r\) of \(S_{r (m+1)+1}^\ast\), which can be abbreviated to \(E_\delta^S\), \(\delta = (r+1)m + r\); let \(n\) \((\ge 3)\) be an odd number, \(\lambda = n + 2^{-1} (n+1)\delta\). Let \(P_\lambda^{ES}\) be the graph consisting of \(2^{-1} (n+1)E_\delta^S\) and \({P_n}\) by coinciding the vertex of degree \(r+1\) of every component of \(2^{-1} (n+1)E_\delta^S\) with \(2^{-1} (n+1)\) vertices whose subscript is odd of \({P_n}\), respectively. By using the properties of adjoint polynomials of graphs, we discuss the factorizations of the adjoint polynomials of graphs \(E_\delta^S \bigcup r{K_1}\) and \(P_{2\lambda + 1}^{ES} \bigcup {K_1}\) and \(P_{2\lambda + 3 + \delta}^{ES} \bigcup E_\delta^S\). Let \(n = 2^{k-1}q-1\), and \({\lambda_k} = ({2^k}q-1) + 2^{k-1}q\delta\), we discuss the factorizations of the adjoint polynomials of graphs \(P_{\lambda_k}^{ES}\) and \(P_{\lambda_k}^{ES} \bigcup (k-1){K_1}P_{\lambda_k}^{ES}\). Further, we prove the chromatically equivalence of complements of these graphs.A class of new \(m\)-multisum Rogers-Ramanujan identities and applications.https://zbmath.org/1449.050312021-01-08T12:24:00+00:00"Zhang, Zhizheng"https://zbmath.org/authors/?q=ai:zhang.zhizheng"Li, Xiaoqian"https://zbmath.org/authors/?q=ai:li.xiaoqianSummary: Rogers-Ramanujan identities are among the most famous \(q\)-series in partition theory and combinatorics, they have been proved and generalized widely. The purpose of this paper is to establish a class of new multisum Rogers-Ramanujan identities by applying the bilateral Bailey lemma and iterating technique.Analysis of the effect of medicines over bacteria based on competition graphs with picture fuzzy environment.https://zbmath.org/1449.050502021-01-08T12:24:00+00:00"Das, Sankar"https://zbmath.org/authors/?q=ai:das.sankar-c"Ghorai, Ganesh"https://zbmath.org/authors/?q=ai:ghorai.ganeshSummary: In this study, the concept of picture fuzzy competition graph along with its two subclasses such as picture fuzzy \(k\)-competition graphs and \(p\)-competition picture fuzzy graphs are introduced. Picture fuzzy competition graph is one of the generalizations of competition graph. Several properties of picture fuzzy competition graphs have been investigated. Some new types of picture fuzzy graphs have been introduced like picture fuzzy open neighborhood graph and picture fuzzy closed neighborhood graph. In addition, the relationship between picture fuzzy \(k\)-competition graph and picture fuzzy \(k\)-neighborhood graph are established. An application of picture fuzzy competition graph in medical science is presented.A note on the coefficients of the \({A_\alpha}\)-characteristic polynomial of a graph.https://zbmath.org/1449.051432021-01-08T12:24:00+00:00"Liu, Shunyi"https://zbmath.org/authors/?q=ai:liu.shunyi"Qin, Zhongmei"https://zbmath.org/authors/?q=ai:qin.zhongmeiSummary: Let \(G\) be a graph with \(n\) vertices, and let \(A (G)\) and \(D (G)\) denote the adjacent matrix and the degree matrix of \(G\), respectively. Define \({A_\alpha} (G) = \alpha D (G) + (1-\alpha)A (G)\) for any real \(\alpha \in [0,1]\). The \({A_\alpha}\)-characteristic polynomial of \(G\) is the characteristic polynomial of \({A_\alpha} (G)\), i.e., \({\mathrm{det}} (x{I_n}-{A_\alpha} (G))\), where \({I_n}\) is the identity matrix of size \(n\). In this paper, we give a combinatorial expression for the fifth coefficient of the \({A_\alpha}\)-characteristic polynomial of a graph.Structural recognition algorithm for prefractal graph.https://zbmath.org/1449.680562021-01-08T12:24:00+00:00"Utakaeva, Irina Khaĭrlyevna"https://zbmath.org/authors/?q=ai:utakaeva.irina-khairlyevna(no abstract)Bounds of Zagreb indices and hyper Zagreb indices.https://zbmath.org/1449.050692021-01-08T12:24:00+00:00"Wang, Shaohui"https://zbmath.org/authors/?q=ai:wang.shaohui"Gao, Wei"https://zbmath.org/authors/?q=ai:gao.wei.3"Jamil, Muhammad K."https://zbmath.org/authors/?q=ai:jamil.muhammad-kamran"Farahani, Mohammad R."https://zbmath.org/authors/?q=ai:farahani.mohammad-reza"Liu, Jia-Bao"https://zbmath.org/authors/?q=ai:liu.jia-baoLet \(G\) be a finite graph without loops and multiple edges. The first hyper-Zagreb index is the sum of the squares of edge degrees over the edge set \(E(G)\), i.e., \(HM_1(G)=\sum\limits_{e\sim f} d(e)^2\), where \(d(e)=d(u)+d(v)\) is the edge degree. In the paper under review, the second hyper-Zagreb index on the set of adjacent edges is introduced by the formula \(HM_2(G)=\sum\limits_{e\sim f} d(e)d(f)\), where \(e\sim f\) represents the adjacent edges of \(G\). The authors prove the upper and lower bounds on these hyper-Zagreb indices and provide the relations between hyper-Zagreb indices and Zagreb indices in terms of inequalities between them.
Reviewer: Alexander Guterman (Moskva)Odd vertex equitable even labeling of ladder graphs.https://zbmath.org/1449.052242021-01-08T12:24:00+00:00"Jeyanthi, P."https://zbmath.org/authors/?q=ai:jeyanthi.pon"Maheswari, A."https://zbmath.org/authors/?q=ai:maheswari.anthony"Vijayalakshmi, M."https://zbmath.org/authors/?q=ai:vijayalakshmi.maniSummary: Let \(G\) be a graph with \(p\) vertices and \(q\) edges and \(A=\{1,3,\ldots,q\}\) if \(q\) is odd or \(A=\{1,3,\ldots,q+1\}\) if \(q\) is even. A graph \(G\) is said to admit an odd vertex equitable even labeling if there exists a vertex labeling \(f:V(G)\to A\) that induces an edge labeling \(f^\ast\) defined by \(f^\ast(uv)=f(u)+f(v)\) for all edges \(uv\) such that for all \(a\) and \(b\) in \(A\), \(|v_f(a)-v_f(b)|\le 1\) and the induced edge labels are \(2,4,\ldots,2q\) where
\(v_f(a)\) is the number of vertices \(v\) with \(f(v)=a\) for \(a \in A\). A graph that admits an odd vertex equitable even labeling is called an odd vertex equitable even graph [the authors, Proyecciones 36, No. 1, 1--11 (2017; Zbl 1380.05176)]. In this paper we investigate the odd vertex equitable even labeling behavior of some ladder graphs.Signless Laplacian spectra of generalized core-satellite graphs.https://zbmath.org/1449.051732021-01-08T12:24:00+00:00"Tian, Guixian"https://zbmath.org/authors/?q=ai:tian.guixian"Sun, Mei"https://zbmath.org/authors/?q=ai:sun.meiSummary: The generalized core-satellite graph is a special kind of join graphs, which is the natural generalization of many well known types of graphs. With the help of the numerical characteristic theory of matrices, the signless Laplacian spectra of core-satellite graphs and generalized core-satellite graphs were determined. Based on the obtained results, some signless Laplacian integral graphs were constructed, which generalized some existed results.On \((\ell,m)\)-regular bipartition triples.https://zbmath.org/1449.050232021-01-08T12:24:00+00:00"Mahadeva Naika, M. S."https://zbmath.org/authors/?q=ai:mahadeva-naika.megadahalli-sidda"Nayaka, S. Shivaprasada"https://zbmath.org/authors/?q=ai:nayaka.s-shivaprasadaSummary: Let \(BT_{\ell,m}(n)\) denote the number of \((\ell,m)\)-regular bipartition triples of a positive integer \(n\). We establish infinite families of arithmetic identities and congruences for \(BT_{\ell,m}(n)\) modulo 3, 9 and 27 for various values of \(\ell\) and \(m\). For examples, we show that
\[
BT_{3,5}\left( 5^{\alpha +2}n+\frac{11\cdot 5^{\alpha +1}-3}{4}\right) \equiv 0 \pmod{9}
\]
and
\[
BT_{3,9}(27n+19)\equiv 0 \pmod{27}
\]
for all nonnegative integers \(\alpha\) and \(n\).A survey on rainbow matchings in graphs and hypergraphs.https://zbmath.org/1449.051042021-01-08T12:24:00+00:00"Li, Tong"https://zbmath.org/authors/?q=ai:li.tong"Wang, Guanghui"https://zbmath.org/authors/?q=ai:wang.guanghui"Zhou, Wenling"https://zbmath.org/authors/?q=ai:zhou.wenlingSummary: A hypergraph \(H =(V, E)\) is a two-tuple \( (V, E)\), where the element in the hyperedge set \(E\) is a non-empty subset of the vertex set \(V\). Therefore, the graph is a special hypergraph, and the hypergraph can also be regarded as a generalization of the general graph. In particular, if the elements in the hyperedge set \(E\) are all a \(k\)-subset of the vertex set \(V\), then the hypergraph is said to be \(k\)-uniform. Usually, for the sake of simplicity, we also refer to the hyperedge as the edge. A matching in a graph (hypergraph) refers to a collection of mutually disjoint edges in a graph (hypergraph). There are two ways to define a rainbow matching: one is a collection of mutually disjoint edges with different colors in an edge-colored graph (hypergraph); the other one is a collection of mutually disjoint edges with different colors, where each edge is from different edge-colored graphs (hypergraphs). This paper mainly introduces the results related to rainbow matchings in graphs and hypergraphs.Ehrhart polynomial for lattice squares, cubes and hypercubes.https://zbmath.org/1449.520102021-01-08T12:24:00+00:00"Ionascu, Eugen J."https://zbmath.org/authors/?q=ai:ionascu.eugen-julienFor a given \(d\)-dimensional compact simplicial complex \(\mathcal{P}\) in \({\mathbb{R}}^n\), which has all its vertices in the integer lattice, the number of lattice points in \(t\mathcal{P}\) for a positive integer \(t\) is given by a rational polynomial \(L({\mathcal{P}},t)\) of degree \(d\) of the variable \(t\). This well studied polynomial is called the ``Ehrhart polynomial'' of the simplicial complex. It is known that the number of lattice points in the interior of \(t\mathcal{P}\) is expressed by the Ehrhart polynomial as \((-1)^d L({\mathcal{P}},-t)\). For \(n=2\), the paper under review studies the sequence of integers that arise as number of latttice points in the interior of a lattice square, put into increasing order. This sequence is called ``almost perfect squares''. The paper observes that this sequence is very similar, but not identical, to the sequence A194154 of the On-Line Encyclopedia of Integer Sequences. The paper constructs integer lattice squares, cubes, and hypercubes in \(n=2,3,4\) dimensions. All integer lattice squares are characterized in \({\mathbb{R}}^4\). For each of these problems, the corresponding Ehrhart polynomial is computed.
Reviewer: László A. Székely (Columbia)On the relationship between the thickness of some complete bipartite graphs and complete tripartite graphs.https://zbmath.org/1449.052202021-01-08T12:24:00+00:00"Dong, Xue"https://zbmath.org/authors/?q=ai:dong.xue"Guo, Xia"https://zbmath.org/authors/?q=ai:guo.xia"Yang, Yan"https://zbmath.org/authors/?q=ai:yang.yanSummary: The thickness of a graph \(G\) is the minimum number of planar spanning subgraphs into which \(G\) can be decomposed. It is one key indicator for measuring the planarity of a graph. It is important to study the thickness of a graph. There are many important applications in VLSI and network design. At present, the exact thickness of some types of graphs are obtained, but the relationship between the thickness of the complete bipartite graph and the complete tripartite graph has not been fully presented. By studying the relationship between the thickness of partial complete bipartite graph and complete tripartite graph, it is obtained that the thickness of \({K_{1,n,n+1}}\) and \({K_{n+1,n+1}}\), \({K_{1,n,n+2}}\) and \({K_{n+1,n+2}}\), \({K_{2,n,n+2}}\) and \({K_{n+2,n+2}}\) are equal.On the strong persistence property for monomial ideals.https://zbmath.org/1449.130122021-01-08T12:24:00+00:00"Reyes, Enrique"https://zbmath.org/authors/?q=ai:reyes.enrique|reyes.enrique-g"Toledo, Jonathan"https://zbmath.org/authors/?q=ai:toledo.jonathanSummary: Let \(I\) be the edge ideal associated to a graph with loops, a weighted graph or a clutter. In this paper we study when \(I\) has the strong persistence property, this is \((I^{k+1}:I) = I^k\) for each \(k \ge 1\).Some identities involving Fibonacci sequence and Lucas sequence.https://zbmath.org/1449.050262021-01-08T12:24:00+00:00"Chen, Guohui"https://zbmath.org/authors/?q=ai:chen.guohuiSummary: The summation problem about the convolution sums of second-order linear recursion sequences is considered. According to the definition and properties of Fibonacci and Lucas polynomials, based on the existing research results, and by using the elementary method and the power series expansion of exponential function, some new calculation formulas of these second-order linear recursion sequence are obtained. In addition, by analyzing and generalizing these new results, a series of interesting identities are obtained.The neighbor expanded sum distinguishing total colorings of cactus graphs.https://zbmath.org/1449.051172021-01-08T12:24:00+00:00"Zhang, Hui"https://zbmath.org/authors/?q=ai:zhang.hui.3|zhang.hui.6|zhang.hui.7|zhang.hui.2|zhang.hui.5|zhang.hui.1|zhang.hui.8|zhang.hui.10|zhang.hui|zhang.hui.11|zhang.hui.4|zhang.hui.9"Li, Zepeng"https://zbmath.org/authors/?q=ai:li.zepeng"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangenSummary: Let \(G\) be a simple graph. A total \(k\)-coloring of \(G\) is an assignment of \(k\) colors \(1, 2, \dots, k\) to all vertices and edges of \(G\). For \(x \in V (G)\) and \(N (x) = \{y\in V (G)\mid xy\in E (G)\}\), the value \(w (x) = \sum\limits_{e \ni x}c (e)+ \sum\limits_{y \in N (x)}c (y)\) is called the expanded sum at \(x\), where \(c\) is a total \(k\)-coloring of \(G\). A total \(k\)-coloring \(c\) of \(G\) is called the neighbor expanded sum distinguishing (NESD for short) if \(w (x)\ne w (y)\), whenever \(xy \in E (G)\). The minimum number \(k\) of an NESD total \(k\)-coloring of \(G\) is called the neighbor expanded sum distinguishing total chromatic number of \(G\) and denoted by \(egndi_{\sum} (G)\). The neighbor expanded sum distinguishing total colorings of cactus graphs are discussed in this paper by using the method of mathematical induction. It is proved that the neighbor expanded sum distinguishing total chromatic number of any cactus graph is less than or equal to 2. This result illustrates that the NESDTC conjecture is true for cactus graphs.Some combinatorial properties of restricted Eulerian polynomials.https://zbmath.org/1449.110412021-01-08T12:24:00+00:00"Zhang, Xutong"https://zbmath.org/authors/?q=ai:zhang.xutong"Zhang, Biao"https://zbmath.org/authors/?q=ai:zhang.biaoSummary: A new class of restricted Eulerian polynomials is defined by restricting both the first and last letters of the permutations. The relationships of the new restricted Eulerian polynomials and the original ones are obtained in two different ways by using the property of the new restricted Eulerian polynomials. In addition, the equidistribution of excedances and descents for permutations with the last letter restricted is proved.Sufficient conditions for pancyclic graphs by Wener index, hyper-Wiener index and Harary index.https://zbmath.org/1449.050592021-01-08T12:24:00+00:00"Hu, Qiming"https://zbmath.org/authors/?q=ai:hu.qiming"Xu, Huan"https://zbmath.org/authors/?q=ai:xu.huan"Ye, Ming"https://zbmath.org/authors/?q=ai:ye.mingSummary: Let \(G (V,E)\) be an \(n\)-order simple connected graph. If for any positive integer \(k\) \((3 \le k \le n)\), there is a cycle \({C_k}\) of length \(k\) in \(G\), then \(G\) is called a pancyclic graph. Firstly, Wiener, hyper-Wiener and Harary indexes are introduced in this paper. Then, by using the topological index of the graph and its complement, sufficient conditions for the simple connected graph with minimum degree condition to be a pancyclic graph are given.A novel approach for detecting relationships in social networks using cellular automata based graph coloring.https://zbmath.org/1449.680552021-01-08T12:24:00+00:00"Kashani, M."https://zbmath.org/authors/?q=ai:kashani.m-b"Shojaedini, S. V."https://zbmath.org/authors/?q=ai:shojaedini.s-v"Gorgin, S."https://zbmath.org/authors/?q=ai:gorgin.saeid(no abstract)Enumerating perfect matchings of a Halin graph.https://zbmath.org/1449.051422021-01-08T12:24:00+00:00"Lv, Haoyang"https://zbmath.org/authors/?q=ai:lv.haoyang"Zhang, Xiuping"https://zbmath.org/authors/?q=ai:zhang.xiupingSummary: A method to count the number of perfect matchings of cubic bridgeless graph, regular glue, is described, which is the reverse process of brick and brace decomposition. A new lower boundary of the number of perfect matchings of a cubic Halin graph is introduced, which checks the Lovasz-Plummer conjecture.Maximum augmented Zagreb index of graphs with given vertex bipartiteness.https://zbmath.org/1449.050582021-01-08T12:24:00+00:00"Gao, Fang"https://zbmath.org/authors/?q=ai:gao.fang"Zha, Shuping"https://zbmath.org/authors/?q=ai:zha.shuping"Wang, Zhen"https://zbmath.org/authors/?q=ai:wang.zhen|wang.zhen.6|wang.zhen.7|wang.zhen.1|wang.zhen.2|wang.zhen.3|wang.zhen.5"Zhao, Duoduo"https://zbmath.org/authors/?q=ai:zhao.duoduo"Fang, Wei"https://zbmath.org/authors/?q=ai:fang.weiSummary: Augmented Zagreb index (AZI) of a graph is widely used to study the heat information of heptanes and octanes in chemistry. Here graphs with given vertex bipartiteness were studied. The extremal graph having maximum AZI was given. The relationship between the extremal graph and the complete bipartite graph was analyzed.Riordan arrays and combinatorial identity.https://zbmath.org/1449.050212021-01-08T12:24:00+00:00"Yang, Shengliang"https://zbmath.org/authors/?q=ai:yang.shengliang"Chang, Wenlong"https://zbmath.org/authors/?q=ai:chang.wenlongSummary: In this paper, the relation among the arrays of Pascal, Catalan, Motzkin, and Schröder is given by means of the theory of Riordan arrays. Several identities of Catalan number, Motzkin number and Schröder number are proved.Zero-divisor graphs of finite commutative rings: a survey.https://zbmath.org/1449.051372021-01-08T12:24:00+00:00"Singh, Pradeep"https://zbmath.org/authors/?q=ai:singh.pradeep-kumar"Bhat, Vijay Kumar"https://zbmath.org/authors/?q=ai:bhat.vijay-kumarSummary: This article gives a comprehensive survey on zero-divisor graphs of finite commutative rings. We investigate the results on structural properties of these graphs.\(Z\)-spectral radius of the adjacency tensor of uniform supertrees.https://zbmath.org/1449.051712021-01-08T12:24:00+00:00"Shi, Chao"https://zbmath.org/authors/?q=ai:shi.chao"Wang, Xiuwen"https://zbmath.org/authors/?q=ai:wang.xiuwen"Zheng, Yirong"https://zbmath.org/authors/?q=ai:zheng.yirongSummary: Let \(T\) be an \(r\)-uniform supertree, and \({\rho_Z} (T)\) be the \(Z\)-spectral radius of the adjacency tensor of \(T\). We show that \({\rho_Z} (T) = {r^{1 - r/2}}\) with \(r \ge 3\).Variable-weight OOCs via semi-cyclic group divisible designs.https://zbmath.org/1449.050352021-01-08T12:24:00+00:00"Qin, Rongcun"https://zbmath.org/authors/?q=ai:qin.rongcun"Zhao, Hengming"https://zbmath.org/authors/?q=ai:zhao.hengmingSummary: Variable-weight optical orthogonal codes (OOCs) were introduced previously for multimedia optical CDMA systems with multiple quality of service (QoS) requirements. In this paper, \( (W, Q)\) semi-cyclic group divisible designs (\( (W, Q)\)-SCGDDs) are first introduced to construct variable-weight OOCs. Consequently, several new optimal balanced \( (v, \{3, 4\}, 1)\)-OOCs are obtained by using \( (W, Q)\)-SCGDDs and perfect relative difference families.Single-hook immanants for complete graphs.https://zbmath.org/1449.051792021-01-08T12:24:00+00:00"Yu, Guihai"https://zbmath.org/authors/?q=ai:yu.guihai"Hou, Yaoping"https://zbmath.org/authors/?q=ai:hou.yaoping"Qu, Hui"https://zbmath.org/authors/?q=ai:qu.huiSummary: As we know, the computation of immanants is very difficult. In this paper we determine a recursive expression of single-hook immanants of the adjacency matrices and Laplacian matrices of complete graphs on \(n\) vertices, respectively. In addition, the values of the permanents of the adjacency matrices and Laplacian matrices of cycles on \(n\) vertices are given, respectively.On the Hermitian-incidence energy of mixed graphs.https://zbmath.org/1449.051752021-01-08T12:24:00+00:00"Wang, Weizhong"https://zbmath.org/authors/?q=ai:wang.weizhong"Zhou, Kunqiang"https://zbmath.org/authors/?q=ai:zhou.kunqiangSummary: By introducing a new concept, Hermitian-incidence energy (HIE) of a mixed graph \(M\), \(\operatorname{HIE}(M) = \sum\limits_{i = 1}^n {\sqrt {{q_i}}} \) (where \({q_i}\) is the \(i\)-th eigenvalues of the Hermitian quasi-Laplacian matrix of \(M\)), we mainly point out some bounds to HIE using the number of vertices, edges, and the maximum degrees of \(M\).Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs.https://zbmath.org/1449.680462021-01-08T12:24:00+00:00"Goel, Ashish"https://zbmath.org/authors/?q=ai:goel.ashish"Kapralov, Michael"https://zbmath.org/authors/?q=ai:kapralov.michael"Khanna, Sanjeev"https://zbmath.org/authors/?q=ai:khanna.sanjeevFrom the introduction: We consider the well-studied problem of finding a perfect matching in \(d\)-regular bipartite graphs with \(2n\) vertices and \(m=nd\) edges. While the best-known algorithm for general bipartite graphs takes \(O(m\sqrt{n})\) time, in regular bipartite graphs, a perfect matching is known to be computable in \(O(m)\) time. Very recently, the \(O(m)\) bound was improved to \(O(\min\{m,n^{2.5}\ln n/d\})\) expected time, an expression that is bounded by \(\tilde{O}(n^{1.75})\). In this paper, we further improve this result by giving an \(O(\min\{m,n^{2}\ln^3 n/d\})\) expected time algorithm for finding a perfect matching in regular bipartite graphs; as a function of \(n\) alone, the algorithm takes expected time \(O((n\ln n)^{1.5})\).The independence number of the orthogonality graph in dimension \(2^k\).https://zbmath.org/1449.052012021-01-08T12:24:00+00:00"Ihringer, Ferdinand"https://zbmath.org/authors/?q=ai:ihringer.ferdinand"Tanaka, Hajime"https://zbmath.org/authors/?q=ai:tanaka.hajimeThe authors determine the independence number of the orthogonality graph on \(2^k\)-dimensional hypercubes. This result is related to a question stated by \textit{V. Galliard} [Classical pseudo-telepathy and colouring graphs. Zürich: ETH Zürich (Dipl. Thesis) (2001)], who is motivated by a problem in quantum information theory. The applied method is a modification of a rank argument due to \textit{P. Frankl} [Combinatorica 6, 279--285 (1986; Zbl 0648.05031)] who showed the analogous result for \(4p^k\)-dimensional hypercubes, where \(p\) is an odd prime.
Reviewer: Mirko Lepović (Kragujevac)Tiling convex polygons with congruent isosceles right triangles.https://zbmath.org/1449.520122021-01-08T12:24:00+00:00"Chen, Hongjing"https://zbmath.org/authors/?q=ai:chen.hongjing"Su, Zhanjun"https://zbmath.org/authors/?q=ai:su.zhanjun"Zhang, Xiaopeng"https://zbmath.org/authors/?q=ai:zhang.xiaopengSummary: Let \({P_v}\) be a plane convex polygon with \(v\) vertices. It was proved that \({P_v}\) can be tiled with congruent equilateral triangles for \(v = 3, 4, 5, 6\). In this paper we consider the corresponding problem for isosceles right triangles and prove that if \({P_v}\) can be cut into finitely many congruent isosceles right triangles then \(v = 3, 4, 5, 6, 7, 8\). In particular, we determine the sets \(T = \{ (v,k):v \in \{3, 4, 5, \cdots \}, k \in \{1, 2, 3, \cdots\}\}\), and there exists a convex \(v\)-gon that can be tiled with \(k\) congruent isosceles right triangles. In particular, our results on tilings of pentagons are essentially based on a relation with the so-called idoneal numbers.Improved bounds for Rota's basis conjecture.https://zbmath.org/1449.050422021-01-08T12:24:00+00:00"Dong, Sally"https://zbmath.org/authors/?q=ai:dong.sally"Geelen, Jim"https://zbmath.org/authors/?q=ai:geelen.jimSummary: We prove that, if \(B_1,\ldots,B_n\) are disjoint bases of a rank-\(n\) matroid, then there are at least \(n/(7\log n)\) disjoint transversals of \(B_1,\ldots,B_n\) that are also bases.The asymptotic spectrum of graphs and the Shannon capacity.https://zbmath.org/1449.052082021-01-08T12:24:00+00:00"Zuiddam, Jeroen"https://zbmath.org/authors/?q=ai:zuiddam.jeroenAuthor's abstract: We introduce the asymptotic spectrum of graphs and apply the theory of asymptotic spectra of \textit{V. Strassen} [J. Reine Angew. Math. 384, 102--152 (1988; Zbl 0631.68033)] to obtain a new dual characterisation of the Shannon capacity of graphs. Elements in the asymptotic spectrum of graphs include the Lovász theta number, the fractional clique cover number, the complement of the fractional orthogonal rank and the fractional Haemers bound.
Reviewer: Ioan Tomescu (Bucureşti)Randić energy of two classes of corona graphs.https://zbmath.org/1449.051672021-01-08T12:24:00+00:00"Fu, Feiqin"https://zbmath.org/authors/?q=ai:fu.feiqin"Shao, Yanling"https://zbmath.org/authors/?q=ai:shao.yanlingSummary: Let \(G\) be a simple undirected graph, with vertex set \(V (G)= \{v_1, v_2, \cdots, v_n\}\). The Randić matrix of \(G\) is the matrix \(R (G)= (r_{ij})\), where \(r_{ij} =1/\sqrt{d_id_j}\) if the vertices \(v_i\) and \(v_j\) are adjacent and \(r_{ij} =0\) otherwise. The Randić energy \(\operatorname{RE}(G)\) is the sum of absolute values of the eigenvalues of \(R (G)\). The corona of \(G_1\circ G_2\) is obtained by connecting each vertex of \(G_1\) to all vertices of a copy of \(G_2\). In this paper, the Randić energy of corona graphs \(I_r (K_n)\) and \(K_n\circ K_m\) are studied.Hyper-atoms applied to the critical pair theory.https://zbmath.org/1449.110202021-01-08T12:24:00+00:00"Hamidoune, Yahya O."https://zbmath.org/authors/?q=ai:hamidoune.yahya-oThe sumset of two subsets \(A\) and \(B\) of an abelian group \(G\), is \(A+B=\{a+b \ | \ a\in A, b \in B \}.\) If \(A+B\) is aperiodic (that is the set has a trivial stabilizer), then it is known that \(|A+B| \geq |A|+|B| -1.\) \textit{J. H. B. Kemperman}'s theorem [Acta Math. 103, 63--88 (1960; Zbl 0108.25704)] describes the sets \(A\) and \(B\) for which \(|A+B| \leq |A|+|B| -1.\) Let \(\kappa_1(S) = \min \{ |X+S|-|S| \ | \ X\) is a finite subset of the group \(G\) with at least \(k\) elements satisfying \(|G \backslash (X+S)| \geq k \}.\) A maximal cardinality subgroup with \(\kappa_1(S) = |H+S| - |H|\) is a hyper-atom. The authors uses hyper-atoms to give a new isoperimetric proof of the Kemperman structure theorem which overcomes a previous weakness.
Reviewer: Steven T. Dougherty (Scranton)Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4.https://zbmath.org/1449.050762021-01-08T12:24:00+00:00"Fulek, Radoslav"https://zbmath.org/authors/?q=ai:fulek.radoslav"Kynčl, Jan"https://zbmath.org/authors/?q=ai:kyncl.janThe strong Hanani-Tutte theorem [\textit{W. T. Tutte}, J. Comb. Theory 8, 45--53 (1970; Zbl 0187.20803)] states that a graph is planar if it can be drawn in the plane such that no pair of independent edges cross an odd number of times.
This paper provides a counterexample to the possible extension of the strong Hanani-Tutte theorem for orientable surfaces of genus 4. Namely, the authors construct a graph of genus 5 that has a drawing on the orientable surface of genus 4, with every pair of independent edges crossing an even number of times.
Moreover, they construct a counterexample to the possible extension of the unified Hanani-Tutte theorem [\textit{R. Fulek} et al., Electron. J. Comb. 24, No. 3, Research Paper P3.18, 8 p. (2017; Zbl 1369.05045)] on the torus.
Reviewer: Stelian Mihalas (Timişoara)Incompatible intersection properties.https://zbmath.org/1449.052362021-01-08T12:24:00+00:00"Frankl, Peter"https://zbmath.org/authors/?q=ai:frankl.peter"Kupavskii, Andrey"https://zbmath.org/authors/?q=ai:kupavskii.andreyA family \(\mathcal{F}\) of sets \(F \subseteq [n]\) is \(r\)-wise \(t\)-intersecting if, for any \(F_1, F_2, \ldots, F_r\) \(\in \mathcal{F}\), \(|F_1 \cap F_2 \cap \cdots, F_r| \geq t\). It is observed that a 3-wise 1-intersecting family \(\mathcal{F}\) that is also 2-wise, 2-intersecting satisfies \(|\mathcal{F}| \leq 5n/16\) (and that if, in addition, \(\bigcap \mathcal{F} = \emptyset\), then \(|\mathcal{F}| \leq 2^{n-2}\)). It is conjectured that if \(\mathcal{F}\) is 3-wise 1-intersecting and 2-wise 3-intersecting, then \(|\mathcal{F}| \leq 2^{n-2}\). It is proved that if \(\mathcal{F}\) is 3-wise 1-intersecting and 2-wise 32-intersecting, then \(|\mathcal{F}| \leq 2^{n-2}\). The methods used in this difficult paper are elementary, and it is largely self-contained.
Reviewer: Gregory Loren McColm (Tampa)Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows.https://zbmath.org/1449.051262021-01-08T12:24:00+00:00"Dvořák, Zdeněk"https://zbmath.org/authors/?q=ai:dvorak.zdenek"Mohar, Bojan"https://zbmath.org/authors/?q=ai:mohar.bojan"Šámal, Robert"https://zbmath.org/authors/?q=ai:samal.robertSummary: ``We prove that, in several settings, a graph has exponentially many nowhere-zero flows. These results may be seen as a counting alternative to the well-known proofs of existence of \(\mathbb{Z}_{3}-, \mathbb{Z}_{4}-\), and \(\mathbb{Z}_{6}\)-flows. In the dual setting, proving exponential number of 3-colorings of planar triangle-free graphs is a related open question due to \textit{C. Thomassen} [J. Comb. Theory, Ser. B 102, No. 2, 521--529 (2012; Zbl 1239.05083)].''
Among other things, the authors prove that every 3-edge-connected cubic graph with \(n\) vertices has at least \(2^{n/5}\) nowhere-zero \(\mathbb{ Z}_{2}\times \mathbb{Z}_{3}\)-flows, any 3-edge-connected graph with \(n\) vertices has at least \(2^{n/7}\) nowhere-zero \(\mathbb{ Z}_{2}\times \mathbb{Z}_{3}\)-flows, any \(n\)-vertex graph with \(m\) edges having two disjoint spanning trees has at least \(\max\{2^{n/250},3^{m-2n+2}\}\) nowhere-zero \(\mathbb{ Z}_{2}\times \mathbb{Z}_{2}\)-flows and every 6-edge-connected graph with \(n\geq 2\) vertices has at least \(2^{(n-2)/12}\) nowhere-zero \(\mathbb{Z}_{3}\)-flows.
Reviewer: Ioan Tomescu (Bucureşti)The colouring number of infinite graphs.https://zbmath.org/1449.051892021-01-08T12:24:00+00:00"Bowler, Nathan"https://zbmath.org/authors/?q=ai:bowler.nathan"Carmesin, Johannes"https://zbmath.org/authors/?q=ai:carmesin.johannes"Komjáth, Péter"https://zbmath.org/authors/?q=ai:komjath.peter"Reiher, Christian"https://zbmath.org/authors/?q=ai:reiher.christianThe authors show that a graph has colouring number not larger than a given infinite cardinal if and only if it contains neither of two types of subgraph. This characterisation also re-establishes a previous result that every graph with infinite colouring number has a well-ordering of its vertices.
Reviewer: Hang Lau (Montréal)Highly-arc-transitive and descendant-homogeneous digraphs with finite out-valency.https://zbmath.org/1449.051192021-01-08T12:24:00+00:00"Amato, Daniela A."https://zbmath.org/authors/?q=ai:amato.daniela-aA digraph \(D\) is said to have property \(Z\) if there is a digraph homomorphism from \(D\) onto the digraph \(Z\). The descendant set of a vertex in a digraph \(D\) is the induced subdigraph on the set of vertices reachable from the given vertex by an outward-directed path. A digraph \(D\) is descendant-homogeneous if it is vertex-transitive and any isomorphism between finitely generated subdigraphs of \(D\) extends to an automorphism of \(D\). The present paper investigates highly-arc-transitive digraphs with a homomorphism onto \(Z\) which are, additionally, descendant-homogeneous. It is shown that if \(D\) is a highly-arc-transitive descendant-homogeneous digraph with property \(Z\) and \(F\) is the subdigraph spanned by the descendant sets of a line in \(D\), then \(F\) is a locally finite 2-ended digraph with property \(Z\). In addition if \(D\) has prime out-valency, then there is only one possibility for the subdigraph \(F\), which is then used to classify the highly-arc-transitive descendant-homogeneous digraphs of prime out-valency with property \(Z\).
Reviewer: Wai-Kai Chen (Fremont)Combinatorial identities for enumerations of equivalent classes with action of group on set.https://zbmath.org/1449.050302021-01-08T12:24:00+00:00"Tang, Shangang"https://zbmath.org/authors/?q=ai:tang.shangangSummary: By using Burnside-Polya enumerating method, principle of inclusion-exclusion and other combinatorial analysis, a class of combinatorial identities for equivalent classes with action of group on set are studied. Some combinatorial identities for enumerations of equivalent classes of a class of mapping under identical transformation group and cycle group and dihedral group actions are obtained. These results generalize some known results.Certain topological indices of line graph of Dutch windmill graphs.https://zbmath.org/1449.050672021-01-08T12:24:00+00:00"Sardar, Muhammad S."https://zbmath.org/authors/?q=ai:sardar.muhammad-sh"Zafar, Sohail"https://zbmath.org/authors/?q=ai:zafar.sohail"Zahid, Zohaib"https://zbmath.org/authors/?q=ai:zahid.zohaib"Farahani, Mohammad R."https://zbmath.org/authors/?q=ai:farahani.mohammad-reza"Wang, Shaohui"https://zbmath.org/authors/?q=ai:wang.shaohui"Naduvath, Sudev"https://zbmath.org/authors/?q=ai:naduvath.sudevSummary: A Dutch windmill graph \(D_n^{ (m)}\), \(m \ge 1\), \(n \ge 3\) is the graph obtained by taking \(m\) copies of the cycle graph \({C_n}\) with a vertex in common. In this paper, we compute certain topological indices such as the Zagreb indices, hyper-Zagreb indices, atom-bond connectivity index etc. of the line graph of a Dutch windmill graph.On the Harary index of the caterpillars.https://zbmath.org/1449.050622021-01-08T12:24:00+00:00"Ouyang, Gengxu"https://zbmath.org/authors/?q=ai:ouyang.gengxuSummary: The Harary index of a graph was defined as \(H (G) = \sum\limits_{\{ {u, v} \} \subset V(G)} {\frac{1}{{d({u, v})}}}\), where \(d ({u, v})\) was the distance between the vertex \(u\) and \(v\). In the paper, we proved that there must be a larger Harary index of caterpillar for any tree with order \(n\) and diameter \(d\) and characterized the maximal Harary index among all caterpillars with fixed diameter. Moreover, we derived the maximal and minimal Harary index of the double star-like trees.On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order.https://zbmath.org/1449.050072021-01-08T12:24:00+00:00"Sabri, Ahmad"https://zbmath.org/authors/?q=ai:sabri.ahmad"Vajnovszki, Vincent"https://zbmath.org/authors/?q=ai:vajnovszki.vincentSummary: A generalized (resp. \(p\)-ary) ballot sequence is a sequence over the set of non-negative integers (resp. integers less than \(p\)) where in any of its prefixes each positive integer \(i\) occurs at most as often as any integer less than \(i\). We show that the reflected Gray code order induces a cyclic 3-adjacent gray code on both, the set of fixed length generalized ballot sequences and \(p\)-ary ballot sequences when \(p\) is even, that is, ordered list where consecutive sequences (regarding the list cyclically) differ in at most 3 adjacent positions. Non-trivial efficient generating algorithms for these ballot sequences, in lexicographic order and for the obtained Gray codes, are also presented.Generalized Jacobsthal numbers and restricted \(k\)-ary words.https://zbmath.org/1449.050202021-01-08T12:24:00+00:00"Ramirez, José L."https://zbmath.org/authors/?q=ai:ramirez.jose-luis"Shattuck, Mark"https://zbmath.org/authors/?q=ai:shattuck.mark-aSummary: We consider a generalization of the problem of counting ternary words of a given length which was recently investigated by \textit{T. Koshy} and \textit{R. P. Grimaldi} [Fibonacci Q. 55, No. 2, 129--136 (2017; Zbl 1401.11042)]. In particular, we use finite automata and ordinary generating functions in deriving a \(k\)-ary generalization. This approach allows us to obtain a general setting in which to study this problem over a \(k\)-ary language. The corresponding class of \(n\)-letter \(k\)-ary words is seen to be equinumerous with the closed walks of length \(n-1\) on the complete graph for \(k\) vertices as well as a restricted subset of colored square-and-domino tilings of the same length. A further polynomial extension of the \(k\)-ary case is introduced and its basic properties deduced. As a consequence, one obtains some apparently new binomial-type identities via a combinatorial argument.On the largest part size and its multiplicity of a random integer partition.https://zbmath.org/1449.050242021-01-08T12:24:00+00:00"Mutafchiev, Ljuben"https://zbmath.org/authors/?q=ai:mutafchiev.lyuben-rSummary: Let \(\lambda\) be a partition of the positive integer \(n\) chosen uniformly at random among all such partitions. Let \(L_n = L_n(\lambda)\) and \(M_n = M_n(\lambda)\) be the largest part size and its multiplicity, respectively. For large \(n\), we focus on a comparison between the partition statistics \(L_n\) and \(L_n M_n\). In terms of convergence in distribution, we show that they behave in the same way. However, it turns out that the expectation of \(L_n M_n - L_n\) grows as fast as \(\frac{1}{2}\log n\). We obtain a precise asymptotic expansion for this expectation and conclude with an open problem arising from this study.Colourability and word-representability of near-triangulations.https://zbmath.org/1449.050942021-01-08T12:24:00+00:00"Glen, Marc Elliot"https://zbmath.org/authors/?q=ai:glen.marc-elliotSummary: A graph \(G = (V,E)\) is word-representable if there is a word \(w\) over the alphabet \(V\) such that \(x\) and \(y\) alternate in \(w\) if and only if the edge \((x,y)\) is in \(G\). It is known that all 3-colourable graphs are word-representable, while among those with a higher chromatic number some are word-representable while others are not. There has been some recent research on the word-representability of polyomino triangulations. It was shown, that a triangulation of a convex polyomino is word-representable if and only if it is 3-colourable; this result was extended to the case of a rectangular polyomino triangulation when a single domino tile is allowed. It was shown in that a near-triangulation is 3-colourable if and only if it is internally even. This paper provides a much shorter and more elegant proof of this fact, and also shows that near-triangulations are in fact a generalization of the polyomino triangulations studied earlier, and so we generalize the results of two former papers, and solve several open problems.Product diffusion in dynamic consumer social networks.https://zbmath.org/1449.910792021-01-08T12:24:00+00:00"Huang, Qiwei"https://zbmath.org/authors/?q=ai:huang.qiwei"Zhang, Yulin"https://zbmath.org/authors/?q=ai:zhang.yulin.1Summary: Considering the dynamics and the heterogeneity of consumer social networks, this paper establishes models to study the threshold of persistent diffusion of the monopolist's product by using the theories of complex network and differential equation. Three strategies are studied in the paper, including strategies without considering advertising or pricing, with consideration of advertising and with consideration of both advertising and pricing. The results show that, without considering advertising or pricing strategies, the threshold of persistent diffusion of the product depends on the properties and the dynamics of consumer social networks. When the company implements advertising and skimming pricing strategies, the product can persistently diffuse, which is related to the constrained condition of the price. The condition is unrelated to the properties of networks. In the remaining strategy situations, the product can persistently diffuse if there exist innovators.On strong, ideal and weak super magic graphs.https://zbmath.org/1449.052212021-01-08T12:24:00+00:00"Boonklurb, R."https://zbmath.org/authors/?q=ai:boonklurb.ratinan"Srichote, W."https://zbmath.org/authors/?q=ai:srichote.w"Singhun, S."https://zbmath.org/authors/?q=ai:singhun.siriratSummary: A graph \(G\), where \(|V (G)| = p\) and \(|E (G) = q|\), is called super magic if there exists a bijection \(f\) from \(V (G) \cup E (G)\) to \(\{1, 2, 3, \dots, p + q\}\) such that \(f (a) + f (b) + f (ab) = c^\prime (f)\) is a constant for any \(ab\in E (G)\), \(f (E (G)) = \{1, 2, 3, \dots, q\}\) and \(f (V (G)) = \{q+1, q+2, q+3, \dots, p+q\}\). The super magic strength of a graph \(G\) is defined as the minimum of all \(c^\prime (f)\) and is denoted by SMS\( (G)\). In this article bounds for super magic strength of some cycle-related graphs involving two parameters are given and the exact values of SMS of some cycle-related graphs involving two parameters are obtained. Moreover, if SMS is the set of all super magic graphs, then we can decompose SMS into 3 partite sets, which are strong, ideal and weak super magic, respectively. We categorize several interesting graphs involving two parameters into these partite sets.The further research on fuzzy transversal matroids.https://zbmath.org/1449.050432021-01-08T12:24:00+00:00"Wu, Deyin"https://zbmath.org/authors/?q=ai:wu.deyinSummary: The paper extends the conception of fuzzy transversal matroids to define more general fuzzy transversal matroids. With the help of the induced set function of fuzzy matroids, this paper proves that all of the fuzzy transversal matroids are closed. Then, fundamental sequences and induced matroid sequences of these fuzzy matroids are studied by the closed property. By the aid of these researches and the truncated fuzzy set family, the paper gets an equivalent characterization of independent fuzzy sets and fuzzy bases. Lastly, this paper finds out an equivalent characterization of which all of the fuzzy partial transversal of a fuzzy set family can compose a fuzzy transversal matroid.On the complexity for constructing a 3-colouring for planar graphs with short facets.https://zbmath.org/1449.051112021-01-08T12:24:00+00:00"Sirotkin, D. S."https://zbmath.org/authors/?q=ai:sirotkin.d-sThe article considers the problem of coloring (dividing) the vertices of an ordinary graph into three subsets of pairwise non-adjacent vertices. In [\textit{D. P. Dailey}, Discrete Math. 30, 289--293 (1980; Zbl 0448.05030)], it was shown that the 3-BP problem is NP-complete in the class of planar graphs with degrees of all vertices at most 4. Brooks's theorem says this problem is solvable in polynomial time for graphs with degrees of all vertices no more than 3. For planar graphs, all faces of which (including external ones) are triangles, the 3-BP problem is solvable in linear time. The main result of the investigation is formulated as a theorem showing that the 3-BP problem is NP-complete in the class of planar graphs with powers of all vertices not more than 5.
Reviewer: Tatuana Badokina (Saransk)Complete critical Ramsey numbers of cycle and \({K_4}\) numbers.https://zbmath.org/1449.051852021-01-08T12:24:00+00:00"Li, Yan"https://zbmath.org/authors/?q=ai:li.yan.7|li.yan.1|li.yan.5|li.yan.9|li.yan.8|li.yan.2|li.yan|li.yan.4|li.yan.3|li.yan.6|li.yan.10"Li, Yusheng"https://zbmath.org/authors/?q=ai:li.yusheng"Wang, Ye"https://zbmath.org/authors/?q=ai:wang.yeSummary: For graphs \(G\) and \(H\), Ramsey number \(r ({G, H})\) is the smallest integer \(r\) such that every red/blue edge coloring of \({K_r}\) contains either a red copy of \(G\), or a blue copy of \(H\). The complete critical Ramsey number \({r_K} ({G, H})\) is the largest integer \(n\) such that every 2-coloring of \({K_r} - {K_n}\) contains either a red copy of \(G\), or a blue copy of \(H\). When the positive integer \(n \ge 5\), \({r_K} ({C_n}, {K_4}) = \lfloor {n/2} \rfloor\), \({C_n}\) is a cycle with \(n\) vertices.Difference bases in finite abelian groups.https://zbmath.org/1449.050342021-01-08T12:24:00+00:00"Banakh, Taras"https://zbmath.org/authors/?q=ai:banakh.taras-o"Gavrylkiv, Volodymyr"https://zbmath.org/authors/?q=ai:gavrylkiv.volodymyr-mSummary: A subset \(B\) of a group \(G\) is called a difference basis of \(G\) if each element \(g\in G\) can be written as the difference \(g =ab^{-1}\) of some elements \(a,b\in B\). The smallest cardinality \(|B|\) of a difference basis \(B\subset G\) is called the difference size of \(G\) and is denoted by \(\Delta [G]\). The fraction \(\partial [G]:=\Delta [G]/\sqrt{|G|}\) is called the difference characteristic of \(G\). Using properties of the Galois rings, we prove recursive upper bounds for the difference sizes and characteristics of finite abelian groups. In particular, we prove that for a prime number \(p\geq 11\), any finite abelian \(p\)-group \(G\) has difference characteristic \(\partial [G]<\frac{\sqrt{p}-1}{\sqrt{p}-3}\cdot \sup \partial [C_{p^k}]<\sqrt{2}\cdot \frac{\sqrt{p}-1}{\sqrt{p}-3}\). Also we calculate the difference sizes of all abelian groups of cardinality less than 96.A recursive method for perfect matching number classified with saturation of a certain vertex.https://zbmath.org/1449.052132021-01-08T12:24:00+00:00"Tang, Baoxiang"https://zbmath.org/authors/?q=ai:tang.baoxiang"Ren, Han"https://zbmath.org/authors/?q=ai:ren.hanSummary: Two new graphs \(2 - 2n{K_5}\) and \(2 - n{Z_5}\) are constructed. Using the nested recursive method, two recursive relations of the perfect matching numbers of graphs \(2 - 2n{K_5}\) and \(2 - n{Z_5}\) are obtained, and then the two recursive general solutions are solved. Thus, the formula for calculating the perfect matching number of these two types of graphs is obtained.Characterization of the cross-linked fibrils under axial motion constraints with graphs.https://zbmath.org/1449.530022021-01-08T12:24:00+00:00"Nagy Kem, Gyula"https://zbmath.org/authors/?q=ai:nagy-kem.gyulaSummary: The filament networks play a significant role in biomaterials as structural stability and transmit mechanical signs. Introducing a 3D mechanical model for the infinitesimal motion of cross-linked fibrils under axial motion constraints, we provide a graph theoretical model and give the characterization of the flexibility and the rigidity of this framework. The connectedness of the graph \(G(v,r)\) of the framework in some cases characterizes the flexibility and rigidity of these structures. In this paper, we focus on the kinematical properties of fibrils and proof the next theorem for generic nets of fibrils that are cross-linked by another type of fibrils. ``If the fibrils and the bars are generic positions, the structure will be rigid if and only if each of the components of \(G(v,r)\) has at least one circuit.'' We offer some conclusions, including perspectives and future developments in the frameworks of biostructures as microtubules, collagens, celluloses, actins, other polymer networks, and composite which inspired this work.Generalized dominoes tiling's Markov chain mixes fast.https://zbmath.org/1449.050462021-01-08T12:24:00+00:00"Kayibi, K. K."https://zbmath.org/authors/?q=ai:kayibi.koko-kalambay"Samee, U."https://zbmath.org/authors/?q=ai:samee.umatul|samee.uma"Merajuddin"https://zbmath.org/authors/?q=ai:merajuddin.pirzada|merajuddin.m"Pirzada, S."https://zbmath.org/authors/?q=ai:pirzada.shariefuddinSummary: A generalized tiling is defined as a generalization of the properties of tiling a region of \(\mathbb{Z}^2\) with dominoes, and comprises tiling with rhombus and any other tilings that admits height functions which can be ordered into a distributive lattice. By using properties of the distributive lattice, we prove that the Markov chain consisting of moving from one height function to the next by a flip is fast mixing and the mixing time \(\tau(\epsilon)\) is given by \(\tau(\epsilon)\leq(kmn)^3(mn\;\ln\;k+\ln\;\epsilon^{-1})\), where \(mn\) is the area of the grid \(\Gamma\) that is a \(k\)-regular polycell. This result generalizes the result of \textit{K. K. Kayibi} and \textit{S. Pirzada} [Theor. Comput. Sci. 714, 1--14 (2018; Zbl 1387.05043)] and improves on the mixing time obtained by using coupling arguments by \textit{N. Destainville} [in: Discrete models: combinatorics, computation, and geometry. Proceedings of the 1st international conference (DM-CCG), Paris, France, July 2--5, 2001. Paris: Maison de l'Informatique et des Mathématiques Discrètes (MIMD). 1--22 (2001; Zbl 1017.68148)] and by \textit{M. Luby} et al. [SIAM J. Comput. 31, No. 1, 167--192 (2001; Zbl 0992.82013)].Enumeration of permutations avoiding a triple of 4-letter patterns is almost all done.https://zbmath.org/1449.050142021-01-08T12:24:00+00:00"Callan, David"https://zbmath.org/authors/?q=ai:callan.david"Mansour, Toufik"https://zbmath.org/authors/?q=ai:mansour.toufik"Shattuck, Mark"https://zbmath.org/authors/?q=ai:shattuck.mark-aSummary: This paper basically completes a project to enumerate permutations avoiding a triple \(T\) of 4-letter patterns, in the sense of classical pattern avoidance, for every \(T\). There are 317 symmetry classes of such triples \(T\) and previous papers have enumerated avoiders for all but 14 of them. One of these 14 is conjectured not to have an algebraic generating function. Here, we find the generating function for each of the remaining 13, and it is algebraic in each case.Cycles and complete \(k\)-partite graphs among Gallai graphs.https://zbmath.org/1449.051542021-01-08T12:24:00+00:00"Hao, Chen"https://zbmath.org/authors/?q=ai:hao.chen"Xie, Yikang"https://zbmath.org/authors/?q=ai:xie.yikang"Xue, Nan"https://zbmath.org/authors/?q=ai:xue.nan"Yang, Weihua"https://zbmath.org/authors/?q=ai:yang.weihuaSummary: Let \(G\) be a graph with \(E(G)\ne \emptyset\). The Gallai graph \(Gal (G)\) of a graph \(G\) has the edges of \(G\) as its vertices, and two distinct vertices \(e\) and \(f\) of \(\mathrm{Gal}(G)\) are adjacent in \(\mathrm{Gal}(G)\) if the edges \(e\) and \(f\) of \(G\) are adjacent in \(G\) but do not span a triangle in \(G\). Clearly, the Gallai graph \(\mathrm{Gal}(G)\) is a spanning subgraph of the well-known line graph \(L (G)\) of \(G\). In this paper, we characterize those graphs whose Gallai graphs are cycles and complete \(k\)-partite graphs, respectively.The research on a complex network analysis method for constructing waveform modes.https://zbmath.org/1449.900632021-01-08T12:24:00+00:00"Peng, Yali"https://zbmath.org/authors/?q=ai:peng.yali"Yang, Yuxin"https://zbmath.org/authors/?q=ai:yang.yuxin"Zeng, Xinyi"https://zbmath.org/authors/?q=ai:zeng.xinyi"Deng, Jiangang"https://zbmath.org/authors/?q=ai:deng.jiangangSummary: Based on the actual data of public bicycles, the stock time series of the distribution points is transformed into finite modal sequences to further analyze the time series volatility and extract the key features of the sequence, and the complex network of the fluctuating modal group is constructed. Based on the analysis of sliding window and modal parameters, the stock collection of public bicycles is taken to provide the basis for system optimization. The empirical study shows that the network characteristics are related to the size of the sliding window, the degree of the network, and the weighted clustering coefficient. By choosing the optimal parameters, a feasible and efficient solution for optimizing the scheduling time of the common bicycle system is proposed.A survey on total coloring of graphs.https://zbmath.org/1449.051182021-01-08T12:24:00+00:00"Zhu, Enqiang"https://zbmath.org/authors/?q=ai:zhu.enqiangSummary: The total coloring of a graph is the generalization of its vertex coloring and edge coloring, whose requirement is to assign colors to both its vertices and edges such that any adjacent element (adjacent vertices and adjacent edges) and incident elements (vertices and edges) do not receive the same color. The total chromatic number of a graph is the minimum integer for which the graph admits a total coloring. In terms of this graph parameter, different researchers independently proposed an identical conjecture: every graph has a total coloring using at most \(\Delta + 2\) colors, where \(\Delta\) denotes the maximum degree of the graph. This conjecture is still open. This paper will present a comprehensive survey on this topic.On the maximal connected component with faulty vertices on the class of hypercube-like networks.https://zbmath.org/1449.052312021-01-08T12:24:00+00:00"Zhai, Dengxin"https://zbmath.org/authors/?q=ai:zhai.dengxin"Aygul, Mamut"https://zbmath.org/authors/?q=ai:aygul.mamutSummary: In this paper, the number of vertices of the maximal connected component of hypercube-like networks \(HL_n\) with faulty vertices is studied, and the following conclusion is obtained. If the faulty vertex set \(F\) satisfies \(|F| \le kn - \frac{k (k + 1)}{2}\), then the number of vertices of the maximal connected component is at least \({2^n} - |F| - (k - 1)\).A survey on uniquely colorable graphs.https://zbmath.org/1449.051082021-01-08T12:24:00+00:00"Li, Zepeng"https://zbmath.org/authors/?q=ai:li.zepengSummary: A graph is uniquely colorable if it has only one proper coloring up to permutation of the colors. It has been proven that the problem of determining whether a graph is uniquely colorable is NP-hard. In this survey, we present the most important results on uniquely colorable graphs, especially on uniquely 3-colorable planar graphs, from the aspects of structural property, existence and construction and summarize some problems that have not been solved.A survey on not necessarily proper colorings under which certain pairs of vertices are distinguished by non-multiple color sets.https://zbmath.org/1449.050902021-01-08T12:24:00+00:00"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangenSummary: In this paper we give a brief introduction to research advances on general edge coloring (resp., \(V\)-total coloring, \(I\)-total coloring, \(E\)-total coloring, \(VI\)-total coloring, \(VE\)-total coloring, \(IE\)-total coloring, general total coloring) under which any two distinct vertices (or any two adjacent vertices, or any two distinct vertices between which the distance is at most \(d\)) are distinguished by non-multiple color set.A generalization of André-Jeannin's symmetric identity.https://zbmath.org/1449.050272021-01-08T12:24:00+00:00"Munarini, Emanuele"https://zbmath.org/authors/?q=ai:munarini.emanueleSummary: \textit{R. André-Jeannin} [Fibonacci Q. 35, No. 1, 68--74 (1997; Zbl 0879.11006)] obtained a symmetric identity involving the reciprocal of the Horadam numbers \(W_n\), defined by a three-term recurrence \(W_{n+2}= PW_{n+1} - QW_n\) with constant coefficients. In this paper, we extend this identity to sequences \(\{a_n\}_{n\in N}\) satisfying a three-term recurrence \(a_{n+2} = p_{n+1} a_{n+1} + q_{n+1} a_n\) with arbitrary coefficients. Then, we specialize such an identity to several \(q\)-polynomials of combinatorial interest, such as the \(q\)-Fibonacci, \(q\)-Lucas, \(q\)-Pell, \(q\)-Jacobsthal, \(q\)-Chebyshev and \(q\)-Morgan-Voyce polynomials.Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns.https://zbmath.org/1449.050042021-01-08T12:24:00+00:00"Callan, David"https://zbmath.org/authors/?q=ai:callan.david"Mansour, Toufik"https://zbmath.org/authors/?q=ai:mansour.toufikSummary: This paper is one of a series whose goal is to enumerate the avoiders, in the sense of classical pattern avoidance, for each triple of 4-letter patterns. There are 317 symmetry classes of triples of 4-letter patterns, avoiders of 267 of which have already been enumerated. Here we enumerate avoiders for all small Wilf classes that have a representative triple containing the pattern 1342, giving 40 new enumerations and leaving only 13 classes still to be enumerated. In all but one case, we obtain an explicit algebraic generating function that is rational or of degree 2. The remaining one is shown to be algebraic of degree 3. We use standard methods, usually involving detailed consideration of the left to right maxima, and sometimes the initial letters, to obtain an algebraic or functional equation for the generating function.Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns.https://zbmath.org/1449.050032021-01-08T12:24:00+00:00"Callan, David"https://zbmath.org/authors/?q=ai:callan.david"Mansour, Toufik"https://zbmath.org/authors/?q=ai:mansour.toufikSummary: Recently, it has been determined that there are 242 Wilf classes of triples of 4-letter permutation patterns by showing that there are 32 non-singleton Wilf classes. Moreover, the generating function for each triple lying in a non-singleton Wilf class has been explicitly determined. In this paper, toward the goal of enumerating avoiders for the singleton Wilf classes, we obtain the generating function for all but one of the triples containing 1324. (The exceptional triple is conjectured to be intractable.) Our methods are both combinatorial and analytic, including generating trees, recurrence relations, and decompositions by left-right maxima. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence amenable to the kernel method.Forests and pattern-avoiding permutations modulo pure descents.https://zbmath.org/1449.050012021-01-08T12:24:00+00:00"Baril, Jean-Luc"https://zbmath.org/authors/?q=ai:baril.jean-luc"Kirgizov, Sergey"https://zbmath.org/authors/?q=ai:kirgizov.sergey"Petrossian, Armen"https://zbmath.org/authors/?q=ai:petrossian.armenSummary: We investigate an equivalence relation on permutations based on the pure descent statistic. Generating functions are given for the number of equivalence classes for the set of all permutations, and the sets of permutations avoiding exactly one pattern of length three. As a byproduct, we exhibit a permutation set in one-to-one correspondence with forests of ordered binary trees, which provides a new combinatorial class enumerated by the single-source directed animals on the square lattice. Furthermore, bivariate generating functions for these sets are given according to various statistics.Computing all Laplacian H-eigenvalues for a uniform loose path of length three.https://zbmath.org/1449.051952021-01-08T12:24:00+00:00"Yue, Junjie"https://zbmath.org/authors/?q=ai:yue.junjie"Zhang, Liping"https://zbmath.org/authors/?q=ai:zhang.lipingSummary: The spectral theory of Laplacian tensor is an important tool for revealing some important properties of a hypergraph. It is meaningful to compute all Laplacian H-eigenvalues for some special \(k\)-uniform hypergraphs. For a \(k\)-uniform loose path of length three, the Laplacian H-spectrum has been studied when \(k\) is odd. However, all Laplacian H-eigenvalues of a \(k\)-uniform loose path of length three have not been found out. In this paper, we compute all Laplacian H-eigenvalues for a \(k\)-uniform loose path of length three. We show that the number of Laplacian H-eigenvalues of an odd(even)-uniform loose path with length three is 7(14). Some numerical results are given to show the efficiency of our method. Especially, the numerical results show that its Laplacian H-spectrum converges to \(\{0, 1, 1.5, 2\}\) when \(k\) goes to infinity. Finally, we show that the convergence of the Laplacian H-spectrum from theoretical analysis.Total irregularity strength of cycle related graphs with pendent edges.https://zbmath.org/1449.052232021-01-08T12:24:00+00:00"Ibrahim, M."https://zbmath.org/authors/?q=ai:ibrahim.mamane-souley|ibrahim.malik-muhammad|ibrahim.mazlinda|ibrahim.muhammad-jamilu|ibrahim.mahmoud-a|ibrahim.mohd-shafiq|ibrahim.muhammed-a|ibrahim.michael-nawar|ibrahim.musthafa|ibrahim.mohd-zamri|ibrahim.m-m-a|ibrahim.m-a-k|ibrahim.mohd-asrul-hery|ibrahim.mohammed-olanrewaju|ibrahim.makram|ibrahim.mohammed-ali-faya|ibrahim.m-n-m|ibrahim.mahmud|ibrahim.mansor-h|ibrahim.mohd-faisal|ibrahim.mohamed-hamdi|ibrahim.maged-h|ibrahim.moustafa|ibrahim.marc|ibrahim.mariam|ibrahim.muhammad-talal|ibrahim.mohamed-hamza|ibrahim.mohamed-a|ibrahim.m-k"Siddiqui, M. K."https://zbmath.org/authors/?q=ai:siddiqui.mohammad-khubeb|siddiqui.muhammad-kamran"Shabir, S."https://zbmath.org/authors/?q=ai:shabir.s"Nadeem, M."https://zbmath.org/authors/?q=ai:nadeem.muhammed|nadeem.mohd|nadeem.muhammad|nadeem.muhammad-faisal|nadeem.mehrozSummary: Let \(G=(V,E)\) be a graph. A total labeling \(\psi:V\cup E\to\{1,2,\dots,k\}\) is called totally irregular total \(k\)-labeling of \(G\) if every two distinct vertices \(u\) and \(v\) in \(V(G)\) satisfy \(wt(u)\neq wt(v)\), and every two distinct edges \(u_1u_2\) and \(v_1v_2\) in \(E(G)\) satisfy \(wt(u_1u_2)\neq wt(v_1v_2)\), where \(wt(u)=\psi(u)+\sum_{uv\in E(G)}\psi(uv)\) and \(wt(u_1u_2)=\psi(u_1)+\psi(u_1u_2)+\psi(u_2)\). The minimum \(k\) for which a graph \(G\) has a totally irregular total \(k\)-labeling is called the total irregularity strength of \(G\), denoted by \(ts(G)\).
In this paper, we determine the exact value of the total irregularity strength of cycle related graphs (convex polytopes) with pendent edges.Two upper bounds for the Gutman indices of (four) F-sums of graphs.https://zbmath.org/1449.050542021-01-08T12:24:00+00:00"An, Mingqiang"https://zbmath.org/authors/?q=ai:an.mingqiang"Xiong, Liming"https://zbmath.org/authors/?q=ai:xiong.limingSummary: The Gutman index (also known as Schultz index of the second kind) of a graph \(G\) is defined as \(DD_*(G)=\sum_{\{u,v\}\subseteq V(G)}[d_G(u)d_G(v)]d(u,v|G)\), where \(d_G(u)\) denotes the degree of a vertex \(u\) in \(G\) and \(d(u,v|G)\) denotes the distance between two vertices \(u\) and \(v\) in \(G\). In this paper, we establish two upper bounds for the Gutman indices of four sums of two graphs in terms of other indices of two individual graphs.Exponents of the primitive Boolean matrices with fixed girth.https://zbmath.org/1449.051782021-01-08T12:24:00+00:00"Yu, Guanglong"https://zbmath.org/authors/?q=ai:yu.guanglong"Guo, Shuguang"https://zbmath.org/authors/?q=ai:guo.shuguang"Jia, Wenjuan"https://zbmath.org/authors/?q=ai:jia.wenjuan"Che, Yuhan"https://zbmath.org/authors/?q=ai:che.yuhanSummary: The girth of a primitive Boolean matrix is defined to be the girth of its associated digraph. In this paper, among all primitive Boolean matrices of order \(n\), the primitive exponents of those of girth \(g\) are considered. For the primitive matrices of both order \(n\geq 10\) and girth \(g>\frac{n^2-4n}{4(n-3)}\), the matrices with primitive exponents in \([2n-2+(g-1)(n-3),n+g(n-2)]\) are completely characterized.Markov spectral clustering algorithm with DCBM for community detection.https://zbmath.org/1449.910852021-01-08T12:24:00+00:00"Ren, Shuxia"https://zbmath.org/authors/?q=ai:ren.shuxia"Zhang, Shubo"https://zbmath.org/authors/?q=ai:zhang.shubo"Wu, Tao"https://zbmath.org/authors/?q=ai:wu.taoSummary: Spectral clustering algorithm is one of the classical community detection algorithms. Due to the current constructed similarity graphs carry less community structure information, the actual clustering effect has a big gap with the ideal clustering effect. Therefore, based on degree corrected stochastic block model and Markov chain, a novel spectral clustering approach for community detection, called MSCD, is proposed. Firstly, probability matrix composed of the connection probability between nodes is introduced based on DCBM, and the mapping relationship is established between probability matrix and similar matrix. Then, Markov chain is utilized to reconstruct the similar graph of spectral clustering. Finally, the reconstructed similar graph is used to partition the networks into clusters. Three typical algorithms of SC, MRW-KNN and FluidC are performed on synthetic networks and real networks. Comparative experiments show that the MSCD algorithm has more efficient clustering performance and can reveal a clearer community.On the irregularity of cacti.https://zbmath.org/1449.050522021-01-08T12:24:00+00:00"Liu, Yang"https://zbmath.org/authors/?q=ai:liu.yang.14"Li, Jianxi"https://zbmath.org/authors/?q=ai:li.jianxiSummary: The irregularity of a graph \(G\) is defined as the sum of weights \(|d_G(v_i)-d_G(v_j)|\) of all edges \(v_iv_j\) of \(G\), where \(d_G(v_i)\) and \(d_G(v_j)\) are the degrees of the vertices \(v_i\) and \(v_j\) in \(G\), respectively. In this paper, the graphs with maximum irregularity among all cacti, all cacti with a given number of pendent vertices and all cacti with a perfect matching are determined, respectively.The square mapping graph of \(2\times 2\) matrix rings over prime fields.https://zbmath.org/1449.051392021-01-08T12:24:00+00:00"Tang, Gaohua"https://zbmath.org/authors/?q=ai:tang.gaohua"Zhang, Hengbin"https://zbmath.org/authors/?q=ai:zhang.hengbin"Wei, Yangjiang"https://zbmath.org/authors/?q=ai:wei.yangjiangSummary: Let \(R\) be a ring with identity. The square mapping graph of \(R\) is a digraph \(\Gamma(R)\) defined on the elements of \(R\) and with an edge from a vertex a to \(a\) vertex \(b\) if and only if \(a^2=b\). Let \(\mathbb{M}_2(\mathbb{Z}_p)\) be the \(2\times 2\) matrix ring over the field \(\mathbb{Z}_p\), where \(p\) is prime. In this paper, we completely determine the structure of \(\Gamma(\mathbb{M}_2(\mathbb{Z}_p))\) by showing its two disjoint induced subgraphs.A note on the Erdős-Faber-Lovász conjecture: quasigroups and complete digraphs.https://zbmath.org/1449.050862021-01-08T12:24:00+00:00"Araujo-Pardo, G."https://zbmath.org/authors/?q=ai:araujo-pardo.gabriela"Rubio-Montiel, C."https://zbmath.org/authors/?q=ai:rubio-montiel.christian"Vázquez-Ávila, A."https://zbmath.org/authors/?q=ai:vazquez-avila.adrianSummary: A decomposition of a simple graph \(G\) is a pair \((G,P)\) where \(P\) is a set of subgraphs of \(G\), which partitions the edges of \(G\) in the sense that every edge of \(G\) belongs to exactly one subgraph in \(P\). If the elements of \(P\) are induced subgraphs then the decomposition is denoted by \([G,P]\).
A \(k\)-\(P\)-coloring of a decomposition \((G,P)\) is a surjective function that assigns to the edges of \(G\) a color from a \(k\)-set of colors, such that all edges of \(H\in P\) have the same color, and, if \(H_1, H_2\in P\) with \(V(H_1)\cap V(H_2)\neq\emptyset\) then \(E(H_1)\) and \(E(H_2)\) have different colors. The chromatic index \(\chi^\prime((G,P))\) of a decomposition \((G,P)\) is the smallest number \(k\) for which there exists a \(k\)-\(P\)-coloring of \((G,P)\).
The well-known Erdős-Faber-Lovász conjecture states that any decomposition \([K_n,P]\) satisfies \(\chi^\prime([K_n,P])\leq n\). We use quasigroups and complete digraphs to give a new family of decompositions that satisfy the conjecture.Maximum genus and independent set.https://zbmath.org/1449.050742021-01-08T12:24:00+00:00"Dong, Guanghua"https://zbmath.org/authors/?q=ai:dong.guanghua"Ren, Han"https://zbmath.org/authors/?q=ai:ren.han"Huang, Yuanqiu"https://zbmath.org/authors/?q=ai:huang.yuanqiu"Wang, Ning"https://zbmath.org/authors/?q=ai:wang.ningSummary: In this paper, we obtained two results, one is for the maximum genus, and the other is for the independence number. (i) Let \(G\) be a connected graph with minimum degree at least \(3\) and \(A=\{v_1,v_2,\dots,v_m\}\) be an independent set such that \(G-A\) is connected, then \(\gamma_M(G)\geq\gamma_M(G-\{v_1,v_2,\dots,v_m\})+\frac{1}{2}\sum_{i=1}^m(d(v_i)-\varepsilon_i)\), where \(\varepsilon_i=1\) if \(d(v_i)\equiv 1\pmod{2}\) and \(\varepsilon_i=2\) otherwise. (ii) Let \(G\) be a connected \(3\)-regular graph and \(A=\{x_1,x_2,\dots,x_{\gamma_M(G)}\}\) be a maximum non-separating independent set of \(G\), then its independence number \(\alpha(G)\geq\gamma_M(G)+\alpha(G-\mathcal{N}_A)\), where \(\mathcal{N}_A\) is the closed neighborhood of the set \(A\).On super totient numbers, with applications and algorithms to graph labeling.https://zbmath.org/1449.052262021-01-08T12:24:00+00:00"Mahmood, M. Khalid"https://zbmath.org/authors/?q=ai:mahmood.muhammad-khalid"Ali, Shahbaz"https://zbmath.org/authors/?q=ai:ali.shahbazSummary: For any subset \(S=\{0,1,2,n-1\}\) of integers, the number \(\varphi(n)\) count the members of \(S\) which are co-prime to \(n\). We attach an additional property to these numbers as: if the elements of \(S\) which are relatively prime to \(n\) can be separated into two disjoint subsets of equal sums then \(n\) is called a super totient number. Let \(G=(V,E)\) be a given graph. A monotonically increasing function \(h\) on the set of vertices \(V\) of \(G\) into subset of natural numbers will be called super totient labeling of \(G\), if the function \(h^{\ast}\) on the set of edges \(E\) of \(G\) into natural numbers given by \(h^{\ast}(ab)=h(a)h(b)\) gives a super totient number for all edges \(ab\in E\), where \(a,b\in V\). Graphs admitting such functions will be termed as super totient graphs. A complete characterization of super totient numbers together with their applications and algorithms in graph labeling for some classes of well-known graphs such as lattice graphs, binary tree graphs and \(k\)-ary tree graphs is proposed.A note on list edge coloring of planar graphs without adjacent short cycles.https://zbmath.org/1449.050992021-01-08T12:24:00+00:00"Hu, Linna"https://zbmath.org/authors/?q=ai:hu.linna"Song, Huimin"https://zbmath.org/authors/?q=ai:song.huimin"Wu, Jian-Liang"https://zbmath.org/authors/?q=ai:wu.jian-liangSummary: 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 \(\varphi\) of \(G\) such that \(\varphi(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 all \(e\in E(G)\), then \(G\) is said to be edge-\(k\)-choosable. In this paper, we prove that a planar graph \(G\) is edge-\((\Delta(G)+1)\)-choosable if any \(4\)-cycle is not adjacent to a \(3\)-cycle, or \(\Delta(G)\geq 6\) and any two \(4\)-cycles are not adjacent.A proof technique for skewness of graphs.https://zbmath.org/1449.051272021-01-08T12:24:00+00:00"Chia, Gek L."https://zbmath.org/authors/?q=ai:chia.gek-ling"Lee, Chan L."https://zbmath.org/authors/?q=ai:lee.chan-lye"Ling, Yan Hao"https://zbmath.org/authors/?q=ai:ling.yan-haoSummary: The skewness of a graph \(G\) is the minimum number of edges in \(G\) whose removal results in a planar graph. By appropriately introducing a weight to each edge of a graph, we determine, among other things, the skewness of the generalized Petersen graph \(P(4k,k)\) for odd \(k\geq 9\). This provides an answer to the conjecture raised in [\textit{G. L. Chia} and \textit{C. L. Lee}, Front. Math. China 7, No. 3, 427--436 (2012; Zbl 1252.05042)].Partitioning the vertices of a graph into a total dominating set and an independent dominating set.https://zbmath.org/1449.051992021-01-08T12:24:00+00:00"Delgado, Pamela"https://zbmath.org/authors/?q=ai:delgado.pamela"Desormeaux, Wyatt J."https://zbmath.org/authors/?q=ai:desormeaux.wyatt-j"Haynes, Teresa W."https://zbmath.org/authors/?q=ai:haynes.teresa-wSummary: We study graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set and say that such graphs have a TDID-partition. In particular, we develop several sufficient conditions for a graph to have a TDID-partition. We show that, with the exception of a few graphs, every graph or its complement has a TDID-partition. From this result, it follows that with the exception of the cycle on five vertices, every non-trivial, self-complementary graph has such a partition. Further, we characterize the trees having a TDID-partition. Noting that the independent set in a TDID-partition of a graph \(G\) is a restrained dominating set, our results imply bounds on the restrained domination number of \(G\).Super connectivity of Kronecker products with complete multipartite graphs.https://zbmath.org/1449.051622021-01-08T12:24:00+00:00"Zhao, Shuang"https://zbmath.org/authors/?q=ai:zhao.shuang"Tian, Yingzhi"https://zbmath.org/authors/?q=ai:tian.yingzhi"Meng, Jixiang"https://zbmath.org/authors/?q=ai:meng.jixiangSummary: Let \(G_1\) and \(G_2\) be two graphs. The Kronecker product \(G_1\times G_2\) has vertex set \(V(G_1\times G_2)=V(G_1)\times V(G_2)\) and edge set \(E(G_1\times G_2)=\{(u_1,v_1)(u_2,v_2)\colon u_1u_2\in E(G_1)\) and \(v_1v_2\in E(G_2)\}\). In this paper, we determine the super connectivity of \(K_{p_1,p_2,\dots,p_r}\times K_n\) for \(n\geq 3\). In addition, we show that if \(G\) is a nonbipartite graph with \(\kappa(G)=\delta(G)\), then \(G\times K_{p_1,p_2,\dots,p_r}\) is super-\(\kappa\), where the sequence \(p_1,p_2,\dots,p_r\) satisfies \((1)\,r\geq 3\), \((2)\,p_1\leq p_2\leq\dots\leq p_r\), \((3)\,\sum_{i=1}^{r-2}p_i\geq p_{r-1}\).On binomial double sums with Fibonacci and Lucas numbers. II.https://zbmath.org/1449.110312021-01-08T12:24:00+00:00"Kılıç, Emrah"https://zbmath.org/authors/?q=ai:kilic.emrah"Taşdemir, Funda"https://zbmath.org/authors/?q=ai:tasdemir.fundaSummary: In this paper, we compute various binomial-double-sums involving the Fibonacci numbers as well as their alternating analogous. It would be interesting that all sums we shall compute are evaluated in nice multiplication forms in terms of again the Fibonacci and Lucas numbers.
For Part I, see Ars Comb. 144, 173--185 (2019; Zbl 07144788).On the \(\lambda\)-fold spectra of tripartite multigraphs of order 4 and size 5.https://zbmath.org/1449.051842021-01-08T12:24:00+00:00"Bunge, R. C."https://zbmath.org/authors/?q=ai:bunge.ryan-c"El-Zanati, S. I."https://zbmath.org/authors/?q=ai:el-zanati.saad-i-el-zanati"Febles Miranda, L."https://zbmath.org/authors/?q=ai:febles-miranda.l"Guadarrama, J. P."https://zbmath.org/authors/?q=ai:guadarrama.j-p"Roberts, D. P."https://zbmath.org/authors/?q=ai:roberts.dan-p"Song, E."https://zbmath.org/authors/?q=ai:song.eunhye|song.enbing|song.eunjung|song.enmin|song.erping|song.eddie|song.erxiang|song.enbin|song.enming"Zale, A."https://zbmath.org/authors/?q=ai:zale.aThere are three non-isomorphic multigraphs \(\{G_1,G_2,G_3\}\) with five edges whose underlying simple graph is a triangle with a pendant edge (equivalently, a graph with degree sequence \((3,2,2,1)\)). This paper examines edge-decompositions of \(\lambda\)-fold copies of the complete graph \(K_n\) into copies of \(G_i\), for each \(i\in\{1,2,3\}\). Necessary conditions on existence are established for each \(G_i\) and each \(n\), and shown to be sufficient.
Reviewer: Charles J. Colbourn (Tempe)Path-transformation graph of maximum matchings.https://zbmath.org/1449.052102021-01-08T12:24:00+00:00"Liu, Yan"https://zbmath.org/authors/?q=ai:liu.yan.3|liu.yan.6|liu.yan.4|liu.yan.2|liu.yan|liu.yan.1|liu.yan.8|liu.yan.5|liu.yan.7"Lei, Mengxia"https://zbmath.org/authors/?q=ai:lei.mengxia"Huang, Xiaoxian"https://zbmath.org/authors/?q=ai:huang.xiaoxianSummary: The path-transformation graph of maximum matchings of a graph \(G\), denoted by \(\mathcal{NM} (G)\), is a graph whose vertices are maximum matchings of \(G\) and two maximum matchings \({M_1}\) and \({M_2}\) are adjacent in \(\mathcal{NM} (G)\) if the symmetric difference of \({M_1}\) and \({M_2}\) induces a path (there is no limit for the length of the path). In this paper, we study the connectivity of the transformation graph, and obtain the necessary and sufficient condition under which the transformation graph is a complete graph or a tree or a cycle, respectively.Minimum detour index of cactus graphs.https://zbmath.org/1449.051522021-01-08T12:24:00+00:00"Fang, Wei"https://zbmath.org/authors/?q=ai:fang.wei"Yu, Hongjie"https://zbmath.org/authors/?q=ai:yu.hongjie.1"Gao, Yubin"https://zbmath.org/authors/?q=ai:gao.yubin"Jing, Guangming"https://zbmath.org/authors/?q=ai:jing.guangming"Li, Zhongshan"https://zbmath.org/authors/?q=ai:li.zhongshan"Li, Xiaoxin"https://zbmath.org/authors/?q=ai:li.xiaoxinSummary: The detour index of a connected graph is defined as the sum of the detour distances (lengths of longest paths) between unordered pairs of vertices of the graph. A cactus is a connected graph in which no edge lies in more than one cycle. In this paper, we characterize the first two smallest detour indices among all cactus graphs and which attain the bounds.The Laplacian spectra and Laplacian energies of hexagonal cyclic chains.https://zbmath.org/1449.051692021-01-08T12:24:00+00:00"Lou, Zhenzhen"https://zbmath.org/authors/?q=ai:lou.zhenzhen"Huang, Qiongxiang"https://zbmath.org/authors/?q=ai:huang.qiongxiang"Ma, Xiaoling"https://zbmath.org/authors/?q=ai:ma.xiaolingSummary: Let \(L_n\), \(F_n\) and \(M_n\) be tree-type hexagonal chains, respectively. Those are linear chains, cyclic chains, Möbius cyclic chains. \textit{I. Gutman} [Match 8, 291--314 (1980; Zbl 0454.05044)], \textit{G. Derflinger} and \textit{H. Sofer} [``Die HMO-Koeffizienten der linearen Polyacene in geschlossener Form'', Monatsh. Chemie 99, 1866--1875 (1968)] give the adjacency spectra of \(L_n\) and \(F_n\) with different methods, respectively. In this paper, we determine the Laplacian spectra of \(F_n\) and \(M_n\), from which we get the explicit value of Laplacian energies of \(F_n\) and \(M_n\), respectively. Additionally, we obtain the integral expressions of their Laplacian energies, which are approximately to six times \(n\).Malware clustering based on graph convolutional networks.https://zbmath.org/1449.621382021-01-08T12:24:00+00:00"Liu, Kai"https://zbmath.org/authors/?q=ai:liu.kai.2|liu.kai.5|liu.kai.4|liu.kai|liu.kai.1|liu.kai.3"Fang, Yong"https://zbmath.org/authors/?q=ai:fang.yong"Zhang, Lei"https://zbmath.org/authors/?q=ai:zhang.lei.5|zhang.lei.22|zhang.lei.18|zhang.lei.4|zhang.lei.13|zhang.lei|zhang.lei.9|zhang.lei.2|zhang.lei.25|zhang.lei.10|zhang.lei.21|zhang.lei.24|zhang.lei.23|zhang.lei.17|zhang.lei.16|zhang.lei.15|zhang.lei.7|zhang.lei.20|zhang.lei.1|zhang.lei.6|zhang.lei.3|zhang.lei.12|zhang.lei.8|zhang.lei.19|zhang.lei.14|zhang.lei.11"Zuo, Zheng"https://zbmath.org/authors/?q=ai:zuo.zheng"Liu, Liang"https://zbmath.org/authors/?q=ai:liu.liangSummary: Many new types of malwares are often modified by attackers based on the existing malwares. Therefore, family homology analysis of malwares can help to study the evolutionary trend and traceability of malwares. In this paper, starting from API call graphs of malwares and combined with Graph Convolutional Networks (GCN), we proposed a similarity calculation and family clustering model for malwares. Firstly, we extract API call graphs of malwares with disassembly tools and the label the attributions of API functions in the graphs. Then, we select key API functions by their contributions to the malware families and construct the API call graphs of malwares. We use GCN and Convolutional Neural Networks (CNN) as the models of the malware similarity calculation in which the inputs are the API call graphs. Finally, we use DBSCAN algorithm to cluster malwares. The experimental results show that the proposed method can achieve 87.3\%accuracy and can effectively cluster malware families.Color-connected graphs and information-transfer paths.https://zbmath.org/1449.050882021-01-08T12:24:00+00:00"Chartrand, Gary"https://zbmath.org/authors/?q=ai:chartrand.gary"Devereaux, Stephen"https://zbmath.org/authors/?q=ai:devereaux.stephen"Zhang, Ping"https://zbmath.org/authors/?q=ai:zhang.ping.6|zhang.ping.1Summary: Let \(G\) be an edge-colored nontrivial connected graph, where adjacent edges may be colored the same. A path \(P\) in \(G\) is a rainbow path if no two edges of \(P\) are colored the same. For an integer \(k\geq 2\), a path \(P\) in \(G\) is a \(k\)-rainbow path if every subpath of \(P\) having length \(\ell\) for each \(\ell\) with \(\ell\leq k\) is a rainbow path. An edge coloring of \(G\) is a \(k\)-rainbow coloring if every pair of distinct vertices of \(G\) are connected by a \(k\)-rainbow path in \(G\). The minimum number of colors for which \(G\) has a \(k\)-rainbow coloring is called the \(k\)-rainbow connection number \(\text{rc}_k(G)\) of \(G\). In this paper, we investigate the \(3\)-rainbow colorings in graphs and the relationship between the \(3\)-rainbow connection numbers and the well-studied rainbow or proper connection numbers of graphs. The values of \(\text{rc}_3(G)\) are determined for several well-known classes of graphs \(G\).The characteristic polynomials of three classes of sign transform graphs.https://zbmath.org/1449.051462021-01-08T12:24:00+00:00"Zhang, Ya'nan"https://zbmath.org/authors/?q=ai:zhang.yanan"Chen, Haiyan"https://zbmath.org/authors/?q=ai:chen.haiyanSummary: Let \(G = (V (G), E (G))\) be a simple graph of order \(n\) and size \(m\), and let \(\sigma: E (G) \to \{+1, -1\}\) be a mapping defined on the edges of \(G\). We call \(\Gamma = (G, \sigma)\) a signed graph of \(G\). Given a signed graph \(\Gamma\), some previous researchers defined the signed line graph \(\mathcal{L} (\Gamma)\) as well as the signed subdivision graph \(S (\Gamma)\) and obtained relations between their adjacency characteristic polynomials and Laplacian characteristic polynomials of \(\Gamma\). In this paper, we define other three classes of signed transformation graphs, named signed middle graph, signed triangular extension graph and signed total graph respectively, denoted by \(Q (\Gamma)\), \(R (\Gamma)\), \(T (\Gamma)\) respectively. When \(G\) is regular, we give the relation between the adjacency characteristic polynomials and Laplacian characteristic polynomials of the three classes of signed transformation graphs and the corresponding polynomials of the original signed graph \(\Gamma\). These results generalize the counterpart of unsigned graphs.Connected graphs with maximal Roman domination number one less than their order.https://zbmath.org/1449.051962021-01-08T12:24:00+00:00"Abdollahzadeh Ahangar, H."https://zbmath.org/authors/?q=ai:ahangar.hossein-abdollahzadeh"Chellali, Mustapha"https://zbmath.org/authors/?q=ai:chellali.mustapha.1"Kuziak, Dorota"https://zbmath.org/authors/?q=ai:kuziak.dorota"Samodivkin, Vladimir"https://zbmath.org/authors/?q=ai:samodivkin.vladimir-dSummary: A Roman dominating function on a graph \(G\) is a labeling \(f:V(G)\to\{0,1,2\}\) such that every vertex with label \(0\) has a neighbor with label \(2\). A maximal Roman dominating function on a graph \(G\) is a Roman dominating function \(f\) such that \(V_0=\{w\in V(G)\mid f(w)=0\}\) is not a dominating set of \(G\). The weight of a maximal Roman dominating function is the value \(w(f)=f(V(G))=\sum_{x\in V(G)}f(x)\). The maximal Roman domination number \(\gamma_{mR}(G)\) of a graph \(G\) equals the minimum weight of a maximal Roman dominating function on \(G\). In this paper we provide a characterization of connected graphs \(G\) of order \(n\) such that \(\gamma_{mR}(G)=n-1\) among some specific classes of graphs.Some vertex-degree-based topological indices of cacti.https://zbmath.org/1449.050532021-01-08T12:24:00+00:00"Ali, Akbar"https://zbmath.org/authors/?q=ai:ali.akbar"Raza, Zahid"https://zbmath.org/authors/?q=ai:raza.zahid"Bhatti, Akhlaq Ahmad"https://zbmath.org/authors/?q=ai:bhatti.akhlaq-ahmadSummary: The present study is devoted to characterize the cactus with minimum \(T_1\) index and maximum \(T_2\) index over the class of all cacti having fixed number of vertices and cycles, where \(T_1\) index is the first multiplicative Zagreb index, Narumi-Katayama index, modified second Zagreb index, or harmonic index, and \(T_2\) index is the second multiplicative Zagreb index or modified first multiplicative Zagreb index.A discharging method to find subgraphs having two edge-disjoint spanning trees.https://zbmath.org/1449.051582021-01-08T12:24:00+00:00"Wang, Keke"https://zbmath.org/authors/?q=ai:wang.keke"Zhan, Mingquan"https://zbmath.org/authors/?q=ai:zhan.mingquan"Lai, Hong-Jian"https://zbmath.org/authors/?q=ai:lai.hong-jianSummary: We introduce the discharging method in the study of subgraphs with two edge-disjoint spanning trees. As an application, we present a short proof for the theorem that every 3-connected, essentially 10-connected line graph is Hamiltonian connected.Vertex-distinguishing I-total colorings and vertex-distinguishing VI-total colorings of \(m{C_4}\).https://zbmath.org/1449.051152021-01-08T12:24:00+00:00"Yang, Han"https://zbmath.org/authors/?q=ai:yang.han"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangenSummary: The problem of the vertex distinguishing I-total colorings (VDITC) and vertex distinguishing VI-total colorings (VDVITC) of the disjoint union \(m{C_4}\) of \(m\) cycles of order 4 are discussed in this paper. By using the methods of constructing a matrix which is composed of color sets and empty set as the elements, distributing color sets in advance and coloring explicitly, we give the optimal vertex-distinguishing I-total colorings and the optimal vertex-distinguishing VI-total colorings of \(m{C_4}\). Thus vertex-distinguishing I-total chromatic numbers and the vertex-distinguishing VI-total chromatic numbers of \(m{C_4}\) are determined. Results in this paper show that the VDITC conjecture and VDVITC conjecture are valid for \(m{C_4}\).Comparisons between multiplicative Zagreb eccentricity indices and a new eccentric connectivity index.https://zbmath.org/1449.050682021-01-08T12:24:00+00:00"Wang, Hong-Yong"https://zbmath.org/authors/?q=ai:wang.hongyong"Yang, Deniu"https://zbmath.org/authors/?q=ai:yang.deniu"Jiang, Qin"https://zbmath.org/authors/?q=ai:jiang.qinSummary: Let \(G=(V,E)\) be a connected simple graph with \(|V|=n\) and \(|E|=m\). The first and the second multiplicative Zagreb eccentricity index are defined as \(\mathbb{Z}_1(G)=\prod_{u\in V(G)}e_u^2\) and \(\mathbb{Z}_2(G)=\prod_{uv\in E(G)}e_ue_v\) respectively, where \(e_u\) is the eccentricity of a vertex \(u\) of \(G\). The multiplicative eccentric connectivity index is defined by \(\mathbb{Z}_3(G)=\prod_{uv\in E(G)}(e_u+e_v)\). In this paper, the comparisions between these indices are investigated in detail. As a result, an inequality for the index \(\mathbb{Z}_3(G)\), which is similar to the Zagreb indices inequality, is proved.Vertex-to-clique monophonic distance in graphs.https://zbmath.org/1449.050832021-01-08T12:24:00+00:00"Keerthi Asir, I."https://zbmath.org/authors/?q=ai:asir.i-keerthi"Athisayanathan, S."https://zbmath.org/authors/?q=ai:athisayanathan.sSummary: Let \(C\) be a clique and \(u\) a vertex in a connected graph \(G\). A vertex-to-clique \(u-C\) path \(P\) is a \(u-v\) path, where \(v\) is a vertex in \(C\) such that \(P\) contains no vertices of \(C\) other than \(v\) and the \(u-C\) path \(P\) is said to be \(u-C\) monophonic path if \(P\) contains no chords in \(G\). The vertex-to-clique monophonic distance \(d_m(u,C)\) is the length of a longest \(u-C\) monophonic path in \(G\). A \(u-C\) monophonic path of length \(d_m(u,C)\) is called a vertex-to-clique \(u-C\) monophonic. The vertex-to-clique monophonic eccentricity \(e_{m_1}(u)\) of a vertex \(u\) in \(G\) is the maximum vertex-to-clique monophonic distance from \(u\) to a clique \(C\in\zeta\) in \(G\), where \(\zeta\) is the set of all cliques in \(G\). The vertex-to-clique monophonic radius \(R_{m_1}\) of \(G\) is the minimum vertex-to-clique monophonic eccentricity among the vertices of \(G\), while the vertex-to-clique monophonic diameter \(D_{m_1}\) of \(G\) is the maximum vertex-to-clique monophonic eccentricity among the vertices of \(G\). It is shown that \(R_{m_1}\leq D_{m_1}\) for every connected graph \(G\) and that every two positive integers \(a\) and \(b\) with \(2\leq a\leq b\) are realizable as the vertex-to-clique monophonic radius and the vertex-to-clique monophonic diameter, respectively, of some connected graph. The vertex-to-clique monophonic center \(C_{m_1}(G)\) is the subgraph induced by the set of all vertices having minimum vertex-to-clique monophonic eccentricity and the vertex-to-clique monophonic periphery \(P_{m_1}(G)\) is the subgraph induced by the set of all vertices having maximum vertex-to-clique monophonic eccentricity. It is shown that the vertex-to-clique monophonic center of every connected graph \(G\) lies in a single block of \(G\).Unicyclic graphs with the first seven smallest Laplacian permanent.https://zbmath.org/1449.052072021-01-08T12:24:00+00:00"Zhu, Zhongxun"https://zbmath.org/authors/?q=ai:zhu.zhongxunSummary: Let \(L(G)\) be the Laplacian matrix of \(G\) of order \(n\), the permanent \(\operatorname{per}(L(G))\) of \(L(G)\) is defined as \(\operatorname{per}(L(G))=\sum_{\sigma}\prod_{i=1}^nl_{i,\sigma(i)}\), where the sum goes over every permutation \(\sigma\) of the set \(\{1,2,\dots,n\}\). Since if \(G\) is bipartite, each summand of \(\operatorname{per}(L(G))\) is non-negative, but for non-bipartite, its sign of summands become rather complicated, so the researches are mainly focus on bipartite. In this paper, we begin studying non-bipartite, the first seven smallest Laplacian permanents on unicyclic graphs are determined and the corresponding extremal graphs are characterized.Some notes on product cordial graphs.https://zbmath.org/1449.052272021-01-08T12:24:00+00:00"Seoud, M. A."https://zbmath.org/authors/?q=ai:seoud.mohamed-abdel-azim"Jaber, Huda"https://zbmath.org/authors/?q=ai:jaber.hudaSummary: In this paper we give some properties of maximal product cordial graphs. We give some necessary conditions for planar graphs to be product cordial, and we determine all product cordial planar graphs of order at most 7.Long cycles in \(n\)-extendable bipartite graphs.https://zbmath.org/1449.051532021-01-08T12:24:00+00:00"Gan, Zhiyong"https://zbmath.org/authors/?q=ai:gan.zhiyong"Lou, Dingjun"https://zbmath.org/authors/?q=ai:lou.dingjunSummary: A graph \(G\) is said to be \(n\)-extendable if it has a matching of size \(n\), and every matching of size \(n\) extends to a perfect matching of \(G\). In this paper, we prove that an \(n\)-extendable bipartite graph with \(\nu>6n\) has a longest cycle \(C\) such that \(|V(C)|\geq 6n\). The bound for \(|V(C)|\) is sharp. By a result of \textit{Y. Li} and \textit{D. Lou} [Ars Comb. 139, 3--18 (2018; Zbl 06940829)], we prove that if \(G\) is \(n\)-extendable and bipartite, then \(G\) has a cycle \(C\) of length \(|V(C)|\geq\min\{\nu,6n\}\).Edge fault tolerance of regular graphs on super 3-restricted edge connectivity.https://zbmath.org/1449.051602021-01-08T12:24:00+00:00"Wang, Shiying"https://zbmath.org/authors/?q=ai:wang.shiying"Zhang, Guozhen"https://zbmath.org/authors/?q=ai:zhang.guozhenSummary: Let \(G=(V,E)\) be a connected graph. An edge set \(S\subseteq E\) is a 3-restricted edge cut if \(G-S\) is disconnected and every component of \(G-S\) has at least three vertices. The 3-restricted edge connectivity of \(G\), denoted by \(\lambda_3(G)\), is defined to be the cardinality of a minimum 3-restricted edge cut. \(G\) is super-\(\lambda_3\) if every minimum 3-restricted edge cut of \(G\) isolates one connected subgraph of order three. We define a super-\(\lambda_3\) graph \(G\) to be \(m\)-super-\(\lambda_3\) if \(G-S\) is still super-\(\lambda_3\) for any edge set \(S\subseteq E\) with \(|S|\leq m\). The maximum integer of such \(m\), denoted by \(S_{\lambda_3}(G)\), is said to he the edge fault tolerance of \(G\) on the super-\(\lambda_3\) property. \(S_{\lambda_3}(G)\) is an index to measure the reliability of networks. In this paper, we give the lower and upper bounds on \(S_{\lambda_3}(G)\) for regular graphs and determine the exact value of \(S_{\lambda_3}(G)\) for a special class of regular graphs. More refined bounds on \(S_{\lambda_3}(G)\) are obtained for Cartesian product of regular graphs and an example shows that the obtained bounds are best possible.A note on tetravalent \(s\)-arc-regular Cayley graphs of finite simple groups.https://zbmath.org/1449.200012021-01-08T12:24:00+00:00"Ling, Bo"https://zbmath.org/authors/?q=ai:ling.boSummary: A Cayley graph \(\Gamma=\mathrm{Cay}(G,S)\) is said to be normal if \(G\) is normal in \(\Aut\Gamma\), otherwise, \(\Gamma\) is called non-normal. By earlier work of \textit{J. J. Li} et al. [J. Algebra Appl. 16, No. 10, Article ID 1750195, 17 p. (2017; Zbl 1404.20001)], the only possibilities for non-normal connected tetravalent \(s\)-arc-regular Cayley graphs of finite simple groups must arise from one of two graphs of the alternating group \(A_{35}\). In this paper, we prove that the full automorphism groups of these two graphs are isomorphic to \(A_{36}\) and show that these two graphs are not isomorphic, and so this paper completes the classification of nonnormal connected tetravalent \(s\)-arc-regular Cayley graphs of finite simple groups.A family of multimagic squares based on large sets of orthogonal arrays.https://zbmath.org/1449.050362021-01-08T12:24:00+00:00"Zhang, Yong"https://zbmath.org/authors/?q=ai:zhang.yong.11|zhang.yong.12|zhang.yong.2|zhang.yong.1|zhang.yong.4|zhang.yong.13|zhang.yong|zhang.yong.9|zhang.yong.5|zhang.yong.8|zhang.yong.7|zhang.yong.10|zhang.yong.14"Chen, Kejun"https://zbmath.org/authors/?q=ai:chen.kejun|chen.kejun.1"Li, Wen"https://zbmath.org/authors/?q=ai:li.wen.2|li.wen|li.wen.1Summary: Large set of orthogonal arrays (LOA) were introduced by \textit{D. R. Stinson} [``Resilient functions and large sets of orthogonal arrays'', Congr. Numer. 92, 105--110 (1993)], and it is also used to construct multimagic squares recently. In this paper, multimagic squares based on strong double LOA are further investigated. It is proved that there exists an MS\((q^{2t-1},t)\) for any prime power \(q\geq 2t-1\) with \(t\geq 3\), which provided a new family of multimagic squares.Some topological indices of a graph operation and applications.https://zbmath.org/1449.050602021-01-08T12:24:00+00:00"Liu, Jia-Bao"https://zbmath.org/authors/?q=ai:liu.jia-bao"Wang, Weizhong"https://zbmath.org/authors/?q=ai:wang.weizhongSummary: Let \(\mu_1,\mu_2,\dots,\mu_n\) and \(q_1,q_2,\dots,q_n\) denote the eigenvalues of the Laplacian matrix \(L(G)\) and the signless Laplacian matrix \(Q(G)\), respectively. The Kirchhoff index, defined as \(Kf(G)=n\sum_{i=1}^{n-1}\frac{1}{\mu_i}\), and the Laplacian-energy-like invariant, defined as \(LEL(G)=\sum_{i=1}^{n-1}\sqrt{\mu_i}\) are two well studied quantities with applications in chemical physics. Analogously, the incidence energy \(IE(G)\) of a graph \(G\) is defined as \(IE(G)\sum_{i=1}^{n-1}\sqrt{q_i}\). The graph \(G^\ast\), constructed from \(G\), is the line graph of the subdivision graph \(S(G)\). In this paper, we deduce the closed-form formulae for calculating the \(Kf(G^\ast)\), \(LEL(G^\ast)\) and \(IE(G^\ast)\), respectively.The 2-dimension of a tree.https://zbmath.org/1449.050482021-01-08T12:24:00+00:00"Hedetniemi, Jason T."https://zbmath.org/authors/?q=ai:hedetniemi.jason-t"Hedetniemi, Stephen T."https://zbmath.org/authors/?q=ai:hedetniemi.stephen-t"Laskar, Renu C."https://zbmath.org/authors/?q=ai:laskar.renu-c"Mulder, Henry Martyn"https://zbmath.org/authors/?q=ai:mulder.henry-martynSummary: Let \(x\) and \(y\) be two distinct vertices in a connected graph \(G\). The \(x,y\)-location of a vertex \(w\) is the ordered pair of distances from \(w\) to \(x\) and \(y\), that is, the ordered pair \((d(x,w), d(y,w))\). A set of vertices \(W\) in \(G\) is \(x,y\)-located if any two vertices in \(W\) have distinct \(x,y\)-location. A set \(W\) of vertices in \(G\) is 2-located if it is \(x,y\)-located, for some distinct vertices \(x\) and \(y\). The 2-dimension of \(G\) is the order of a largest set that is 2-located in \(G\). Note that this notion is related to the metric dimension of a graph, but not identical to it. We study in depth the trees \(T\) that have a 2-locating set, that is, have 2-dimension equal to the order of \(T\). Using these results, we have a nice characterization of the 2-dimension of arbitrary trees.The difference between the eccentric distance sum and eccentric connectivity index.https://zbmath.org/1449.051502021-01-08T12:24:00+00:00"Hua, Hongbo"https://zbmath.org/authors/?q=ai:hua.hongbo"Wang, Hongzhuan"https://zbmath.org/authors/?q=ai:wang.hongzhuan"Wang, Maolin"https://zbmath.org/authors/?q=ai:wang.maolinSummary: The eccentric distance sum and eccentric connectivity index are two distance-based topological indices associated with a (molecular) graph. More recently, \textit{H. Zhang} et al. [Discrete Appl. Math. 254, 204--221 (2019; Zbl 1404.05093)] characterized the graph attaining the minimum value of the difference between the eccentric distance sum and eccentric connectivity index among all connected graphs of diameter two and given independence number. In this note, we generalize Zhang and Li's this result by characterizing the graph attaining the minimum value of the difference between the eccentric distance sum and eccentric connectivity index among all connected graphs of given independence number. Moreover, we characterize the graph attaining the minimum value of the difference between the eccentric distance sum and eccentric connectivity index among all connected graphs of given matching number.Online social networks under hypergraph structure and their hidden influence evaluation.https://zbmath.org/1449.910822021-01-08T12:24:00+00:00"Li, Quanlin"https://zbmath.org/authors/?q=ai:li.quanlin"Li, Chaoran"https://zbmath.org/authors/?q=ai:li.chaoran"Ma, Jingyu"https://zbmath.org/authors/?q=ai:ma.jingyuSummary: This paper sets up a reasonable synthesis among hypergraph structure, probability behavior and information theory, and applies them to the study of online social networks. This motivates us to provide a new mathematical method for analyzing online social networks and their hidden influence. Therefore, this paper first applies hypergraph theory to set up the information transmission process by means of a hyperpath between any two users, and describes quantitative relation and fluctuation strength through combining hypergraph structure with probabilistic behavior. Then the average mutual information is established to provide a new mathematical evaluation method of hidden influence. Numerical examples verify the effectiveness of the evaluation method of hidden influence.Cyclic permutations and crossing numbers of join products of symmetric graph of order six.https://zbmath.org/1449.050722021-01-08T12:24:00+00:00"Berežný, Štefan"https://zbmath.org/authors/?q=ai:berezny.stefan"Staš, Michal"https://zbmath.org/authors/?q=ai:stas.michalSummary: In the paper, we extend known results concerning crossing numbers for join of graphs of order six. We give the crossing number of the join product \(G+D_n\), where the graph \(G\) consists of two leaves incident with two opposite vertices of one 4-cycle, and \(D_n\) consists on \(n\) isolated vertices. The proof is done with the help of software that generates all cyclic permutations for a given number \(k\), and creates a new graph COG for a calculating the distances between all \((k-1)\)! vertices of the graph. Finally, by adding new edges to the graph \(G\), we are able to obtain the crossing number of the join product with the discrete graph \(D_n\) for two other graphs. The methods used in the paper are new, and they are based on combinatorial properties of cyclic permutations.A note on sums of a class of series.https://zbmath.org/1449.330062021-01-08T12:24:00+00:00"Jun, Sungtae"https://zbmath.org/authors/?q=ai:jun.sungtae"Milovanović, Gradimir V."https://zbmath.org/authors/?q=ai:milovanovic.gradimir-v"Kim, Insuk"https://zbmath.org/authors/?q=ai:kim.insuk"Rathie, Arjun K."https://zbmath.org/authors/?q=ai:rathie.arjun-kumarSummary: The aim of this note is to provide sums of a unified class of series of the form \[S_i(a)=\sum_{k=0}^{\infty} (-1)^{k} \binom{a-i}{k} \frac{1}{2^{k}(a+k+1)}\] in the most general form for any \(i\in\mathbb{Z}\). For each \(\nu\in\mathbb{N}\), in four cases when \(i=\pm 2\nu\) and \(i=\pm(2\nu-1)\), simple explicit expressions for \(S_i(a)\) are obtained, e.g. \[S_{2\nu}(a)=\frac{2^{2\nu-1-a}}{(a-2\nu+1)_\nu}\left[\frac{\sqrt{\pi}\, \Gamma (a+1)}{\Gamma \left(a+\frac{3}{2}-\nu\right)}-P_{\nu-1}(a)\right],\] where \(P_\nu(a)\) is an algebraic polynomial in \(a\) of degree \(\nu\).
For \(i=1\) and \(a=n\) \((\in \mathbb{N})\), we recover the well known sum of the series due to \textit{M. Vowe} and \textit{H.-J. Seiffert} [Elem. Math. 42, No. 4, 111--112 (1987; Zbl 1253.33007)]. Several other known results due to \textit{H. M. Srivastava} [Proc. Japan Acad., Ser. A 65, No. 1, 8--11 (1989; Zbl 0653.33004)] and \textit{Y. S. Kim} et al. [Commun. Korean Math. Soc. 27, No. 4, 745--751 (2012; Zbl 1253.33004)] can be considered as special cases of our result.2-signed total domination number of two classes of graphs.https://zbmath.org/1449.051982021-01-08T12:24:00+00:00"Chen, Wei"https://zbmath.org/authors/?q=ai:chen.wei.2|chen.wei.3|chen.wei.1|chen.wei.4|chen.wei"Hong, Xia"https://zbmath.org/authors/?q=ai:hong.xiaSummary: Let \(G = (V, E)\) be a graph and \(\delta (G) \ge 1\). A function \(f: V \mapsto \{-2, -1, 1, 2\}\) is said to be a 2-signed total domination function if \(f (N (v)) \ge 1\) for \(v \in V\). In this paper, the exact values of the 2-signed total domination number of path \({P_m}\) and cycle \({C_m}\) are determined by exhaustive method and classified discussion.Operations on \(m\)-polar fuzzy \(r\)-uniform hypergraphs.https://zbmath.org/1449.051912021-01-08T12:24:00+00:00"Akram, Muhammad"https://zbmath.org/authors/?q=ai:akram.muhammad"Shahzadi, Gulfam"https://zbmath.org/authors/?q=ai:shahzadi.gulfam"Shum, K. P."https://zbmath.org/authors/?q=ai:shum.kar-pingSummary: In this paper, we present certain operations, including Cartesian, composition, union, join products of \(m\)-polar fuzzy hypergraphs. Moreover, we discuss lexicographic, strong and tensor products of \(m\)-polar fuzzy \(r\)-uniform hypergraphs. Finally, we describe a real world problem of selecting a pair of good player team for competition with other country using union operation of \(m\)-polar fuzzy hypergraphs.Converting the sum of weighted degrees of natural numbers with the same parameters.https://zbmath.org/1449.050102021-01-08T12:24:00+00:00"Nikonov, Aleksandr Ivanovich"https://zbmath.org/authors/?q=ai:nikonov.aleksandr-ivanovichSummary: Consider the transformation of a finite sum of weighted equal powers of natural numbers to a form that uses the binomial coefficients. This conversion enables the sequential reduction of enumerated values that belong to the intermediate and final operations of this reduction.Bounds on the structural indices of primitive non-powerful generalized sign pattern matrices.https://zbmath.org/1449.150782021-01-08T12:24:00+00:00"Huang, Yufei"https://zbmath.org/authors/?q=ai:huang.yufeiSummary: In view of the special effects of ``loop'' in the study of structural index problems, two classes of special generalized signed digraphs are defined: primitive non-powerful generalized signed digraphs with intersecting cycles structure and that with distinguished intersecting cycles structure, respectively. With restriction on primitive nonpowerful generalized signed digraphs with intersecting cycles structure and those with distinguished intersecting cycles structure, upper bounds on the structural indices, e.g. \(k\)th local \(\tau\)-base, \(k\)th same \(\tau\)-base, \(k\)th lower \(\tau\)-base, \(k\)th upper \(\tau\)-base and \(\omega\)-indecomposable base, are discussed by imitating the digraphs, analyzing the ambiguous reachable set and using the properties of Frobenius numbers, respectively.Automorphism groups of some graphs for the ring of Gaussian integers modulo \({p^s}\).https://zbmath.org/1449.051412021-01-08T12:24:00+00:00"Zhang, Hengbin"https://zbmath.org/authors/?q=ai:zhang.hengbin"Nan, Jizhu"https://zbmath.org/authors/?q=ai:nan.ji-zhuSummary: In this paper, the automorphism group is completely determined. The unitary Cayley graph, the unit graph and the total graph are defined to be simple graphs over the ring of Gaussian integers modulo \({p^s}\).On relation between the Kirchhoff index and number of spanning trees of graph.https://zbmath.org/1449.050842021-01-08T12:24:00+00:00"Milovanović, Igor"https://zbmath.org/authors/?q=ai:milovanovic.igor-z"Glogić, Edin"https://zbmath.org/authors/?q=ai:glogic.edin"Matejić, Marjan"https://zbmath.org/authors/?q=ai:matejic.marjan-m"Milovanović, Emina"https://zbmath.org/authors/?q=ai:milovanovic.emina-iSummary: Let \(G\) be a simple connected graph with degree sequence \((d_1 , d_2 , \dots , d_n )\) where \(\Delta = d_1 \geq d_2 \geq\cdots\geq d_n = \delta> 0\) and let \(\mu_1 \geq \mu_2 \geq \cdots \geq \mu_{n-1} > \mu_n = 0\) be the Laplacian eigenvalues of \(G\). Let \(Kf(G) = n \sum^{n-1}_{i=1} \frac{1}{\mu_i}\) and \(\tau(G) = \frac{1}{n} \prod_{i=1}^{n-1} \mu_i\) denote the Kirchhoff index and the number of spanning trees of \(G\), respectively. In this paper, we establish several lower bounds for \(Kf (G)\) in terms of \(\tau(G)\), the order, the size and maximum degree of \(G\).Treewidth of grid subsets.https://zbmath.org/1449.050732021-01-08T12:24:00+00:00"Berger, Eli"https://zbmath.org/authors/?q=ai:berger.eli"Dvoržak, Zdeněk"https://zbmath.org/authors/?q=ai:dvorzak.zdenek"Norin, Sergey"https://zbmath.org/authors/?q=ai:norin.sergeyThe \(3\)-dimensional \( n \times n \times n \) grid \( Q_n \) considered in this paper is the `usual' \(3\)-dimensional grid with non-decreasing diagonals of its unit cubes added to its set of edges. Any \(2\)-coloring of the vertices of \( Q_n \) is known to contain a monochromatic subgraph with \( \Omega(n^2)\) vertices. This paper is concerned with the `\(2\)-dimensionality' of such subgraphs as represented by their tree-width. The authors prove that for any tree-width \( t \geq 0 \) there exists an \( n \geq 1 \) such that any partition of the vertices of \(Q_n\) into two sets has the property that at least one of the sets induces a subgraph of \( Q_n\) of tree-width at least \(t\). As a corollary, the class \( Q_n \), \( n \geq 1 \), is not tree-width fragile. Unlike the previously known classes which are not tree-width fragile, the class \( Q_n \), \( n \geq 1 \), has bounded maximum degree. It is also the first known class that is not tree-width fragile while being fractionally tree-width fragile. In addition, it is shown that any subset of vertices separating the vertices of \(Q_n\) into two subsets contains an induced subgraph of tree-width at least \( \frac{n}{\sqrt{18}}-1 \). The employed proof techniques include an interesting use of a discrete variant of homotopy theory.
Reviewer: Robert Jajcay (Terre Haute)Asymptotic metric behavior of random Cayley graphs of finite abelian groups.https://zbmath.org/1449.051362021-01-08T12:24:00+00:00"Shapira, Uri"https://zbmath.org/authors/?q=ai:shapira.uri"Zuck, Reut"https://zbmath.org/authors/?q=ai:zuck.reutSummary: Using methods of \textit{J. Marklof} and \textit{A. Strömbergsson} [ibid. 33, No. 4, 429--466 (2013; Zbl 1340.05063)] we establish several limit laws for metric parameters of random Cayley graphs of finite abelian groups with respect to a randomly chosen set of generators of a fixed size. Doing so we settle a conjecture of \textit{G. Amir} and \textit{O. Gurel-Gurevich} [Groups Complex. Cryptol. 2, No. 1, 59--65 (2010; Zbl 1194.05054)].The research on fuzzy ranks of fuzzy matroids.https://zbmath.org/1449.050452021-01-08T12:24:00+00:00"Wu, Deyin"https://zbmath.org/authors/?q=ai:wu.deyinSummary: With the help of the inspiration of regular fuzzy matroids, we define the regular fuzzy bases of general fuzzy matroids in this paper. Then, many properties about regular fuzzy bases are gained by the base-subset sets. For example, closed fuzzy matroids have regular fuzzy bases, the fuzzy cardinalities of regular fuzzy bases are equal in the same fuzzy matroid, the fuzzy cardinalities of regular fuzzy bases are maximal in fuzzy bases cardinality of the same fuzzy matroid, and so on. By these properties, we give a necessary and sufficient condition for closed fuzzy matroids to be regular fuzzy matroids, and find out the computational formula about the fuzzy cardinality of regular fuzzy bases. Lastly, we establish a notion which is called the fuzzy rank of fuzzy matroids (the fuzzy matroid rank for short), and prove the conclusion that the fuzzy matroid rank is equal to the fuzzy cardinality of regular fuzzy bases in its closure, and obtain the computational formula about the fuzzy rank of general fuzzy matroids by its closure. Meanwhile, we discuss also many properties about the fuzzy matroid rank in detail, and try to study fuzzy matroids by the fuzzy rank of fuzzy matroids. The fuzzy rank of fuzzy matroids is one of the characteristics of fuzzy matroids. There will be many works in studying fuzzy matroids by the fuzzy matroid rank or researching the fuzzy matroid rank by properties of fuzzy matroids.The 6-element case of \({S_1}\)-Frankl conjecture. I.https://zbmath.org/1449.050062021-01-08T12:24:00+00:00"Hu, Zechun"https://zbmath.org/authors/?q=ai:hu.ze-chun.1|hu.ze-chun"Li, Shilun"https://zbmath.org/authors/?q=ai:li.shilunSummary: The union-closed sets conjecture (Frankl's conjecture) says that for any finite union-closed family of finite sets, other than the family consisting only of the empty set, there exists an element that belongs to at least half of the sets in the family. Recently, two stronger versions of Frankl's conjecture (\({S_1}\)-Frankl conjecture and \({S_2}\)-Frankl conjecture for short) were introduced and partial proofs were given. In particular, it was proved that \({S_1}\)-Frankl conjecture holds if \(n \le 5\), where \(n\) is the number of all the elements in the family of sets. In this paper and its sister paper, we prove that it holds if \(n = 6\). This is the first part of the proof.On improper interval edge colourings.https://zbmath.org/1449.050972021-01-08T12:24:00+00:00"Hudák, Peter"https://zbmath.org/authors/?q=ai:hudak.peter"Kardoš, František"https://zbmath.org/authors/?q=ai:kardos.frantisek"Madaras, Tomáš"https://zbmath.org/authors/?q=ai:madaras.tomas"Vrbjarová, Michaela"https://zbmath.org/authors/?q=ai:vrbjarova.michaelaInterval edge colouring was introduced by \textit{A. S. Asratyan} and \textit{R. R. Kamalyan} [Prikl. Mat., Erevan 5, 25--34 (1987; Zbl 0742.05038)]. A proper colouring of the edges of a graph \(G\) with positive integers is an interval edge colouring if for each vertex \(v\) of \(G\), the colours used on edges incident with \(v\) form a consecutive interval.
In this paper, the authors study a variant of this notion (improper interval edge colouring) where the colouring is not required to be proper. They prove several upper and lower bounds to the maximum number of colours \(\hat{t}(G)\) used in an improper interval edge colouring of \(G\), determine this number for wheels and prisms, and prove some estimates for complete graphs. They also show that the difference between \(\hat{t}(G)\) and its analogue for standard interval edge colouring can be arbitrarily large.
Reviewer: Tomáš Kaiser (Plzeň)Constructing disjunction matrices with unitary space and analyzing the tighter bound.https://zbmath.org/1449.050382021-01-08T12:24:00+00:00"Zhang, Lihua"https://zbmath.org/authors/?q=ai:zhang.lihua"Niu, Meifang"https://zbmath.org/authors/?q=ai:niu.meifangSummary: Disjunction matrices mainly are used to test positive samples in sample space, which are also known as the problem samples, and every disjunction matrix is a \( (0,1)\) matrix. At present, many literatures make use of geometric spaces over a finite field to construct \({d^z}\)-disjunction matrices, in which there are more results in symplectic space. Some of these literatures make use of the inclusion relation between subspaces in geometric spaces over a finite field to construct \({d^z}\)-disjunction matrices, the test ratio (the ratio of the rows to columns of the \({d^z}\)-disjunction matrices) and the tighter bound of \(z\) are discussed. This paper uses the subspaces of the type of \( (m,s)\) in unitary space \(F_{q^2}^{(n)}\) to index the rows of the \({d^z}\)-disjunction matrices, the subspaces of the type of \( (r, s-1)\) in unitary space \(F_{q^2}^{(n)}\) to index the columns of the \({d^z}\)-disjunction matrices, using the inclusion relation between them to construct a new class of \({d^z}\)-disjunction matrices. By means of calculating the largest number of the subspaces of the type of \( (r, s-1)\) included in \(d\) subspaces of the type of \( (m-1, s-1)\), which is included in a given subspace of the type of \( (m, s)\), we give the value range of \(d\) and \(z\) and the tighter bound of \(z\). Since the gap between \(s-1\) in the subspaces of the type of \( (r, s-1)\) and \(s\) in the subspaces of the type of \( (m,s)\) is smaller, the value range of \(d\) and \(z\) and the tighter bound of \(z\) can be relatively quick obtained in this paper.Random graphic model generation algorithm based on Prüfer code.https://zbmath.org/1449.052322021-01-08T12:24:00+00:00"Li, Congcong"https://zbmath.org/authors/?q=ai:li.congcong"Liu, Jinglei"https://zbmath.org/authors/?q=ai:liu.jingleiSummary: Graph model reasoning is an important work in graph model research. A designed reasoning algorithm needs to be tested by a large number of experimental samples. In this paper, a random graph model is designed according to the structural characteristics and parameter characteristics of the graph model. The algorithm designed in this paper generates CP-nets of random structure according to the number and degree of vertices. The principle is getting DAG code by improving Prüfer code. Furthermore, the one-to-one mapping between DAG code and graph structure is established to realize the random generation of the graph model. Then, by combining the designed dominant query algorithm with the typical dominant query, it is proved that the graph model generated by the designed graph model generation algorithm has the randomness of corresponding characteristics. The time consumption of the dominant detection algorithm is heavily dependent on the randomness of topological structure of the graph and the number of parameters.Coloring properties of a class of oblique and diagonal symmetry tangles.https://zbmath.org/1449.570052021-01-08T12:24:00+00:00"Wang, Shuxin"https://zbmath.org/authors/?q=ai:wang.shuxin"Wang, Dongxue"https://zbmath.org/authors/?q=ai:wang.dongxue"Li, Siyu"https://zbmath.org/authors/?q=ai:li.siyu"Wang, Hetong"https://zbmath.org/authors/?q=ai:wang.hetongSummary: This paper discusses and gives the color matrices of a class of oblique and diagonal symmetry tangles by the coloring rules of tangles. On this basis, it gives the color matrices of mirror image of tangles, horizontal flip tangles and vertical flip tangles corresponding to the class of oblique and diagonal symmetry tangles.The inverse problem of Wiener index of graphs with given diameter.https://zbmath.org/1449.050702021-01-08T12:24:00+00:00"Wu, Xiaoying"https://zbmath.org/authors/?q=ai:wu.xiaoying"Chen, Yuanlong"https://zbmath.org/authors/?q=ai:chen.yuanlongSummary: The inverse Wiener index is important in biomedical field, especially in the synthetic drugs. In this paper, we investigate the Wiener index for connected graphs of given diameter, and characterize the graph with the smallest Wiener index \({r_1}\) among all graphs with \(n\) vertices and diameter \(d\). Then we construct a graph with its Wiener index no less than the integer \({r_1}\) among all graphs with \(n\) vertices and diameter \(d\).On the maximum signless Laplacian spectral radius of quasi-tree graph.https://zbmath.org/1449.050472021-01-08T12:24:00+00:00"Fan, Dandan"https://zbmath.org/authors/?q=ai:fan.dandan"Du, Jie"https://zbmath.org/authors/?q=ai:du.jie"Liu, Yang"https://zbmath.org/authors/?q=ai:liu.yang.2|liu.yang.18|liu.yang.5|liu.yang.21|liu.yang.23|liu.yang.15|liu.yang.20|liu.yang.7|liu.yang.1|liu.yang.12|liu.yang.17|liu.yang.13|liu.yang.16|liu.yang.14|liu.yang.4|liu.yang.6|liu.yang.10|liu.yang.8|liu.yang.22|liu.yang.11|liu.yang|liu.yang.3|liu.yang.9|liu.yang.19Summary: If there is a vertex such that the graph obtained after deleting the vertex is a tree, the graph is called a quasi-tree. Based on the concept of quasi-tree and by the corresponding branch transformation, in this paper, a graph with the maximum signless Laplacian spectral radius in all quasi-trees with a fixed degree of a vertex and a given number of suspension points is characterized.Capacity of permutations.https://zbmath.org/1449.050022021-01-08T12:24:00+00:00"Blecher, Aubrey"https://zbmath.org/authors/?q=ai:blecher.aubrey"Brennan, Charlotte"https://zbmath.org/authors/?q=ai:brennan.charlotte-alix"Knopfmacher, Arnold"https://zbmath.org/authors/?q=ai:knopfmacher.arnold"Shattuck, Mark"https://zbmath.org/authors/?q=ai:shattuck.mark-aSummary: Permutations of \([n] = \{1,2,\dots,n\}\) may be represented geometrically as bargraphs with column heights in \([n]\). We define the notion of capacity of a permutation to be the amount of water that the corresponding bargraph would hold if the region above it could retain water assuming the usual rules of fluid flow. Let \(C(n)\) be the sum of the capacities of all permutations of \([n]\). We obtain, in a unique manner, all permutations of length \(n+1\) from those of length \(n\), which yields a recursion for \(C(n + 1)\) in terms of \(C(n)\) that we can subsequently solve. Finally, we consider permutations that have a single dam (i.e., a single area of water containment) and compute the total number and capacity of all such permutations of a given length. We also provide bijective proofs of these formulas and an asymptotic estimate is found for the average capacity as \(n\) increases without bound.Some \(k\)-hop based graph metrics and node ranking in wireless sensor networks.https://zbmath.org/1449.680122021-01-08T12:24:00+00:00"Biró, Csaba"https://zbmath.org/authors/?q=ai:biro.csaba"Kusper, Gábor"https://zbmath.org/authors/?q=ai:kusper.gaborSummary: Node localization and ranking is an essential issue in wireless sensor networks (WSNs). We model WSNs by communication graphs. In our interpretation a communication graph can be directed, in case of heterogeneous sensor nodes, or undirected, in case of homogeneous sensor nodes, and must be strongly connected. There are many metrics to characterize networks, most of them are either global ones or local ones. The local ones consider only the immediate neighbors of the observed nodes. We are not aware of a metric which considers a subgraph, i.e., which is between global and local ones. So our main goal was to construct metrics that interpret the local properties of the nodes in a wider environment. For example, how dense the environment of the given node, or in which extent it can be relieved within its environment. In this article we introduce several novel \(k\)-hop based density and redundancy metrics: Weighted Communication Graph Density (\(\mathcal{WCGD}\)), Relative Communication Graph Density (\(\mathcal{RCGD}\)), Weighted Relative Communication Graph Density (\(\mathcal{WRCGD}\)), Communication Graph Redundancy (\(\mathcal{CGR}\)), Weighted Communication Graph Redundancy (\(\mathcal{WCGR}\)). We compare them to known graph metrics, and show that they can be used for node ranking.Novel decision-making approach based on hesitant fuzzy sets and graph theory.https://zbmath.org/1449.910392021-01-08T12:24:00+00:00"Naz, Sumera"https://zbmath.org/authors/?q=ai:naz.sumera"Akram, Muhammad"https://zbmath.org/authors/?q=ai:akram.muhammadSummary: Hesitant fuzzy set is a powerful and effective tool to express uncertain information in multi-attribute decision-making (MADM) process, as it permits the membership degree of an element to a set represented by several possible values in \([0,1]\). In this paper, we develop a new decision-making approach based on graph theory to deal with the MADM problems, in which the decision information is expressed by hesitant fuzzy elements. Meanwhile, we generalize this approach to make it suitable for processing interval-valued hesitant fuzzy and hesitant triangular fuzzy information. Moreover, we utilize the numerical examples concerning the energy project selection and software evaluation to show the detailed implementation procedure and reliability of our method in solving MADM problems under hesitant fuzzy, interval-valued hesitant fuzzy and hesitant triangular fuzzy environment.Extremal graphs on the bicyclic graphs with prescribed degree sequence.https://zbmath.org/1449.050712021-01-08T12:24:00+00:00"Yang, Yang"https://zbmath.org/authors/?q=ai:yang.yang.2|yang.yang|yang.yang.3|yang.yang.5|yang.yang.1|yang.yang.4"Shao, Yanling"https://zbmath.org/authors/?q=ai:shao.yanlingSummary: Let \(G\) be a simple connected graph, and \({R_f} (G)\) denotes a molecular topological index defined by the degrees of adjacent vertices of \(G\). In order to obtain the maximum or minimum \({R_f} (G)\) for a given degree sequence of bicyclic graphs, the extremal graphs on the bicyclic graphs were obtained using proof by contradiction. An algorithm was given to construct the extremal graph, then a conclusion was drawn.Note on finitary Hindman numbers.https://zbmath.org/1449.052382021-01-08T12:24:00+00:00"Mohsenipour, Shahram"https://zbmath.org/authors/?q=ai:mohsenipour.shahram"Shelah, Saharon"https://zbmath.org/authors/?q=ai:shelah.saharonFrom the introduction: ``Inspired by Paris-Harrington's strengthening of the finite Ramsey theorem, Spencer defined in a similar way the following numbers (which we denote by \((\mathrm{Sp}m,c)\)), strengthening the Folkman-Sanders theorem: Let \((\mathrm{Sp}m,c)\) be the last integer \(k\) such that whenever \([k]=\{1,\ldots, k\}\) is \(c\)-colored then there is \(H=\{a_0,\ldots, a_{l-1}\}\subset [k]\) such that \(\sum H\) (sums of elements of \(H\) with no repetition) is monochromatic and \(m\leq \min H\leq l\). Spencer asked if \((\mathrm{Sp}m,c)\) is primitive recursive. In this paper we give a positive answer to this question. In fact we define the more general numbers \((\mathrm{Sp}m,p,c)\) and show that it is in class \(\mathcal{E}_{5}\) of the Grzegorczyk hierarchy of primitive recursive functions.''
Reviewer: Ioan Tomescu (Bucureşti)SIS epidemic propagation on hypergraphs.https://zbmath.org/1449.051932021-01-08T12:24:00+00:00"Bodó, Ágnes"https://zbmath.org/authors/?q=ai:bodo.agnesSummary: Mathematical modeling of epidemic propagation on hypergraphs is considered in this paper. The goal is to model the community structure with greater accuracy and to describe the dependence of the infection pressure on the number of infected neighbours with a nonlinear function. The master equation describing the process is derived for an arbitrary hypergraph. The mean-field equations are introduced as an approximation to the master equation and are compared against the stochastic simulations. Simulation results can be used to analyze the effects of the hypergraph structure and the model parameters.A Turán theorem for extensions via an Erdős-Ko-Rado theorem for Lagrangians.https://zbmath.org/1449.051512021-01-08T12:24:00+00:00"Watts, Adam Bene"https://zbmath.org/authors/?q=ai:watts.adam-bene"Norin, Sergey"https://zbmath.org/authors/?q=ai:norin.sergey"Yepremyan, Liana"https://zbmath.org/authors/?q=ai:yepremyan.lianaAn \(r\)-graph is an abbreviation for an \(r\)-uniform hypergraph. Let \(V(G)\), \(v(G)\), and \(e(G)\) denote the vertex set, the number of vertices, and the number of edges of an \(r\)-graph \(G\). Let \(\mathrm{Forb}((F)\) denote the class of all \(F\)-free \(r\)-graphs, i.e., \(r\)-graphs not containing \(F\) as subgraph. The Turán function \(\mathrm{ex}(n,F)\) is defined as \(\mathrm{ex}(n,F)= \max \{\mathrm{e}(G) : \mathrm{v}(G)=n, G \in \mathrm{Forb}(F)\}\). The extension of an \(r\)-graph \(F\), denoted by Ext\((F)\), is an \(r\)-graph obtained from \(F\) by adding a new edge for every uncovered pair of vertices containing this pair and \(r-2\) new vertices. The \(r\)-graph \(K_{r,r}^{(r)}\) is the extension of the \(r\)-graph consisting of two disjoint edges. An \(r\)-graph \(H\) is a star if its vertex set admits a partition \((A,B)\) such that \(|e \cap A|=1\) for every edge \(e\) of \(H\). Let \(S^{(r)}(n)\) denote the star on \(n\) vertices with the maximum number of edges. The main result established in this paper is the following. For every \(r \geq 4\), there exists \(n_0 := n_0(r)\) such that \(\mathrm{ex}(n,K_{r,r}^{(r)})= {\mathrm e}(S^{(r)}(n))\) for all \(n > n_0(r)\) and every \(K_{r,r}^{(r)}\)-free \(r\)-graph on \(n\) vertices with maximum number of edges is a star.
The Lagrangian \(\lambda(F)\) of an \(r\)-graph \(F\) is defined as \(\lambda(F)=\max_p \sum_{e \in F} \prod_{v \in e}p(v)\), where the maximum is taken over all probability distributions \(p\) on the vertex set \(V(F)\). An \(r\)-graph \(H\) is intersecting if \(e \cap f \neq \emptyset\) for any pair of edges \(e\) and \(f\) of \(H\). Furthermore, \(H\) is principal if there is a vertex of \(H\) that intersects every edge of \(H\). The main result is derived from the following theorem proved in this paper. For every \(r \geq 4\) there exists a constant \(c_r\) such that, if \(H\) is a non-principal intersecting \(r\)-graph, then \(\lambda(H) < \frac{1}{r!}\left( (1-\frac{1}{r})^{r-1}- c_r \right)\).
Reviewer: Ko-Wei Lih (Taipei)Research of an epidemic model on adaptive networks.https://zbmath.org/1449.920432021-01-08T12:24:00+00:00"Chen, Lu"https://zbmath.org/authors/?q=ai:chen.lu"Zhang, Xiaoguang"https://zbmath.org/authors/?q=ai:zhang.xiaoguangSummary: A new stochastic single population system with age-dependent and diffusion in a polluted environment is formulated and investigated. By using the triple approximation formula under multinomial distributions, the SIS moment closure infectious disease model in the adaptive network is closed, the effect of adaptive behavior on the spread of infectious diseases under multinomial distributions is studied. Through the theory of qualitative and stability, the basic reproduction number \({R_0}\) of the model is obtained and the stability of the equilibrium points is analyzed. It is obtained that the adaptive behavior of rewiring has multiple effects on infectious disease transmission. When the relative infection rate is small enough, the model has a standard forward bifurcation, and when \({R_0} < 1\), the disease tends to be extinct. On the contrary, mathematically, it is rigorously proved that the rewiring can lead to the occurrence of complex dynamic behaviors such as the backward bifurcation and saddle-node bifurcation, etc. Therefore \({R_0} < 1\) is not enough to control the spread of infectious diseases.Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue.https://zbmath.org/1449.051102021-01-08T12:24:00+00:00"Scott, Alex"https://zbmath.org/authors/?q=ai:scott.alexander-d"Seymour, Paul"https://zbmath.org/authors/?q=ai:seymour.paul-dIn graph theory, researchers are very often concerned with induced subgraphs of graphs with large chromatic number, and especially, which induced cycles must occur. In this work, the authors unify and substantially extend results from a number of previous papers. It is shown that for every positive number \(k\) every graph with large chromatic number contains either a large complete subgraph or induced cycles of lengths modulo \(k\). In view of this, two conjectures of Kalai and Meshulam from the 1990's connecting the chromatic number of a graph with the homology of its independence complex are proved.
Reviewer: Mirko Lepović (Kragujevac)On the complementary distance energy of join of certain graphs.https://zbmath.org/1449.050852021-01-08T12:24:00+00:00"Ramane, Harishchandra S."https://zbmath.org/authors/?q=ai:ramane.harishchandra-s"Gundloor, Mahadevappa M."https://zbmath.org/authors/?q=ai:gundloor.mahadevappa-mSummary: The complementary distance matrix of a graph \(G\) is defined as \(CD(G) = [c_{ij}]\), in which \(c_{ij}= 1 + D-d_{ij}\) if \(i \ne j\) and \(c_{ij}= 0\) if \(i=j\), where \(D\) is the diameter of \(G\) and \(d_{ij}\) is the distance between the vertices \(v_i\) and \(v_j\) in \(G\). The complementary distance energy \(CDE(G)\) of \(G\) is defined as the sum of the absolute values of the eigenvalues of complementary distance matrix of \(G\). Two graphs \(G_1\) and \(G_2\) are said to be \(CD\)-equienergetic if \(CDE(G_1) = RCDE(G_2)\). In this paper, we obtain the \(CD\)-polynomial and \(CD\)-energy of the join of regular graphs of diameter at most two. We use these results to show that there exists at least one pair of \(CD\)-non-cospectral, \(CD\)-equienergetic graphs on \(n\) vertices, for every \(n \geq 6\).Signed total domination number of two classes of graphs.https://zbmath.org/1449.052022021-01-08T12:24:00+00:00"Ma, Menghan"https://zbmath.org/authors/?q=ai:ma.menghan"Hong, Xia"https://zbmath.org/authors/?q=ai:hong.xiaSummary: In this paper, we study the signed total domination number \({\gamma_{st}} (G)\) of graphs \(G\). We obtain exact values of the signed total domination number of two classes of graphs \(n \cdot {F_{m + 1}}\) and \(n \cdot {W_{m + 1}}\) by exhaustive method and classified discussion, which corrected the known results, where \(n \cdot {F_{m + 1}}\) and \(n \cdot {W_{m + 1}}\) denote a graph obtained by identifying the center vertex of \(n\) Fan graphs \({F_{m + 1}}\) and a graph obtained by identifying the center vertex of \(n\) Wheel graphs \({W_{m + 1}}\), respectively.Algorithm on the optimal vertex-distinguishing total coloring of \(m{C_9}\).https://zbmath.org/1449.050962021-01-08T12:24:00+00:00"He, Yuping"https://zbmath.org/authors/?q=ai:he.yuping"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangenSummary: Let \(G\) be a simple graph and \(f\) be a proper total coloring (or a total coloring in brief) of \(G\). For any vertex \(u\) in \(G\), \({C_f} (u)\) denotes the set of colors of vertex \(u\) and edges which are coincident with vertex \(u\). \({C_f} (u)\) is said to be the color set of vertex \(u\) under \(f\). If \({C_f} (u) \ne {C_f} (v)\) for any two distinct vertices \(u\) and \(v\) of \(G\), then \(f\) is called vertex-distinguishing total coloring of \(G\) (in brief VDTC). A vertex distinguishing total coloring using \(k\) colors is called \(k\)-vertex distinguishing total coloring of \(G\) (in brief \(k\)-VDTC). The minimum number \(k\) for which there exists a \(k\)-vertex-distinguishing total coloring of \(G\) is called the vertex-distinguishing total chromatic number of \(G\), denoted by \({\chi_{vt}} (G)\). By the method of prior distributing the color sets, we obtain vertex-distinguishing total chromatic number of \(m{C_9}\) in this paper.Towards Erdős-Hajnal for graphs with no 5-hole.https://zbmath.org/1449.051482021-01-08T12:24:00+00:00"Chudnovsky, Maria"https://zbmath.org/authors/?q=ai:chudnovsky.maria"Fox, Jacob"https://zbmath.org/authors/?q=ai:fox.jacob"Scott, Alex"https://zbmath.org/authors/?q=ai:scott.alexander-d"Seymour, Paul"https://zbmath.org/authors/?q=ai:seymour.paul-d"Spirkl, Sophie"https://zbmath.org/authors/?q=ai:spirkl.sophie-theresaIn this paper, all graphs are finite and have no loops or parallel edges. The cardinalities of the largest stable sets and cliques in a graph \(G = (V, E)\) with \(|V|=n\) are denoted by \(\alpha(G)\) and \(\omega(G)\), respectively. For two graphs \(G\) and \(H\) we say that \(G\) contains \(H\) if some induced subgraph of \(G\) is isomorphic to \(H\) and \(G\) is \(H\)-free otherwise. The Erdős-Hajnal conjecture says that for every graph \(H\) there exists \(c > 0\) such that \(\max(\alpha(G), \omega(G)) \geq n^c\) for every \(H\)-free graph \(G\) and this is still open when \(H=C_5\) (\(C_5\) denotes the cycle of length 5). The best general bound for the Erdős-Hajnal conjecture to date \(\max((\alpha(G), \omega(G)) \geq n^{c \sqrt{log(n)}}\) was proved by \textit{P. Erdős} and \textit{A. Hajnal} [Discrete Appl. Math. 25, No. 1--2, 37--52 (1989; Zbl 0715.05052)] for every \(H\)-free graph \(G\) (logarithm is of base 2). This was also the known bound for \(H = C_5\). In this paper, the authors improve the bound to \(\max((\alpha(G), \omega(G)) \geq n^{c \sqrt{log(n) log(n) log(n)}}\) for every \(C_5\)-free graph \(G\).
Reviewer: Eleonor Ciurea (Braşov)A class of non-matchable distributive lattices.https://zbmath.org/1449.052172021-01-08T12:24:00+00:00"Wang, Xu"https://zbmath.org/authors/?q=ai:wang.xu.5"Zhao, Xuxu"https://zbmath.org/authors/?q=ai:zhao.xuxu"Yao, Haiyuan"https://zbmath.org/authors/?q=ai:yao.haiyuanSummary: In this paper, we consider non-matchable distributive lattices. By introducing the meet-irreducible cell with respect to a perfect matching of a plane elementary bipartite graph and giving its characterizations, we obtain a new class of non-matchable distributive lattices, and extend a result on non-matchable distributive lattices with a cut element.A new upper bound for the size of \(s\)-distance sets in boxes.https://zbmath.org/1449.520112021-01-08T12:24:00+00:00"Hegedűs, G."https://zbmath.org/authors/?q=ai:hegedus.gaborThe subject is related to the following distance problem by Erdős: Given \(n\) points in the plane, what is the smallest number of distinct distances they can determine? In 1946 Erdős gave some inequalities for the minimum number of these distances.
An \(s\)-distance set is any subset \(G\) of \(n\)-dimensional Euclidean space such that the size of the set of distances among points of \(G\) (the number of distinct distances) is at most \(s\).
In the paper, the author investigates \(s\)-distance sets in the direct product of finite sets of points (boxes) in \(n\)-dimensional Euclidean space. A new upper bound for the size of \(s\)-distance sets in boxes is given. In the proof, the author uses Tao's slice rank method.
Reviewer: Elizaveta Zamorzaeva (Chişinău)Impact of weights on opinion propagation in complex networks.https://zbmath.org/1449.910842021-01-08T12:24:00+00:00"Li, Xiaolin"https://zbmath.org/authors/?q=ai:li.xiaolin"Yuan, Meng"https://zbmath.org/authors/?q=ai:yuan.meng"Wang, Peng"https://zbmath.org/authors/?q=ai:wang.peng.1|wang.peng|wang.peng.2"Xu, Xinjian"https://zbmath.org/authors/?q=ai:xu.xinjianSummary: The investigation of structure and dynamics of social networks has regularly attracted contributions from applied mathematicians and social scientists over the last several decades. The high interest is a broad range of dynamical processes unfolding over underline networks, e.g., opinion formation and propagation. The threshold model has been widely adopted as a classic model for studying such contagion processes on social networks. Previous studies, however, have paid less attention on weighted properties of nodes or links. In this paper, a modified threshold model on weighted networks has been proposed and studied by Monte-Carlo simulations. Two regimes of the underline weights are identified in which the system exhibits distinct behaviors: when networks are sufficiently sparse, there exists the worst weight value causing maximal spreading; when networks are sufficiently dense, on the contrary, there exists the best weight value maintaining best robustness.The classification of \(f\)-coloring of random graphs.https://zbmath.org/1449.051132021-01-08T12:24:00+00:00"Xiong, Yaping"https://zbmath.org/authors/?q=ai:xiong.yaping"Cai, Jiansheng"https://zbmath.org/authors/?q=ai:cai.jianshengSummary: A random graph \(G\left ({n, p} \right)\) is a graph on \(n\) labeled vertices, in which every pair of vertices is chosen to be an edge of \(G\) randomly and independently with probability \(p\). In particular, when \(p = \frac{1}{2}\), a probability space is given where all labeled graphs on \(n\) vertices are equiprobable. For a simple graph \(G = \left ({V, E} \right)\) with vertex set \(V\) and edge set \(E\), an \(f\)-coloring \(c\) of \(G\) is a generalized edge-coloring in which each color class appears at each vertex \(v\) at most \(f\left (v \right)\) times where \(f\left (v \right)\) is a positive integer assigned to \(v\). A sufficient condition for the random graph \(G\left ({n, \frac{1}{2}} \right)\) to be \(f\)-class 1 is given.A novel hybrid method for solving combined functional neutral differential equations with several delays and investigation of convergence rate via residual function.https://zbmath.org/1449.651662021-01-08T12:24:00+00:00"Kurkcu, Omur Kıvanc"https://zbmath.org/authors/?q=ai:kurkcu.omur-kivanc"Aslan, Ersin"https://zbmath.org/authors/?q=ai:aslan.ersin"Sezer, Mehmet"https://zbmath.org/authors/?q=ai:sezer.mehmetSummary: In this study, we introduce a novel hybrid method based on a simple graph along with operational matrix to solve the combined functional neutral differential equations with several delays. The matrix relations of the matching polynomials of complete and path graphs are employed in the matrix-collocation method. We improve the obtained solutions via an error analysis technique. The oscillation of them on time interval is also estimated by coupling the method with Laplace-Pad'{e} technique. We develop a general computer program, and so we can efficiently monitor the precision of the method. We investigate a convergence rate of the method by constructing a formula based on the residual function. Eventually, an algorithm is described to show the easiness of the method.A note on decycling number and vertex-arboricity of cubic graphs.https://zbmath.org/1449.051552021-01-08T12:24:00+00:00"Yang, Chao"https://zbmath.org/authors/?q=ai:yang.chao.2|yang.chao.3|yang.chao.1"Ren, Han"https://zbmath.org/authors/?q=ai:ren.hanSummary: In this paper, from the view of graph embedding, we provide a formula for the decycling number of cubic graphs. Together with the above formula and the maximum genus theorem, we prove that \(a (G) = 2\) for any cubic graph \(G\), where \(a (G)\) is the vertex-arboricity of \(G\), and the result confirms the conjecture ``every planar graph \(G\) without 3-cycles has a vertex partition \( ({V_1}, {V_2})\) such that \({V_1}\) is an independent set and \({V_2}\) induces a forest'' due to some previous authors.Beginnings of matrix theory in the Czech Republic and their results.https://zbmath.org/1449.150012021-01-08T12:24:00+00:00"Štěpánová, Martina"https://zbmath.org/authors/?q=ai:stepanova.martinaThe book traces the early history of matrix theory in the Czech lands approximately in the period 1850--1950. The main emphasis is on the outstanding results of Eduard Weyr (1852--1903) dealing with the so-called Weyr characteristic and Weyr canonical form. These concepts are closely related to the well-known Segre characteristic and Jordan canonical form of a square matrix. Despite Weyr's priority over Jordan, his results remained almost forgotten for about a century. The Weyr characteristic has become increasingly popular since the 1980s thanks to H. Schneider, D. Hershkowitz, and their followers, who were studying relations between matrices and their associated graphs. The Weyr canonical form has been rediscovered several times, and became more widely known due to \textit{H. Shapiro}'s paper [Am. Math. Mon. 106, No. 10, 919--929 (1999; Zbl 0981.15008)], who introduced it to nonspecialists and gave proper credit to Weyr.
The text represents an expanded version of the author's dissertation thesis. It is based on a careful study of a large number of primary sources spanning the period of about 150 years. Weyr's results are first described in a proper historical context, and then explained once again in the language of modern mathematics. A considerable portion of the book is devoted to the reception of Weyr's work since its publication until the present day. The book is very well written and will be of interest to all historians of mathematics. Readers who are not fluent in Czech can take advantage of a twenty-page-long English summary.
Reviewer: Antonín Slavík (Praha)On domination numbers of special graphs.https://zbmath.org/1449.051972021-01-08T12:24:00+00:00"Ao, Guoyan"https://zbmath.org/authors/?q=ai:ao.guoyan"Hong, Xia"https://zbmath.org/authors/?q=ai:hong.xia"Zhang, Guizhi"https://zbmath.org/authors/?q=ai:zhang.guizhiSummary: The domination number of a graph has its important applying background. In this paper, we determined the domination numbers of graphs \({P_m} \vee {{\overline K}_n}\) and \({C_m} \vee {{\overline K}_n}\), and obtained two upper bounds of domination numbers of graphs \(C (n, m)\) and \(C (n, m, n)\).The inclusion graph of \(S\)-acts.https://zbmath.org/1449.051382021-01-08T12:24:00+00:00"Sun, Shuang"https://zbmath.org/authors/?q=ai:sun.shuang"Liu, Hongxing"https://zbmath.org/authors/?q=ai:liu.hongxing.1|liu.hongxingSummary: Let \(S\) be a semigroup and \(M\) be an \(S\)-act. The inclusion graph of \(M\), denoted by \(G (M)\), is the undirected simple graph whose vertices are all non-trivial subact of \(M\) and defining two distinct vertices \(I\) and \(J\) to be adjacent if and only if \(I \subseteq J\) or \(J \subseteq I\). Some results on completeness, connectivity, diameter, girth, the clique number and the chromatic number of \(G (M)\) are presented.Structure learning of \({\mathrm{PM}}_{2.5}\) distribution using sparse graphical models.https://zbmath.org/1449.622612021-01-08T12:24:00+00:00"Zhang, Hai"https://zbmath.org/authors/?q=ai:zhang.hai.2"Guo, Xiao"https://zbmath.org/authors/?q=ai:guo.xiao"Ren, Sa"https://zbmath.org/authors/?q=ai:ren.sa"Deng, Yajing"https://zbmath.org/authors/?q=ai:deng.yajingSummary: We consider the structure learning problem of the \({\mathrm{PM}}_{2.5}\) pollution data over 31 provincial capitals in China. Specifically, we make use of the graphical model tools to study the hubs and the community structures of the \({\mathrm{PM}}_{2.5}\) pollution networks. The results show that the hubs in the \({\mathrm{PM}}_{2.5}\) pollution networks are always seriously polluted cities, and the \({\mathrm{PM}}_{2.5}\) pollution networks have significant community structures which consist of cities which in some sense can be regarded as blocks with similar cause of pollution. In view of the results, we suggest that the government should strengthen the effort to treat the seriously polluted areas and western China areas. Moreover, the management of the \({\mathrm{PM}}_{2.5}\) pollution should be region-dependent.Stability results on the circumference of a graph.https://zbmath.org/1449.051632021-01-08T12:24:00+00:00"Ma, Jie"https://zbmath.org/authors/?q=ai:ma.jie"Ning, Bo"https://zbmath.org/authors/?q=ai:ning.boAuthors' abstract: In this paper, we extend and refine previous Turán-type results on graphs with a given circumference. Let \(W_{n,k,c}\) be the graph obtained from a clique \(K_{c-k+1}\) by adding \(n-(c-k+1)\) isolated vertices each joined to the same \(k\) vertices of the clique, and let \(f(n,k,c) = e(W_{n,k,c})\). Improving a celebrated theorem of \textit{P. Erdős} and \textit{T. Gallai} [Acta Math. Acad. Sci. Hung. 10, 337--356 (1959; Zbl 0090.39401)], \textit{G. N. Kopylov} [Sov. Math., Dokl. 18, 593--596 (1977; Zbl 0419.05032); translation from Dokl. Akad. Nauk SSSR 234, 19--21 (1977)] proved that for \(c<n\), any 2-connected graph \(G\) on \(n\) vertices with circumference \(c\) has at most \(\max\{f(n,2, c), f(n, \lfloor c/2\rfloor, c)\}\) edges, with equality if and only if \(G\) is isomorphic to \(W_{n,2,c}\) or \(W_{ n, \lfloor c/2\rfloor, c}\). Recently, \textit{Z. Füredi} et al. [J. Comb. Theory, Ser. B 121, 197--228 (2016; Zbl 1348.05105)] proved a stability version of Kopylov's theorem. Their main result states that if \(G\) is a 2-connected graph on \(n\) vertices with circumference \(c\) such that \(10\leq c<n\) and \(e(G)>\max \{ f(n,k+1,c), f(n, \lfloor c/2\rfloor -1,c)\}\) then either \(G\) is a subgraph of \(W_{n,2,c}\) or \(W_{ n,\lfloor c/2 \rfloor ,c}\) or \(c\) is odd and \(G\) is a subgraph of a member of two well-characterized families which we define as \(\mathcal{X}_{n,c}\) and \(\mathcal{Y}_{n,c}\). We prove that if \(G\) is a 2-connected graph on \(n\) vertices with minimum degree at least \(k\) and circumference \(c\) such that \(10\leq c<n\) and \(e(G)>\max\{f(n,k+1, c), f(n, \lfloor c/2 \rfloor -1,c)\}\), then one of the following holds:
(i) \(G\) is a subgraph of \(W_{n,k,c}\) or \(W_{n,\lfloor c/2 \rfloor,c}\),
(ii) \(k=2\), \(c\) is odd, and \(G\) is a subgraph of a member of \(\mathcal{X}_{n,c} \cup \mathcal{Y}_{n,c}\), or
(iii) \(k\geq 3\) and \(G\) is a subgraph of the union of a clique \(K_{c-k+1}\) and some cliques \(K_{k+1}\)'s, where any two cliques share the same two vertices.
This provides a unified generalization of the above result of Füredi et al. [loc. cit.] as well as a recent result of \textit{B. Li} and \textit{B. Ning} [Linear Multilinear Algebra 64, No. 11, 2252--2269 (2016; Zbl 1352.05105)] and independently, of \textit{Z. Füredi} et al. [Discrete Math. 340, No. 11, 2688--2690 (2017; Zbl 1369.05118)] on non-Hamiltonian graphs. A refinement and some variants of this result are also obtained. Moreover, we prove a stability result on a classical theorem of \textit{J. A. Bondy} [ibid. 1, 121--132 (1971; Zbl 0224.05120)]. We use a novel approach, which combines several proof ideas including a closure operation and an edge-switching technique. We will also discuss some potential applications of this approach for future research.
Reviewer: Ioan Tomescu (Bucureşti)Homomorphism thresholds for odd cycles.https://zbmath.org/1449.051492021-01-08T12:24:00+00:00"Ebsen, Oliver"https://zbmath.org/authors/?q=ai:ebsen.oliver"Schacht, Mathias"https://zbmath.org/authors/?q=ai:schacht.mathiasAuthors' abstract: The interplay of minimum degree conditions and structural properties of large graphs with forbidden subgraphs is a central topic in extremal graph theory. For a given graph \(F\) we define the homomorphism threshold as the infimum over all \(\alpha\in [0,1]\) such that every \(n\)-vertex \(F\)-free graph \(G\) with minimum degree at least \(\alpha n\) has a homomorphic image \(H\) of bounded order (i.e. independent of \(n\)), which is \(F\)-free as well. Without the restriction of \(H\) being \(F\)-free we recover the definition of the chromatic threshold, which was determined for every graph \(F\) by \textit{P. Allen} et al. [Adv. Math. 235, 261--295 (2013; Zbl 1263.05048)]. The homomorphism threshold is less understood and we address the problem for odd cycles.
Reviewer: Ioan Tomescu (Bucureşti)The signed total reinforcement number of \(P (n, 2)\).https://zbmath.org/1449.051282021-01-08T12:24:00+00:00"Li, Ning"https://zbmath.org/authors/?q=ai:li.ningSummary: We define the signed total reinforcement number of a graph \(G\), denoted by \(R_t^s (G)\), to be the minimum cardinality of a set \(S \subseteq {E^C} (G)\) such that \(\gamma_t^s (G + S) < \gamma_t^s (G)\). This paper gives the \(R_t^s\) of generalized Petersen graphs \(P (n, 2)\) for \(n \ge 6\). If \(n \equiv 2 \pmod 3\), then \(R_t^s (P (n, 2)) = 2\); if \(n \equiv 1 \pmod 3\), then \(R_t^s (P (n, 2)) = 3\); if \(n \equiv 0 \pmod 3\), then \(R_t^s (P (n, 2)) = 5\).Coloring dense digraphs.https://zbmath.org/1449.050952021-01-08T12:24:00+00:00"Harutyunyan, Ararat"https://zbmath.org/authors/?q=ai:harutyunyan.ararat"Le, Tien-Nam"https://zbmath.org/authors/?q=ai:le.tien-nam"Newman, Alantha"https://zbmath.org/authors/?q=ai:newman.alantha"Thomassé, Stéphan"https://zbmath.org/authors/?q=ai:thomasse.stephanLet \(\alpha (D),\chi (D)\) denote the independence and the chromatic number of a digraph \(D,\) respectively. A tournament \ \(S\) is called a hero, if there is a number \(f(S)\) such that \(\chi (T)\leq f(S)\) for every tournament \(T\) that does not contain \(S\) as an induced subgraph. \textit{E. Berger} et al. [J. Comb. Theory, Ser. B 103, No. 1, 1--20 (2013; Zbl 1254.05064)] fully characterized the class of heroes. In this paper, the authors introduce a notion of a superhero. A digraph \(H\) is called a superhero if for every \(\alpha \geq 1,\) there is a number \(g(H,\alpha )\) such that \(\chi (D)\leq g(H,\alpha )\) for every digraph \(D\), \(\alpha (D)=\alpha ,\) that does not contain \(H\) as an induced subgraph. The main result of the paper states that a digraph is a superhero if and only if it is a hero.
Reviewer: Peter Horák (Tacoma)The signature of generalized line graph and \(\{{C_4^1}, {K_{1,3}^1}, {K_{1,4}}\}\)-free graph.https://zbmath.org/1449.051812021-01-08T12:24:00+00:00"Zhao, Zhimin"https://zbmath.org/authors/?q=ai:zhao.zhimin"He, Changxiang"https://zbmath.org/authors/?q=ai:he.changxiang"Xu, Guanghui"https://zbmath.org/authors/?q=ai:xu.guang-huiSummary: The positive (resp., negative) inertia index of \(G\), denoted by \(p (G)\) (resp., \(n (G)\)), is defined to be the number of positive (resp., negative) eigenvalues of its adjacency matrix. The signature \(s (G)\) of a graph \(G\) is defined as the difference between its positive inertia index and negative inertia index. In 2013, some researchers conjectured that \(-{c_3} (G) \le s (G) \le {c_5} (G)\) for an arbitrary simple graph \(G\), where \({c_3} (G)\) denotes the number of cycles in \(G\) of length 3 modulo 4, \({c_5} (G)\) denotes the number of cycles in \(G\) of length 1 modulo 4. This paper proves that this conjecture holds for generalized line graphs and the \(\{{C_4^1}, {K_{1,3}^1}, {K_{1,4}}\}\)-free graph.Interval edge-coloring of the generalized \(\theta\)-chain.https://zbmath.org/1449.050932021-01-08T12:24:00+00:00"Chen, Xun"https://zbmath.org/authors/?q=ai:chen.xun"Huang, Qiongxiang"https://zbmath.org/authors/?q=ai:huang.qiongxiang"Chen, Lin"https://zbmath.org/authors/?q=ai:chen.lin.3Summary: An edge-coloring of a graph \(G\) with colors \(1,2,\dots, t\) is an interval \(t\)-coloring if all colors are used, and the colors of edges incident to each vertex of \(G\) are distinct and form a continuous interval of integers. A graph \(G\) is interval colorable if it has an interval \(t\)-coloring for some positive integer \(t\). The set of all interval colorable graphs is denoted by \(\mathfrak{R}\). The deficiency def\( (G)\) of a graph \(G\) is the minimum number of pendant edges whose attachment to \(G\) makes it interval colorable. Obviously, \(G \in \mathfrak{R}\) if and only if \({\mathrm{def}} (G) = 0\). A generalized \(\theta\)-chain, denoted by \({\theta_{{m_1}, {m_2}, \dots, {m_k}}}\), is a simple graph obtained by substituting each edge \({v_{i-1}}{v_i}\) of the path \(P = [{v_0}, {v_1}, \dots, {v_k}]\) (\(k\ge 1\)) for \({m_i} \ge 2\) pairwise internally disjoint \( ({v_{i - 1}}{v_i})\)-paths, where \({i = 1, 2, \dots, k}\). In this paper, the conclusions of deficiency of generalized \(\theta\)-graph are generalized, and the deficiency of the generalized \(\theta\)-chain \({\theta_{{m_1}, {m_2}, \dots, {m_k}}}\) is determined.Edge transitive maps of complete graph with the prime vertices.https://zbmath.org/1449.051402021-01-08T12:24:00+00:00"Yu, Xue"https://zbmath.org/authors/?q=ai:yu.xue"Lou, Bengong"https://zbmath.org/authors/?q=ai:lou.bengongSummary: We study the edge-transitive but not arc-transitive maps of complete graphs \({K_p}\), where \(p\) is an odd prime such that \(p \equiv 3 \pmod 4\). A construction of the map and the enumeration formulate of non-isomorphic such maps are given. Furthermore, we obtain the genus of the map under certain conditions.Topology of complexes of edge covering partite graphs and hypergraphs.https://zbmath.org/1449.050802021-01-08T12:24:00+00:00"Vassiliev, Victor A."https://zbmath.org/authors/?q=ai:vassiliev.victor-aThe vertex set \(A\) of an \(m\)-partite \(r\)-hypergraph of type \((k_1,\ldots,k_m)\) partitions into \(m\) subsets \(A_i\) of orders \(k_1,\ldots,k_m\) and the edges are the \(r\)-subsets of \(A\) all \(r\) elements of any of which belong to different sets \(A_i\). An \(m\)-partite \(r\)-hypergraph is edge-covering if each vertex of the corresponding \(m\)-partite graph belongs to at least one hyperedge. Each \(m\)-partite \(r\)-hypergraph corresponds to a face of the simplex whose vertices are all the \(r\)-element hyperedges on \(A\); the face is spanned by its hyperedges. The faces spanned by the non-edge-covering \(m\)-partite \(r\)-hypergraphs form the simplicial subcomplex \( {\mathcal{H}}_r(A) \). The aim of this article is the calculation of the homology groups and homotopy types of the two related complexes formed by the edge-covering and non-edge-covering \(m\)-partite \(r\)-hypergraphs.
In the main result of the article, it is shown that \( {\mathcal{H}}_r(A) \) is homotopy equivalent to the wedge of \( \binom{m-1}{r-1} \) spheres of dimension \(\vert A\vert -r-1\), it is acyclic in all positive dimensions except for \(\vert A\vert -r-1\), its \((\vert A\vert -r-1)\)-homology group is \( {\mathbb{Z}}^\binom{m-1}{r-1} \), and its Euler characteristic is \( 1 - (-1)^{\vert A\vert -r}\binom{m-1}{r-1} \). The factorization of the entire simplex by \( {\mathcal{H}}_r(A) \) is a cell complex whose cells correspond to the edge-covering \(r\)-hypergraphs and the \(i\)-th homology group of this complex is trivial except for the case \(i=\vert A\vert -r\) when it is the group \( {\mathbb{Z}}^\binom{m-1}{r-1} \). The factoring's Euler characteristic is equal to \( 1 + (-1)^{\vert A\vert -r}\binom{m-1}{r-1} \). Beside providing the proofs and some further results, the author considers in more detail the two special cases \( m=r \) and \( \vert A\vert =m \).
Reviewer: Robert Jajcay (Terre Haute)Encoding and classification of permutations by special conversion with estimates of class power.https://zbmath.org/1449.050082021-01-08T12:24:00+00:00"Savchuk, M. M."https://zbmath.org/authors/?q=ai:savchuk.m-m"Burlaka, M. K."https://zbmath.org/authors/?q=ai:burlaka.m-kSummary: Scientific articles investigating properties and estimates of the number of so-called complete permutations are surveyed and analyzed. The paper introduces a special \(S\)-transform on the set of permutations and determines the permutation properties according to this transform. Classification and coding of permutations by equivalence classes according to their properties with respect to \(S\)-transformation is proposed. This classification and permutation properties, in particular, generalize known results for complete permutations regarding determining certain cryptographic properties of substitutions that affect the cryptographic transformations security. The exact values of the number of permutations in equivalence classes for certain permutation sizes are calculated and the estimates of the cardinality of classes with various properties are constructed by statistical modeling. The complete list of permutation classes with the exact values of their sizes for permutations of order \(n = 11\) is presented. The interval estimates for the size of classes with various characteristics for permutations of order \(n = 11, 26, 30, 31, 32, 33, 45, 55\) are obtained. Monte Carlo estimates and bounds of confidence intervals used the approximation of the binomial distribution by the normal and Poisson distributions, as well as the Python programming language package Scipy. Statistical tables have been calculated that can be used for further conclusions and estimates. The classification of permutations by their properties with respect to the introduced transform can be used in constructing high-quality cryptographic transformations and transformations with special features. The classes of complete permutations with their properties are selected as the best for rotary cryptosystem applications. The obtained results can be used, in particular, to search for permutations with certain characteristics and properties, to find the probability that the characteristic of the generated permutation belongs to a collection of given characteristics, to estimate the complexity of finding permutations with certain properties. A statistical criterion of consent, which uses the characteristics of permutations by \(S\) transformation to test the generators of random permutations and substitutions is proposed.The relationship between the thickness of the complete bipartite graph \({K_{n + 1,2n}}\) and the complete tripartite graph \({K_{1,n,2n}}\).https://zbmath.org/1449.050752021-01-08T12:24:00+00:00"Dong, Xue"https://zbmath.org/authors/?q=ai:dong.xue"Yang, Yan"https://zbmath.org/authors/?q=ai:yang.yanSummary: The thickness of a graph \(G\) is the minimum number of planar spanning subgraphs into which \(G\) can be decomposed. It is one of the key indicators for measuring the planarity of a graph. It is important to study the thickness of a graph. There are many important applications in VLSI and network design. At present, the exact thickness of some types of graphs are obtained, but the relationship between the thickness of the complete bipartite graph and the complete tripartite graph has not been fully presented. In this paper, we obtain the thickness of the complete tripartite graph \({K_{1,n,2n}}\) by constructing a planar decomposition of the complete tripartite graph \({K_{1, 3p+1, 6p+2}}\), and get the result that the thickness of \({K_{n+1, 2n}}\) and \({K_{1,n,2n}}\) is equal.On zero divisor graphs of the rings \(Z_n\).https://zbmath.org/1449.130082021-01-08T12:24:00+00:00"Pirzada, S."https://zbmath.org/authors/?q=ai:pirzada.shariefuddin"Aijaz, M."https://zbmath.org/authors/?q=ai:aijaz.malla"Bhat, M. Imran"https://zbmath.org/authors/?q=ai:bhat.m-imranSummary: For a commutative ring \(R\) with non-zero zero-divisor set \(Z^*(R)\), the zero-divisor graph of \(R\) is \(\varGamma (R)\) with vertex set \(Z^*(R)\), where two distinct vertices \(x\) and \(y\) are adjacent if and only if \(xy=0\). The zero-divisor graph structure of \(\mathbb{Z}_{p^n}\) is described. We determine the clique number, degree of the vertices, size, metric dimension, upper dimension, automorphism group, Wiener index of the associated zero-divisor graph of \(\mathbb{Z}_{p^n}\). Further, we provide a partition of the vertex set of \(\varGamma (\mathbb{Z}_{p^n})\) into distance similar equivalence classes and we show that in this graph the upper dimension equals the metric dimension. Also, we discuss similar properties of the compressed zero-divisor graph.Fixed-time mixed outer synchronization of complex networks.https://zbmath.org/1449.341892021-01-08T12:24:00+00:00"Nie, Pingping"https://zbmath.org/authors/?q=ai:nie.pingping"Li, Wang"https://zbmath.org/authors/?q=ai:li.wang"Shi, Hongjun"https://zbmath.org/authors/?q=ai:shi.hongjunSummary: In this paper, the fixed-time mixed outer synchronization between two complex dynamical networks is studied. By using suitable controllers, we achieve the fixed-time mixed outer synchronization between two complex networks based on the fixed-time stability theory. Finally, numerical simulations are performed to illustrate the effectiveness and feasibility of the proposed control approach.Signed domination numbers for two classes of product graphs.https://zbmath.org/1449.052062021-01-08T12:24:00+00:00"Xu, Baogen"https://zbmath.org/authors/?q=ai:xu.baogen"Zhang, Junxia"https://zbmath.org/authors/?q=ai:zhang.junxia"Li, Guang"https://zbmath.org/authors/?q=ai:li.guangSummary: \(G = (V, E)\) is hypothesized a graph. A two-valued function \(f:V\to\{-1, +1\}\) is said to be a signed domination function of the graph \(G\) if \(\sum\limits_{u\in N[v]}f (u)\ge 1\) holds for every vertex \(v \in V\). The signed domination number of graph \(G\) is defined as \({\gamma_s} (G) = \min\{\sum\limits_{v \in V} f (v)\}\) (\(f\) is a signed domination function of graph \(G\)). It is verified that the partial results of a previous study is wrong by enumerating some examples of graph classes. The signed domination numbers of two classes of product graphs \({C_n} \times {P_3}\) and \({P_n} \times {P_3}\) are re-determined.Seymour's second neighborhood in 3-free digraphs.https://zbmath.org/1449.051202021-01-08T12:24:00+00:00"Chen, Bin"https://zbmath.org/authors/?q=ai:chen.bin.5|chen.bin.2|chen.bin.3|chen.bin.4|chen.bin.1"Chang, An"https://zbmath.org/authors/?q=ai:chang.anSummary: In this paper, we consider Seymour's second neighborhood conjecture in 3-free digraphs, and prove that for any 3-free digraph \(D\), there exists a vertex \(v\), such that \(d^{++} (v) \ge \lfloor \lambda {d^+} (v) \rfloor\), \(\lambda = 0.6958 \dots\). This slightly improves the known results in 3-free digraphs with large minimum out-degree.Brauer upper bound for the \(Z\)-spectral radius of nonnegative tensors.https://zbmath.org/1449.150492021-01-08T12:24:00+00:00"He, Jun"https://zbmath.org/authors/?q=ai:he.jun"Ke, Hua"https://zbmath.org/authors/?q=ai:ke.hua"Liu, Yanmin"https://zbmath.org/authors/?q=ai:liu.yanmin"Tian, Junkang"https://zbmath.org/authors/?q=ai:tian.junkangSummary: In this paper, we propose an upper bound for the largest \(Z\)-eigenvalue of an irreducible weakly symmetric and nonnegative tensor, which is called the Brauer upper bound: \[\rho_Z (A)\le\frac{1}{2}\max\limits_{\begin{subarray} {1}{i,j \in N}\\ {j \ne i}\end{subarray}} ({a_{i\cdots i}} + {a_{j\cdots j}} + \sqrt{({a_{i\cdots i}}-{a_{j\cdots j}})^2 + 4{r_i} (A){r_j} (A)}),\] where \({r_i} (A) = \sum\limits_{{ii_2} \cdots {i_m} \ne ii \cdots i} {a_{{ii_2} \cdots {i_m}}}\), \(i, {i_2}, \dots, {i_m} \in N = \{1,2,\ldots, n\} \). As applications, a bound on the \(Z\)-spectral radius of uniform hypergraphs is presented.Bicomplex generalized \(k\)-Horadam quaternions.https://zbmath.org/1449.110372021-01-08T12:24:00+00:00"Yazlik, Yasin"https://zbmath.org/authors/?q=ai:yazlik.yasin"Köme, Sure"https://zbmath.org/authors/?q=ai:kome.sure"Köme, Cahit"https://zbmath.org/authors/?q=ai:kome.cahitSummary: This study provides a broad overview of the generalization of the various quaternions, especially in the context of its enhancing importance in the disciplines of mathematics and physics. By the help of bicomplex numbers, in this paper, we define the bicomplex generalized \(k-\)Horadam quaternions. Fundamental properties and mathematical preliminaries of these quaternions are outlined. Finally, we give some basic conjucation identities, generating function, the Binet formula, summation formula, matrix representation and a generalized identity, which is generalization of the well-known identities such as Catalan's identity, Cassini's identity and d'Ocagne's identity, of the bicomplex generalized \(k-\)Horadam quaternions in detail.Several in-place identities for the part of size 1 of integer compositions.https://zbmath.org/1449.050222021-01-08T12:24:00+00:00"Guo, Yuhong"https://zbmath.org/authors/?q=ai:guo.yuhong"Ma, Lei"https://zbmath.org/authors/?q=ai:ma.leiSummary: In this paper, we study identities related to the part 1 for compositions of positive integers using the combinatorial proof method. We first present an identity for the number of compositions when the part 1 can be of two kinds. Then we obtain several new in-place identities for the numbers of 1--2 compositions and palindromic compositions.Vertex-distinguishing I-total coloring and VI-total coloring of \(m{C_3} \vee n{C_3}\) and \(m{C_4} \vee n{C_4}\).https://zbmath.org/1449.050922021-01-08T12:24:00+00:00"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangen"Zhang, Shenggui"https://zbmath.org/authors/?q=ai:zhang.shengguiSummary: Let \(G\) be a simple graph. Suppose that \(f\) is a general total coloring of graph \(G\) (i.e., an assignment of several colors to all vertices and edges of \(G\)), if any two adjacent vertices and any two adjacent edges of graph \(G\) are assigned different colors, then \(f\) is called an I-total coloring of a graph \(G\); if any two adjacent edges of \(G\) are assigned different colors, then \(f\) is called a VI-total coloring of a graph \(G\). Let \(C (x)\) denote the set of colors of vertex \(x\) and of the edges incident with \(x\) under \(f\), the set is non multiple set. For an I-total coloring (resp., VI-total coloring) \(f\) of a graph \(G\), if \(C (u)\ne C (v)\) for any two distinct vertices \(u\) and \(v\) of \(V (G)\), then \(f\) is called a vertex-distinguishing I-total coloring (resp., vertex-distinguishing VI-total coloring) of graph \(G\), short for VDIT coloring (resp., VDVIT coloring). Let \(\chi_{\mathrm{vt}}^{\mathrm{I}} (G) = \min\{k|G\text{ has a }k\text{-VDIT coloring}\}\), then \(\chi_{\mathrm{vt}}^{\mathrm{I}} (G)\) is called the VDIT chromatic number of graph \(G\). Let \(\chi_{\mathrm{vt}}^{\mathrm{VI}} (G) = \min\{k|G\text{ has a }k\text{-VDVIT coloring}\}\), then \(\chi_{\mathrm{vt}}^{\mathrm{VI}} (G)\) is called the VDVIT chromatic number of graph \(G\). The VDIT coloring (resp., VDVIT coloring) of \(m{C_3} \vee n{C_3}\) and \(m{C_4} \vee n{C_4}\) are determined and the VDIT chromatic number (resp., VDVIT chromatic number) of them is determined by constructing concrete coloring.Enciphering on the basis of the sums with products of weight and free components as summands.https://zbmath.org/1449.680352021-01-08T12:24:00+00:00"Nikonov, Aleksandr Ivanovich"https://zbmath.org/authors/?q=ai:nikonov.aleksandr-ivanovichSummary: The purpose of the given paper is reviewing of mathematical resources of enciphering of the source text, allowing to ensure the simplicity of appropriate decryption; the source text is a sequence of integer weight coefficients. The composer of the cipher checks how the condition of separability of these coefficients is satisfied. The selection rule provides usage of operations of the lower or upper roundoff. The generated cipher is represented by the values of the finite sums.The Erdös-Ko-Rado theorem for finite affine symplectic space.https://zbmath.org/1449.052372021-01-08T12:24:00+00:00"Hao, Shanshan"https://zbmath.org/authors/?q=ai:hao.shanshan"Cai, Bingling"https://zbmath.org/authors/?q=ai:cai.bingling"Kang, Na"https://zbmath.org/authors/?q=ai:kang.naSummary: In this paper, we determine the maximum size of the 0-intersecting family and the 1-intersecting family in finite affine-symplectic space and describe the structures of these intersecting families which reach the upper bounds. We then obtain the Erdös-Ko-Rado theorem of these intersecting families in the finite affine-symplectic space.Extremal unicyclic graphs with respect to permanent sum.https://zbmath.org/1449.051472021-01-08T12:24:00+00:00"Chen, Lan"https://zbmath.org/authors/?q=ai:chen.lan"Wu, Tingzeng"https://zbmath.org/authors/?q=ai:wu.tingzengSummary: Let \(G\) be a graph with \(n\) vertices, and \(A (G)\) be an adjacency matrix of a graph \(G\). Then the polynomial \(\pi (G, x) = \operatorname{per}(xI - A (G))\) is called the permanent polynomial of \(G\), where \(I\) is the unit matrix of order \(n\). The permanent sum of \(G\) is the sum of the absolute values of the coefficients of \(\pi (G, x)\). The unicyclic graphs having \(i\)-th minimal permanent sum are determined, where \(i = 3, 4, 5, 6, 7\).Some applications of graph theory in networks research.https://zbmath.org/1449.052342021-01-08T12:24:00+00:00"Yao, Bing"https://zbmath.org/authors/?q=ai:yao.bingSummary: Topological graph belongs to graph theory, a branch of mathematics. In this paper, the theory and technique of graph theory are applied in networks research, but only for networks description. This paper focuses on new concepts such as graph network and graph matching network, scale-free graph definition, definition of ``internet of things'', new cumulative distributions, and splitting connectivity in artificial intelligence. The review emphasis is placed on the construction of high-quality networks and special properties of networks, the establishment of new algorithms such as spanning tree count, dominating set, dominating graph, and collapse degree; the applications of dynamic partial differential equations, probability, graph theory and other mathematical techniques in network research are highlighted.On the join graphs with crossing number two.https://zbmath.org/1449.050812021-01-08T12:24:00+00:00"Wang, Jing"https://zbmath.org/authors/?q=ai:wang.jing.3"Zhang, Zuozheng"https://zbmath.org/authors/?q=ai:zhang.zuozheng"Huang, Yuanqiu"https://zbmath.org/authors/?q=ai:huang.yuanqiuSummary: Determining the crossing number of a given graph is NP-complete. It is well known that Kuratowski's theorem characterizes the graph whose crossing number is 0. For nonplanar graph \(G\) with crossing number \(k\) \((k \ge 1)\), there are few results concerning on characterizing the structure of \(G\). We characterized graphs \({G_1}\) and \({G_2}\) for which the crossing number of their join \({G_1} \vee {G_2}\) is one. To further study, this paper is devoted to characterize graphs \({G_1}\) and \({G_2}\) satisfying \({\mathrm{cr}} ({G_1} \vee {G_2}) = 2\) when \(\Delta ({G_2}) \ne 3\).Community detection algorithm based on asymmetric transition probability of nodes.https://zbmath.org/1449.910902021-01-08T12:24:00+00:00"Xu, Pinghua"https://zbmath.org/authors/?q=ai:xu.pinghua"Hu, Wenbin"https://zbmath.org/authors/?q=ai:hu.wenbin"Qiu, Zhenyu"https://zbmath.org/authors/?q=ai:qiu.zhenyu"Nie, Cong"https://zbmath.org/authors/?q=ai:nie.cong"Tang, Chuanhui"https://zbmath.org/authors/?q=ai:tang.chuanhui"Gao, Kuang"https://zbmath.org/authors/?q=ai:gao.kuang"Liu, Zhongzhou"https://zbmath.org/authors/?q=ai:liu.zhongzhouSummary: Community detection is a popular and difficult problem in the field of social network analysis. Most of the current researches mainly focus on optimizing the modularity index, evaluating the similarity of nodes, and designing different models to fit particular networks. These approaches usually suffer from following problems: (1) just a few of them can deal with directed networks as well as undirected networks; and (2) real-world networks are more complex than synthetic networks, many community detection strategies cannot perform well in real-world networks. To solve these problems, this paper presents an algorithm for community detection in complex networks based on random walk method. Different from existing methods based on random walk method, the asymmetric transition probability is designed for the nodes according to network topology and other information. The event propagation law is also applied to the evaluation of nodes importance. A large number of simulation experiments show that the proposed algorithm performs well on both real-world networks and synthetic networks.On the spectral moment of quasi-unicyclic graphs.https://zbmath.org/1449.051762021-01-08T12:24:00+00:00"Wu, Yaping"https://zbmath.org/authors/?q=ai:wu.yaping"Guo, Huiyi"https://zbmath.org/authors/?q=ai:guo.huiyi"Yuan, Shuai"https://zbmath.org/authors/?q=ai:yuan.shuaiSummary: A connected graph \(G = (V (G), E (G))\) is called a quasi-unicyclic graph if there exists \({u_0} \in V (G)\) such that \(G-{u_0}\) is a unicyclic graph. Denote \(Q (n,{d_0}) = \{{G:G}\) is a quasi-unicyclic graph of order \(n\) with \(G-{u_0}\) being a unicyclic graph and \({d_G} ({u_0}) = {d_0}\}\). Let \(A (G)\) be the adjacency matrix of a graph \(G\), and let \({\lambda_1} (G), {\lambda_2} (G), \dots, {\lambda_n} (G)\) be the eigenvalues in non-increasing order of \(A (G)\). The number \(\sum\limits_{i=1}^n {\lambda_i^k} (G)\) \((k = 0,1,\dots, n-1)\) is called the \(k\)-th spectral moment of \(G\), denoted by \({S_k} (G)\). Let \(S (G) = ({S_0} (G), {S_1} (G), \dots, {S_{n-1}} (G))\) be the sequence of spectral moments of \(G\). For two graphs \({G_1}, {G_2}\), we have \({G_1}{\prec_S}{G_2}\) if for some \(k\) \((k = 1,2,\dots, n -1)\), and we have \({S_i} ({G_1}) = {S_i} ({G_2})\) \( (i = 0,1,\dots, k-1)\) and \({S_k} ({G_1}) < {S_k} ({G_2})\). In this paper, we determine the second to the fourth largest quasi-unicyclic graphs, in an \(S\)-order and in the set \(Q (n, {d_0})\), respectively.A characterization of the position value for hypernetwork situations.https://zbmath.org/1449.051862021-01-08T12:24:00+00:00"Li, Siwen"https://zbmath.org/authors/?q=ai:li.siwen"Zhao, Jiagui"https://zbmath.org/authors/?q=ai:zhao.jiagui"Shan, Erfang"https://zbmath.org/authors/?q=ai:shan.erfangSummary: In graph games, there was a model which assumed that only the connected coalitions can fully achieve the worth, but the structures of the coalitions are ignored. In 1996, other researchers generalized the model to ``network situation''. The characteristic function was replaced by the value function to reflect the influence of the structures on benefits of feasible coalitions. In this paper we consider hypernetwork situation, which is a natural extension of network situation. It consists of a triple \( (N, H, v)\) where \( (N, H)\) is a hypernetwork and \(v\) is the value function to describe the possible gains from TU-games, whose cooperation is restricted by a hypernetwork. In 2012, the position value was characterized axiomatically for network situations by using four axioms. By introducing a new axiom, called partial balanced conference contributions, and combining component efficiency, we propose an axiomatic characterization of the position value for hypernetwork situations. As an immediate corollary, we give a new characterization of the position value for network situations.The connectivity and diagnosability of interconnection networks.https://zbmath.org/1449.051592021-01-08T12:24:00+00:00"Wang, Shiying"https://zbmath.org/authors/?q=ai:wang.shiyingSummary: Connectivity and diagnosability are fundamental considerations when designing an interconnected network. Our research in this area has achieved a series of results. In this article, we highlight some of the important articles published in recent years.An integrated causal path identification method.https://zbmath.org/1449.621262021-01-08T12:24:00+00:00"Fei, Nina"https://zbmath.org/authors/?q=ai:fei.nina"Yang, Youlong"https://zbmath.org/authors/?q=ai:yang.youlongSummary: Finding causality merely from observed data is a fundamental problem in science. The most basic form of this causal problem is to determine whether \(X\) leads to \(Y\) or \(Y\) leads to \(X\) in the case of joint observation of two variables \(X, Y\). In statistics, path analysis is used to describe the direct dependence between a set of variables. But in fact, we usually do not know the causal order between variables. However, ignoring the direction of the causal path will prevent researchers from analyzing or using causal models. In this study, we propose a method for estimating causality based on observed data. First, observed variables are cleaned and valid variables are retained. Then, a direct linear non-Gaussian acyclic graph models (DirectLiNGAM) estimates the causal order \(K\) between variables. The third step is to estimate the adjacency matrix \(\boldsymbol{B}\) of the causal relationship based on \(K\). Next, since \(\boldsymbol{B}\) is not convenient for model interpretation, we use adaptive lasso to prune the causal path and variables. Further, a causal path graph and a recursive model are established. Finally, we test and debug the recursive model, obtain a causal model with good fit, and estimate the direct, indirect and total effects between causal variables. This paper overcomes the randomness assigning causal order to variables. This study is different from the researcher's understanding of his own model by generating some form of simulation data. The simplest and relatively unsmooth statistical learning method used in this study has obvious advantages in the field of interpretable machine learning.Saturation number for linear forest \(2{P_3} \bigcup t{P_2}\).https://zbmath.org/1449.050492021-01-08T12:24:00+00:00"Liu, Min"https://zbmath.org/authors/?q=ai:liu.min"Hu, Zhiquan"https://zbmath.org/authors/?q=ai:hu.zhiquanSummary: For a fixed graph \(F\), a graph \(G\) is \(F\)-saturated if it has no \(F\) as a subgraph, but does contain \(F\) after the addition of any new edge. The saturation number, sat\(\left({n, F} \right)\), is the minimum number of edges of a graph in the set of all \(F\)-saturated graphs with order \(n\). In this paper, we determine the saturation number sat\(\left({n, 2{P_3} \bigcup t{P_2}} \right)\) and characterize the extremal graphs for \(n \ge 6t + 8\).Application of discharging method in graph colorings theory.https://zbmath.org/1449.051062021-01-08T12:24:00+00:00"Liu, Jingzhao"https://zbmath.org/authors/?q=ai:liu.jingzhaoSummary: Graph theory is one of the important branches of mathematics, which is rich in content and widely used. The rapid development of its research directly promotes the development of mathematics field. On the basis of introducing the development of graph coloring theory, the application of the discharging method is discussed in graph colorings theory mainly.A highly efficient algorithm for maximum cut on Halin graphs.https://zbmath.org/1449.052332021-01-08T12:24:00+00:00"Xu, Li"https://zbmath.org/authors/?q=ai:xu.li"Lou, Dingjun"https://zbmath.org/authors/?q=ai:lou.dingjun"Jiang, Yifan"https://zbmath.org/authors/?q=ai:jiang.yifan"Qin, Zongrong"https://zbmath.org/authors/?q=ai:qin.zongrongSummary: Given a graph \(G = (V, E)\) with each edge having a positive integer weight, and a positive integer \(k\), can \(V\) be partitioned into two disjoint subsets \({V_1}\) and \({V_2}\) so that the sum of weights of the edges with one end in \({V_1}\) and another end in \({V_2}\) is at least \(k\)? This problem is called the maximum cut problem, which is an NPC problem. When the weight of each edge of \(G\) is 1, it is still an NPC problem. A highly efficient algorithm is designed to solve the maximum cut problem with the weight of each edge to be 1 in Halin graphs. The time complexity of the algorithm is \(O (n)\), where \(n = |V (G)|\).The number of ordered splits where the components of a positive integer \(n\) are not less than 2.https://zbmath.org/1449.050252021-01-08T12:24:00+00:00"Tang, Baoxiang"https://zbmath.org/authors/?q=ai:tang.baoxiang"Ren, Han"https://zbmath.org/authors/?q=ai:ren.hanSummary:Depiction technology of super corona distance matrix spectrum.https://zbmath.org/1449.150272021-01-08T12:24:00+00:00"Xu, Xiaojing"https://zbmath.org/authors/?q=ai:xu.xiaojing"Wang, Peiwen"https://zbmath.org/authors/?q=ai:wang.peiwen"Wang, Zhiping"https://zbmath.org/authors/?q=ai:wang.zhipingSummary: The topological structure of the graph has important significance in chemical molecular structure, and the various matrices of the graph contain the topology information of the graph. In this paper, we depict the distance spectra of four kinds of double corona according to the definition of distance spectrum and the structure characteristics of four types of graphs. The corresponding distance matrix is obtained by mathematical induction. On the basic of them, the block matrix is constructed, which is a super corona distance matrix. By using the uniqueness of the matrix eigenvalues, the eigenvalues and eigenvectors of the super corona distance matrix are solved, and the accuracy and reliability of the conclusion are verified simultaneously. Finally, we research the distance spectra of \(G^{ (S)} \circ \{{G_1}, {G_2}\}\), \(G^{ (Q)} \circ \{{G_1}, {G_2}\}\), \(G^{ (R)} \circ \{{G_1}, {G_2}\}\), \(G^{ (T)} \circ \{{G_1}, {G_2}\}\), when \(G\) is a complete graph and \({G_1}, {G_2}\) are regular graphs.The update exposition of the components organising the sum of weighted equal powers.https://zbmath.org/1449.050112021-01-08T12:24:00+00:00"Nikonov, Aleksandr Ivanovich"https://zbmath.org/authors/?q=ai:nikonov.aleksandr-ivanovichSummary: The sum of the weighted equal powers with natural bases and parameters is organized of components, which are independent or dependent on weight coefficients. Modification of components of the first aspect uses explicitly expressed products of binomial coefficients, and modification of components of the second aspect -- products of binomial and weight coefficients. These visible expressions expand possibilities of representation of structure and an order of shaping of the considered sums.The neighbor expanded sum distinguishing total colorings of three types of join graphs of wheel and fan.https://zbmath.org/1449.051162021-01-08T12:24:00+00:00"Zhang, Hui"https://zbmath.org/authors/?q=ai:zhang.hui.9|zhang.hui|zhang.hui.8|zhang.hui.6|zhang.hui.2|zhang.hui.10|zhang.hui.3|zhang.hui.1|zhang.hui.7|zhang.hui.11|zhang.hui.5|zhang.hui.4"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangen"Wang, Zhiwen"https://zbmath.org/authors/?q=ai:wang.zhiwenSummary: The neighbor expanded sum distinguishing total coloring of join of two wheels is discussed and its neighbor expanded sum distinguishing total coloring index is determined. Then the neighbor expanded sum distinguishing total colorings and the neighbor expanded sum distinguishing total coloring indexes of joins of one fan and one wheel, and two fans are obtained respectively by the method of deleting edges.Four new operations related to composition and their hyper-Zagreb index.https://zbmath.org/1449.050642021-01-08T12:24:00+00:00"Pattabiraman, K."https://zbmath.org/authors/?q=ai:pattabiraman.karthik|pattabiraman.kannanSummary: For a (molecular) graph, the hyper Zagreb index is defined as \(HM (G) = \sum_{uv \in E (G)} ({d_G} (u) + {d_G} (v))^2\). \textit{D. Sarala} et al. [Appl. Math. Comput. 309, 156--169 (2017; Zbl 1411.05230)] introduced four new operations (\(F\)-product) of graphs. In this paper, we study the hyper-Zagreb index for the \(F\)-product of some special well-known graphs such as subdivision and total graph.Acyclic improper list coloring of graphs.https://zbmath.org/1449.051022021-01-08T12:24:00+00:00"Li, Chunmiao"https://zbmath.org/authors/?q=ai:li.chunmiao"Chen, Min"https://zbmath.org/authors/?q=ai:chen.min.2|chen.min.3|chen.min.1|chen.minSummary: In this paper we investigated the acyclic improper list coloring problem which has been a difficult coloring problem so far. By analyzing the structure properties of the minimum counterexample \(G\), together with coloring extension and coloring permutation, it was proved that every non-4-regular graph with maximum degree 4 was acyclically \( (3,3)^\ast\)-choosable. The obtained result generalized several relevant results of this topic.A remark on a theorem of Erdős.https://zbmath.org/1449.051902021-01-08T12:24:00+00:00"Schmerl, J. H."https://zbmath.org/authors/?q=ai:schmerl.james-hSummary: A theorem of Erdős asserts that every infinite \(X\subseteq \mathbb{R}^n\) has a subset of the same cardinality having no repeated distances. This theorem is generalized here as follows: If \((\mathbb{R}^n,E)\) is an algebraic hypergraph that does not have an infinite, complete subset, then every infinite subset has an independent subset of the same cardinality.A note on chromatic blending of colour clusters.https://zbmath.org/1449.051012021-01-08T12:24:00+00:00"Kok, Johan"https://zbmath.org/authors/?q=ai:kok.johan"Sudev, N. K."https://zbmath.org/authors/?q=ai:naduvath.sudev"Jamil, Muhammad Kamran"https://zbmath.org/authors/?q=ai:jamil.muhammad-kamranSummary: For a colour cluster \(\mathbb{C} = ({{\mathcal{C}_1}, {\mathcal{C}_2}, {\mathcal{C}_3}, \ldots, {\mathcal{C}_\ell}})\), \({\mathcal{C}_i}\) is a colour class, and \(|{\mathcal{C}_i}| = {r_i} \ge 1\). We investigate a simple connected graph structure \({G^\mathbb{C}}\), which represents a graphical embodiment of the colour cluster such that the chromatic number \(\chi ({G^\mathbb{C}}) = \ell \), and the number of edges is a maximum, denoted by \({\varepsilon^+} ({G^\mathbb{C}})\). We also extend the study by inducing new colour clusters recursively by blending the colours of all pairs of adjacent vertices. Recursion repeats until a maximal homogeneous blend between all \(\ell \) colours is obtained. This is called total chromatic blending. Total chromatic blending models for example, total genetic, chemical, cultural or social orderliness integration.Note on \(p\)-competition graphs of loopless Hamiltonian digraphs without symmetric arcs.https://zbmath.org/1449.051882021-01-08T12:24:00+00:00"Kidokoro, Y."https://zbmath.org/authors/?q=ai:kidokoro.yasuhisa"Ogawa, K."https://zbmath.org/authors/?q=ai:ogawa.kenjiro"Tagusari, S."https://zbmath.org/authors/?q=ai:tagusari.satoshi"Tsuchiya, M."https://zbmath.org/authors/?q=ai:tsuchiya.morimasaSummary: 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 distinct \(p\) vertices \({v_1}, {v_2},\dots, {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, \dots, p\). In this paper, we obtain that a path is a \(p\)-competition graph of a loopless Hamiltonian digraph without symmetric arcs. We also show that a wheel \({W_n}\) is a \(p\)-competition graph of a loopless Hamiltonian digraph without symmetric arcs.Mathematical aspect of the combinatorial game ``Mahjong''.https://zbmath.org/1449.050152021-01-08T12:24:00+00:00"Cheng, Yuan"https://zbmath.org/authors/?q=ai:cheng.yuan"Li, Chikwong"https://zbmath.org/authors/?q=ai:li.chi-kwong"Li, Sharon H."https://zbmath.org/authors/?q=ai:li.sharon-hSummary: We illustrate how one can use basic combinatorial theory and computer programming technique (Python) to analyze the combinatorial game: Mahjong. The results confirm some folklore concerning the game, and expose some unexpected results. Related results and possible future research in connection to artificial intelligence are mentioned. Readers interested in the subject may further develop the techniques to deepen the study of the game, or study other combinatorial games.On realizability of graphs as \({\Gamma_S} (L)\) for some lattice \(L\).https://zbmath.org/1449.050792021-01-08T12:24:00+00:00"Malekpour, Shahide"https://zbmath.org/authors/?q=ai:malekpour.shahide"Bazigaran, Behnam"https://zbmath.org/authors/?q=ai:bazigaran.behnamSummary: Let \({\Gamma_S} (L)\) denote the graph associated to the lattice \(L\) with respect to a \(\wedge\)-closed subset \(S\) of \(L\). In this paper, some properties of the graph \({\Gamma_S} (L)\) are presented. Also, we investigate the realizability of \({\Gamma_S} (L)\) for some graphs, especially some split graphs.The automorphism groups of the involution \(G\)-graph and Cayley graph.https://zbmath.org/1449.051302021-01-08T12:24:00+00:00"Ashrafi, A. R."https://zbmath.org/authors/?q=ai:ashrafi.ali-reza"Bretto, A."https://zbmath.org/authors/?q=ai:bretto.alain"Gholaminezhad, F."https://zbmath.org/authors/?q=ai:gholaminezhad.farzanehSummary: Let \(G\) be a finite group and \(\Phi (G, S)\) be the \(G\)-graph of a group \(G\) with respect to a non-empty subset \(S\). The aim of this paper is to study the structure and the automorphism group of a simple form of \(G\)-graphs for some finite groups like alternating groups, dihedral, semi-dihedral, dicyclic, and \({\mathbb{Z}_m}\rtimes_\delta{\mathbb{Z}_{2n}}\) groups, where \(\delta\) is an inverse mapping and \({V_{8n}} = \{a,b|{a^{2n}} = {b^4} = 1, aba = b^{-1}, ab^{-1}a = b\}\). Then we compare it with the automorphism group of the corresponding Cayley graph. Also we study the structure of involution \(G\)-graphs when \(S = Inv\) is the set of all involutions of \(G\).A study on integer additive set-graceful graphs.https://zbmath.org/1449.052292021-01-08T12:24:00+00:00"Sudev, N. K."https://zbmath.org/authors/?q=ai:naduvath.sudev"Germina, K. A."https://zbmath.org/authors/?q=ai:germina.k-aSummary: A set-labeling of a graph \(G\) is an injective set-valued function \(f:V (G) \to \mathcal{P} (X)\), where \(X\) is a finite set and \(\mathcal{P} (X)\) is its power set. A set-indexer of \(G\) is a set-labeling such that the induced function \({f^\oplus}:E (G) \to \mathcal{P} (X)-\{\emptyset\}\) defined by \({f^\oplus} (uv) = f (u)\oplus f (v)\) for every \(uv \in E (G)\) is also injective. Let \(G\) be a graph and let \(X\) be a non-empty set. A set-indexer \(f:V (G) \to \mathcal{P} (X)\) is called a set-graceful labeling of \(G\) if \({f^\oplus} (E (G)) = \mathcal{P} (X)-\{\emptyset\}\). A graph \(G\) which admits a set-graceful labeling is called a set-graceful graph. An integer additive set-labeling is an injective function \(f:V (G) \to \mathcal{P} ({\mathbb{N}_0})\), \({\mathbb{N}_0}\) is the set of all non-negative integers and an integer additive set-indexer is an integer additive set-labeling such that the induced function \({f^+}:E (G) \to \mathcal{P} ({\mathbb{N}_0})\) defined by \({f^+} (uv) = f (u) + f (v)\) is also injective. In this paper, we introduce the notion of integer additive set-graceful labeling of graphs analogous to the set-graceful labeling of graphs and study certain properties and characteristics of the graphs which satisfy this type of set-labeling.A generalization of power graphs of commutative rings.https://zbmath.org/1449.051322021-01-08T12:24:00+00:00"Fatehi, M."https://zbmath.org/authors/?q=ai:fatehi.mahsa"Khashyarmanesh, K."https://zbmath.org/authors/?q=ai:khashyarmanesh.kazem"Afkhami, M."https://zbmath.org/authors/?q=ai:afkhami.mojganSummary: Let \(R\) be a commutative ring with non-zero identity. For a natural number \(n\), we associate a directed graph, denoted by \(\mathcal{P}_R^n\), with \({R^n}\backslash \{0\}\) as the vertex set and, for two distinct vertices \(X = ({x_1}, {x_2}, \dots, {x_n})\) and \(Y = ({y_1}, {y_2}, \dots, {y_n})\), we have an arc \(X \to Y\) in \(\mathcal{P}_R^n\) if and only if there exists an \(n \times n\) lower triangular matrix \(A = (a_{i_j})\) over \(R\) such that \(A{X^T} = {Y^T}\) and \({\mathrm{det}} (A) \in [{x_1}, {x_2}, \dots, {x_n}]\), where \([{x_1}, {x_2}, \dots, {x_n}]\) is a subsemigroup generated by the elements \({x_1}, {x_2}, \dots, {x_n}\) in the multiplicative semigroup \(R\). When we consider the ring \(R\) as a semigroup with respect to multiplication, the graph \(\mathcal{P}_R^1\) is the usual directed power graph (over a semigroup). Hence \(\mathcal{P}_R^n\) is a generalization of power graphs. In this paper we study some basic properties of \(\mathcal{P}_R^n\). Also we study the planarity, outer planarity and ring graph of \(\mathcal{P}_R^n\) and we determine the cases for which the graph \(\mathcal{P}_R^n\) has thickness 2.On bounded deviated permutations and their leading statistics.https://zbmath.org/1449.050052021-01-08T12:24:00+00:00"Chien, Weiliang"https://zbmath.org/authors/?q=ai:chien.weiliang"Lin, Yen-chi Roger"https://zbmath.org/authors/?q=ai:lin.yen-chi-rogerSummary: This article investigates the distribution of the initial number in the bounded deviated permutations \(\mathfrak{S}_{n+1}^{\ell, r}\), assuming the uniform distribution in \(\mathfrak{S}_{n+1}^{\ell, r}\). We define the random variable \({X_n} (\pi) = {\pi_1} - 1\) for a bounded deviated permutation \(\pi = {\pi_1}{\pi_2} \cdots {\pi_{n + 1}} \in \mathfrak{S}_{n+1}^{\ell, r}\), and the formulas for the expected value and the standard deviation for \({X_n}\) are derived. The method is then applied to three specific cases, namely \(\mathfrak{S}_{n+1}^{1, 2}\), \(\mathfrak{S}_{n+1}^{1, 3}\), and \(\mathfrak{S}_{n+1}^{2, 2}\). The Hayman method is needed to get the asymptotic forms for these expected values and the standard deviations. In each example, plots about the real data and the expected shape are drawn against each other for comparison.Involutory Latin quandles of order \(pq\).https://zbmath.org/1449.200662021-01-08T12:24:00+00:00"Jedlička, Přemysl"https://zbmath.org/authors/?q=ai:jedlicka.premyslSummary: We present a construction of a family of involutory latin quandles, a family that contains all non-Alexander involutory latin quandles of order \(pq\), for \(p < q\) odd primes. Such quandles exist if and only if \(p\) divides \(q^2-1\).Powers of the Catalan generating function and Lagrange's 1770 trinomial equation series.https://zbmath.org/1449.050172021-01-08T12:24:00+00:00"Gould, H. W."https://zbmath.org/authors/?q=ai:gould.henry-wadsworthSummary: The Catalan numbers \(1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \dots\) are given by \(C (n)=\frac{1}{n+1}\binom{2n}{n}\) for \(n\geq 0\). They are named for Eugene Catalan who studied them as early as 1838. They were also found by Leonhard Euler (1758), Nicholas von Fuss (1795), and Andreas von Segner (1758). The Catalan numbers have the binomial generating function \[C (z)= \sum\limits_{n=0}^\infty C (n)z^n = \frac{1-\sqrt{1-4z}}{2z}.\] It is known that powers of the generating function \(C (z)\) are given by \[C^a (z)= \sum\limits_{n=0}^\infty\frac{a}{a+2n}\binom{a+2n}{n}z^n.\] The above formula is not as widely known as it should be. We observe that it is an immediate, simple consequence of expansions first studied by J. L. Lagrange. Such series were used later by Heinrich August Rothe in 1793 to find remarkable generalizations of the Vandermonde convolution. For the equation \(x^3 - 3x + 1 =0\), the numbers \(\frac{1}{2k+1}\binom{3k}{k}\) analogous to Catalan numbers occur of course. Here we discuss the history of these expansions and formulas due to L. C. Hsu and the author.Some properties of a class of refined Eulerian polynomials.https://zbmath.org/1449.110402021-01-08T12:24:00+00:00"Sun, Yidong"https://zbmath.org/authors/?q=ai:sun.yidong"Zhai, Liting"https://zbmath.org/authors/?q=ai:zhai.litingSummary: Recently, a new kind of refined Eulerian polynomials was defined, namely, \[A_n (p,q)=\sum\limits_{\pi\in \mathfrak{S}_n}p^{{\mathrm odes} (\pi)}q^{{\mathrm edes} (\pi)}\] for \(n\geq 1\), where \(\mathfrak{S}_n\) is the set of all permutations on \(\{1, 2, \cdots, n\}\), odes \( (\pi)\) and edes \( (\pi)\) enumerate the number of descents of permutation \(\pi\) in odd and even positions, respectively. In this paper, we obtain an exponential generating function for \(A_n (p,q)\) and give an explicit formula for \(A_n (p,q)\) in terms of Eulerian polynomials \(A_n (q)\) and \(C (q)\), the generating function for Catalan numbers. In certain cases, we establish a connection between \(A_n (p,q)\) and \(A_n (p,0)\) or \(A_n (0,q)\), and express the coefficients of \(A_n (0,q)\) by Eulerian numbers \(A_{n,k}\). Consequently, this connection discovers a new relation between Euler numbers \(E_n\) and Eulerian numbers \(A_{n,k}\).Edge partition of graphs embeddable in the projective plane and the Klein bottle.https://zbmath.org/1449.050822021-01-08T12:24:00+00:00"Zha, Xiaoya"https://zbmath.org/authors/?q=ai:zha.xiaoyaSummary: In [\textit{B. Xu} and \textit{X. Zha}, Discrete Math. 341, No. 6, 1688--1695 (2018; Zbl 1384.05075)] we show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This edge partition then implies some results in thickness and outerthickness of toroidal graphs. In particular, if each planar graph has outerthickness at most 2, then the outerthickness of toroidal graphs is at most 3 which is the best possible due to \(K_7\). In this paper we continue to study the edge partition for projective planar graphs and Klein bottle embeddable graphs. We show that (1) every non-planar but projective planar graph can be edge partitioned into a planar graph and a union of caterpillar trees; and (2) every non-planar Klein bottle embeddable graph can be edge partitioned into a planar graph and a subgraph of two vertex amalgamation of a caterpillar tree with a cycle with pendant edges. As consequences, the thickness of projective planar graphs and Klein bottle embeddabe graphs are at most 2, which are the best possible, and the outerthickness of these graphs are at most 3.Vertex-distinguishing E-total coloring of complete bipartite graph \({K_{10,n}}\) with \( 91 \le n \le 214\).https://zbmath.org/1449.050912021-01-08T12:24:00+00:00"Chen, Xiang'en"https://zbmath.org/authors/?q=ai:chen.xiangen"Bao, Liya"https://zbmath.org/authors/?q=ai:bao.liyaSummary: Let \(\chi_{vt}^e (G) = \min\{{k\mid G\; {\mathrm{has\; a}}\; k\text{-VDET coloring}}\}\), then \(\chi_{vt}^e (G)\) is called the VDET chromatic number of \(G\). By using the analytical method and proof via contradiction, the VDET coloring of complete bipartite graph \({K_{10,n}}\) was discussed and the VDET chromatic number of \({K_{10,n}}\) \((91 \le n \le 214)\) was obtained.Simplicial descriptions for digraphs and their path homology from the point of \(\Delta\)-sets.https://zbmath.org/1449.051242021-01-08T12:24:00+00:00"Wang, Chong"https://zbmath.org/authors/?q=ai:wang.chong|wang.chong.7|wang.chong.4|wang.chong.6"Ren, Shiquan"https://zbmath.org/authors/?q=ai:ren.shiquan|ren.shiquan.1Summary: In recent years, paths on digraphs were studied by many previous researchers, and the path homology was invented as an algebraic tool for the topology of digraphs. In this paper, we describe the sets of paths on digraphs as graded subsets of \(\Delta\)-sets. By generalizing the embedded homology of hypergraphs and defining the embedded homology of graded subsets of \(\Delta\)-sets, we prove that path homology of digraphs can be described as the embedded homology of graded subsets of \(\Delta\)-sets.On the Euler property of the strong product graphs.https://zbmath.org/1449.051642021-01-08T12:24:00+00:00"Yin, Haoran"https://zbmath.org/authors/?q=ai:yin.haoran"Li, Feng"https://zbmath.org/authors/?q=ai:li.feng.2|li.feng|li.feng.1Summary: Strong product is a method of constructing large-scale networks through some smaller networks. The large network constructed from this method contains small networks as its subnetworks, and retains many good properties of small networks, such as connectivity, embedability and so on. The topological structure of strong product graph is closely related to the topological structure of factor graph. The Euler problem of graphs is an important problem in graph theory, and has many applications in practice, such as the Chinese postman problem. In this paper, we study the Euler problem of strong product graphs, and obtain and prove the necessary and sufficient conditions for the existence of Euler tours and Euler entries for the strong product of two graphs.Descartes product of \( (d, r, k)\)-disjunct matrices.https://zbmath.org/1449.050372021-01-08T12:24:00+00:00"Wang, Shaoyu"https://zbmath.org/authors/?q=ai:wang.shaoyu"Wang, Shaoying"https://zbmath.org/authors/?q=ai:wang.shaoying"Zhao, Guanhua"https://zbmath.org/authors/?q=ai:zhao.guanhuaSummary: The \( (d, r, k)\)-disjunct matrix is an inhibitor model of combinatorial group testing theory. In this paper, we define the Descartes product of the known two \( (d, r, k)\)-disjunct matrices as a new \( (d, r, k)\)-disjunct matrix, and calculate its parameters.Descartes product of two binary superimposed \( (z,u)\)-codes.https://zbmath.org/1449.940822021-01-08T12:24:00+00:00"Guo, Xianchong"https://zbmath.org/authors/?q=ai:guo.xianchong"Wen, Xinmiao"https://zbmath.org/authors/?q=ai:wen.xinmiao"Zhao, Yanbing"https://zbmath.org/authors/?q=ai:zhao.yanbingSummary: \( (z, u)\)-code is an extremely important binary superimposed code in coding theory. Descartes product of the two known \( (z, u)\)-binary superimposed codes is defined as a new \( (z, u)\)-binary superimposed code and its parameters are calculated. At last, we introduce the properties of some error-detecting codes and error-correcting codes.A bi-average tree solution for probabilistic communication situations with fuzzy coalition.https://zbmath.org/1449.051872021-01-08T12:24:00+00:00"Li, Xianghui"https://zbmath.org/authors/?q=ai:li.xianghui"Sun, Hao"https://zbmath.org/authors/?q=ai:sun.hao"Hou, Dongshuang"https://zbmath.org/authors/?q=ai:hou.dongshuangSummary: A probabilistic communication structure considers the setting with communication restrictions in which each pair of players has a probability to communicate directly. In this paper, we consider a more general framework, called a probabilistic communication structure with fuzzy coalition, that allows any player to have a participation degree to cooperate within a coalition. A maximal product spanning tree, indicating a way of the greatest possibility to communicate among the players, is introduced, where the unique path from one player to another is optimal. We present a feasible procedure to find the maximal product spanning trees. Furthermore, for games under this model, a new solution concept in terms of the average tree solution is proposed and axiomatized by defining a restricted game in Choquet integral form.Moments of additive statistics with respect to the Ewens sampling formula.https://zbmath.org/1449.110912021-01-08T12:24:00+00:00"Manstavičius, Eugenijus"https://zbmath.org/authors/?q=ai:manstavicius.eugenijus"Stepas, Vytautas"https://zbmath.org/authors/?q=ai:stepas.vytautasSummary: The additive semigroup of vectors with non-negative integer coordinates endowed with the Ewens probability measure plays an important role as a probabilistic space for many statistical models. In the present paper, we obtain upper estimates of the power moments of additive statistics defined on the semigroup. The statistics are sums of dependent random variables; however, our results have the form of the Rosenthal and von Bahr-Esseen inequalities. The arguments perfected in probabilistic number theory are adopted in the proofs.A bound for the rank-one transient of inhomogeneous matrix products in special case.https://zbmath.org/1449.150642021-01-08T12:24:00+00:00"Kennedy-Cochran-Patrick, Arthur"https://zbmath.org/authors/?q=ai:kennedy-cochran-patrick.arthur"Sergeev, Sergeĭ"https://zbmath.org/authors/?q=ai:sergeev.sergei-alekseevich|sergeev.sergei-m|sergeev.sergei-n"Berežný, Štefan"https://zbmath.org/authors/?q=ai:berezny.stefanSummary: We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [\textit{L. Shue, B. D. O. Anderson}, and \textit{S. Dey}, ``On steady-state properties of certain max-plus products'', in: Proceedings of the 1998 American Control Conference, Philadelphia, Pensylvania, June 24-26,1998. Piscataway, NJ: IEEE. 1909--1913 (1998; \url{doi:10.1109/acc.1998.707354}]. We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.A binary superimposed \( (z,u)\)-code based on permutation matrix.https://zbmath.org/1449.940832021-01-08T12:24:00+00:00"Guo, Xianchong"https://zbmath.org/authors/?q=ai:guo.xianchong"Yang, Yanqing"https://zbmath.org/authors/?q=ai:yang.yanqing"Zhao, Yanbing"https://zbmath.org/authors/?q=ai:zhao.yanbingSummary: The incidence matrix of \( (z, u)\)-cover-free family is a binary superimposed \( (z, u)\)-code. Notions of \( (u + z)\) order \(u\)-permutation matrix were defined, and their constructions and properties and ratio of \( (z, u)\)-code were studied by the \( (u + z)\) order \(u\)-permutation matrix.Module-\(p\) edge magic graceful labelling on graphical passwords.https://zbmath.org/1449.052302021-01-08T12:24:00+00:00"Zhang, Xiaohui"https://zbmath.org/authors/?q=ai:zhang.xiaohui.2"Sun, Hui"https://zbmath.org/authors/?q=ai:sun.hui"Yao, Bing"https://zbmath.org/authors/?q=ai:yao.bingSummary: We considered that each vertex of the ring \({C_n}\) of a super sun-graph \({G_s} ({C_n}, {a_i})\) is added with a path of length two, and the super sun-graph obtained is the characteristic of module-\(p\) edge magic graceful graph. The results show that the super sun-graph constructed with \(n\) trees and joint \({T_i}\) (\(i \in [1, n]\)) with \({n - 1}\) edges is a module-\(p\) edge magic graceful graph.Geometry of permutation limits.https://zbmath.org/1449.600102021-01-08T12:24:00+00:00"Rahman, Mustazee"https://zbmath.org/authors/?q=ai:rahman.mustazee"Virág, Bálint"https://zbmath.org/authors/?q=ai:virag.balint"Vizer, Máté"https://zbmath.org/authors/?q=ai:vizer.mateThis article concerns permutons (a measure on a square with uniform marginal distributions) and permuton processes (a process \(X\) with continuous sample paths such that each \(X(t)\) is uniformly distributed on some fixed interval). In the graph of the symmetric group \(\mathfrak{S}_n\), a \textit{sorting network} is a geodesic from the permutation \((1 2 3 \dots n)\) to \((n (n - 1) (n - 2) \dots 1)\). This article is a hopeful step towards resolving the Archimedean path conjecture of \textit{O. Angel} et al. [Adv. Math. 215, No. 2, 839--868 (2007; Zbl 1132.60008)], which states that as \(n \to \infty\), the random sorting network process on \(\mathfrak{S}_n\) converges in probability to the ``Archimedean process'' \[ \mathcal{A}(t) = \cos (\pi t) \mathbb{A}_x + \sin (\pi t) \mathbb{A}_y, t \in [0,1]\] for an appropriate random variable \((\mathbb{A}_x, \mathbb{A}_y)\) on the plane, defined in terms of an ``Archimedean measure''.
The primary results of this article are:
A process is a permuton process if and only if it is the limit of a sequence of permutation-valued processes.
Among permuton processes \(X(t)\), \(0 \leq t \leq 1\), on the square \([-1, 1]\), such that \(X(1) = - X(0)\), there is a unique process with minimal Dirichlet energy, and it is Archimedean.
Given a permuton-valued path from the identity permuton (of support \(\{ (x, x) : x \in [-1, 1] \}\)) to the reverse permuton (of support \(\{ (x, -x) : x \in [-1, 1] \}\)), the Dirichlet energy (via the Wasserstein metric) of the path is bounded below by the energy of the Archimedean path, that minimum achieved only by the Archimedean path.
However, there is a function of permutons which, if minimized by a nontrivial permuton, is minimized by at least four distinct permutons.
There is a qualitative discussion in which it is asserted that second statement above and the results of \textit{M. Kotowski} [Limits of random permuton processes and large deviations of the interchange process. Toronto: University of Toronto (PhD Thesis) (2016)] together establish the Archimedean path conjecture for ``relaxed'' random sorting networks.
Reviewer: Gregory Loren McColm (Tampa)Tangle-tree duality: in graphs, matroids and beyond.https://zbmath.org/1449.051562021-01-08T12:24:00+00:00"Diestel, Reinhard"https://zbmath.org/authors/?q=ai:diestel.reinhard"Oum, Sang-Il"https://zbmath.org/authors/?q=ai:oum.sang-ilThe authors build upon a general width duality theorem in abstract separation systems with well-defined notions of cohesion and separation, which establishes duality between the existence of high cohesiveness at a local level and a global tree structure, and which they have proved recently by the authors [``Tangle-tree duality in abstract separation systems'', Preprint, \url{arXiv:1701.02509}]. In the present paper this theorem is applied to derive tangle-tree-type duality theorems for tree-width, path-width, tree-decompositions of small adhesion in graphs, for tree-width in matroids, and its application to data science is showcased through derivation of the duality theorem for the existence of clusters in large data sets. Its power is further demonstrated by obtaining the classical duality theorems for width parameters in graph minor theory (such as path-width, tree-width, branch-width and rank-width) as its corollaries.
Reviewer: Dragan Stevanović (Niš)Subgroup growth of virtually cyclic right-angled Coxeter groups and their free products.https://zbmath.org/1449.200362021-01-08T12:24:00+00:00"Baik, Hyungryul"https://zbmath.org/authors/?q=ai:baik.hyungryul"Petri, Bram"https://zbmath.org/authors/?q=ai:petri.bram"Raimbault, Jean"https://zbmath.org/authors/?q=ai:raimbault.jeanLet \(\Gamma\) be a finitely generated group, and \(n\) a positive integer, so that the number \(s_{n}(\Gamma)\) of subgroups of \(\Gamma\) of index \(n\) is finite. In [J. Lond. Math. Soc., II. Ser. 101, No. 2, 556--588 (2020; Zbl 07216611)], the authors studied the factorial growth rate of \(s_{n}(\Gamma)\) for right-angled Artin and Coxeter groups \(\Gamma\), that is, the limits \[\lim_{n \to \infty} \frac{\log(s_{n}(\Gamma))}{n \log(n)}.\] The goal of the paper under review is to treat in detail the subclass of virtually cyclic Coxeter groups and their free products. It turns out that one can obtain much finer estimates than it was possible in the general case, where the limits were determined explicitly for Artin groups, but not for all Coxeter groups.
Recall that, given a graph \(\mathcal{G}\) with vertex set \(V\) and edge set \(E\), the right-angled Coxeter group associated to it is \[\Gamma^{\mathrm{Cox}}({\mathcal{G}})=\langle\sigma_{v} : v \in V,\sigma_{v}^{2} = e, \; {\text{for}}\; v \in V,[\sigma_{v}, \sigma_{w}] = e, \; {\text{for}}\; \{ v, w \} \in E \rangle. \] In the proofs, an asymptotic formula for the number \(n_{n}(\Gamma)\) of permutation representations of degree \(n\) of a free product \(\Gamma\) of certain right-angled Coxeter groups plays a crucial role; this generalises the asymptotic formula implicit in \textit{S. Chowla} et al. [Can. J. Math. 3, 328--334 (1951; Zbl 0043.25904)]. This is based on the fact that the exponential generating function for the sequence of the \(h_{n}(\Gamma)\) converges.
Reviewer: Andrea Caranti (Trento)The two-point Fano and ideal binary clutters.https://zbmath.org/1449.050412021-01-08T12:24:00+00:00"Abdi, Ahmad"https://zbmath.org/authors/?q=ai:abdi.ahmad"Guenin, Bertrand"https://zbmath.org/authors/?q=ai:guenin.bertrandIn this paper, necessary conditions for a binary clutter to be non-ideal are obtained. By that, the authors prove the weakened version of the flowing conjecture. Moreover, it is shown that for each element \(e\) of the ground set at least one member of a blocking pair of minimally non-ideal binary clutters has a two-point Fano minor going through \(e\), in the case when the both members of the blocking pair don't comprise sets with cardinality 3. The proof is based on the concept of a strict \(e\)-hub.
Reviewer: Svetlana A. Kravchenko (Minsk)Injective-edge coloring of planar graphs with girth at least 6.https://zbmath.org/1449.050872021-01-08T12:24:00+00:00"Bu, Yuehua"https://zbmath.org/authors/?q=ai:bu.yuehua"Chen, Wenwen"https://zbmath.org/authors/?q=ai:chen.wenwenSummary: This paper aims to further explore the properties of planar graphs. The method of minimal counterexamples and discharge was used to analyze the injective-edge coloring number of planar graphs with girth at least 6 and in which 6-cycle and \({7^-}\)-cycle do not intersect. It was proved that the upper bound was at most \(3\Delta (G) - 3\). The result improved a conclusion of the existing known injective-edge coloring number.Proof of a conjecture on a congruence modulo 243 for overpartitions.https://zbmath.org/1449.111032021-01-08T12:24:00+00:00"Huang, Xiaoqian"https://zbmath.org/authors/?q=ai:huang.xiaoqian"Yao, Olivia X. M."https://zbmath.org/authors/?q=ai:yao.olivia-xiang-meiAn overpartition of a positive integer \(n\) is a partition of \(n\) in which the first occurrence of a part may be overlined. Let \(\overline{p}(n)\) denote the number of overpartitions of \(n\). \textit{J. F. Fortin} et al. [Ramanujan J. 10, No. 2, 215--235 (2005; Zbl 1079.05003)], \textit{J.-F. Fortin} et al. [Ramanujan J. 10, 215--235 (2005; Zbl 1079.05003)], \textit{M. D. Hirschhorn} and \textit{J. A. Sellers} [J. Comb. Math. Comb. Comput. 53, 65--73 (2005; Zbl 1086.11048)] established some congruences modulo powers of 2 for \(\overline{p}(n)\). \textit{E. X. W. Xia} and \textit{O. X. M. Yao} [J. Number Theory 133, 1932--1949 (2013; Zbl 1275.11136)] and \textit{E. X. W. Xia} [Ramanujan J. 42, 301--323 (2017; Zbl 1422.11214)] found several congruences modulo powers of 2 and 3. Moreover, \textit{E. X. W. Xia} [ibid.] conjectured that, for \(n \ge 0\), \(\overline{p}(96n+76)\equiv 0 \mod 243.\)
In the paper under review the authors confirm this conjecture by using theta function identities and the \((p, k)\)-parametrization of theta functions due to \textit{A. Alaca, Ş. Alaca,} and \textit{K. S. Williams} [Acta Arith. 124, 177--195 (2006; Zbl 1127.11035)], \textit{Ş. Alaca} and \textit{K. S. Williams} [Funct. Approximatio, Comment. Math. 43, 45--54 (2010; Zbl 1213.11087)].
Reviewer: Mihály Szalay (Budapest)Contraction graph method for the interval edge-colorings of graphs.https://zbmath.org/1449.051122021-01-08T12:24:00+00:00"Tao, Yanliang"https://zbmath.org/authors/?q=ai:tao.yanliang"Huang, Qiongxiang"https://zbmath.org/authors/?q=ai:huang.qiongxiang"Chen, Lin"https://zbmath.org/authors/?q=ai:chen.lin.3Summary: An edge-coloring of a graph \(G\) with colors \(1, 2, \dots, t\) is an interval \(t\)-coloring if all colors are used, and the colors of edges incident to each vertex of \(G\) are distinct and form an interval of integers. A graph \(G\) is interval colorable if it has an interval \(t\)-coloring for some positive integer \(t\). The set of all interval colorable graphs is denoted by \(\mathfrak{N}\). For a graph \(G \in \mathfrak{N}\), the least and the greatest values of \(t\) for which \(G\) has an interval \(t\)-coloring are denoted by \(w (G)\) and \(W (G)\), respectively. In this paper, we introduce a contraction graph method for the interval edge-colorings of graphs. By using this method, we show that \(w (G) = \Delta (G)\) or \(\Delta (G) + 1\) for any bicyclic graph \(G \in \mathfrak{N}\). Moreover, we completely determine bicyclic graphs with \(w (G) = \Delta (G)\) and \(w (G) = \Delta (G) + 1\), respectively.On disjunctive and conjunctive set-labelings of graphs.https://zbmath.org/1449.052282021-01-08T12:24:00+00:00"Sudev, N. K."https://zbmath.org/authors/?q=ai:naduvath.sudevSummary: Let \(X\) be a non-empty set and \(\mathcal{P} (X)\) be its power set. A set-valuation or a set-labeling of a given graph \(G\) is an injective function \(f:V (G) \to \mathcal{P} (X)\) such that the induced function \({f^*}:E (G) \to \mathcal{P} (X)\) defined by \({f^*} (uv) = f (u)*f (v)\), where \(*\) is a binary operation on sets. A set-indexer of a graph \(G\) is an injective set-valued function \(f:V (G) \to \mathcal{P} (X)\) such that the induced function \({f^*}:E (G) \to \mathcal{P} (X)\) is also injective. In this paper, two types of set-labelings, called conjunctive set-labeling and disjunctive set-labeling, of graphs are introduced and some properties and characteristics of these types of set-labelings of graphs are studied.Two sufficient conditions for maximally restricted-edge-connected hypergraphs.https://zbmath.org/1449.051942021-01-08T12:24:00+00:00"Pei, Jianfeng"https://zbmath.org/authors/?q=ai:pei.jianfeng"Lin, Shangwei"https://zbmath.org/authors/?q=ai:lin.shangweiSummary: The restricted edge-connectivity of a graph is a generalization of the classical edge-connectivity, and can be used to accurately measure the fault tolerance of networks. Maximally restricted-edge-connected graphs are a class of graphs with optimal restricted edge-connectivity. In this paper, we first extend the concepts of the restricted edge-connectivity and the minimum edge degree to \(r\)-uniform and linear hypergraphs \(H\), prove that the minimum edge degree \(\xi (H)\) of \(H\) is an upper bound on its restricted edge-connectivity \(\lambda^\prime (H)\) if its minimum degree \(\delta (H) \ge r+1\), and call the hypergraph \(H\) with \(\xi (H) = \lambda^\prime (H)\) a maximally restricted-edge-connected hypergraph. Next, we show that an \(r\)-uniform and linear hypergraph \(H\) with order \(n\) and minimum degree \(\delta (H) \ge \frac{n-1}{2 (r-1)} + (r-1)\) is maximally restricted-edge-connected. Finally, we prove that an \(r\)-uniform and linear hypergraph \(H\) with diameter 2 and girth at least 4 is maximally restricted-edge-connected. These results are generalizations of corresponding results in graphs.New relation formula for generating functions.https://zbmath.org/1449.130182021-01-08T12:24:00+00:00"Chammam, Wathek"https://zbmath.org/authors/?q=ai:chammam.wathekSummary: In this paper, we develop a new relation between certain types of generating functions using formal algorithmic methods. As an application, we give a relation between the generating function and finite-type relations between polynomial sequences.Characterization of signed paths and cycles admitting minus dominating function.https://zbmath.org/1449.051292021-01-08T12:24:00+00:00"Shreyas, S. R."https://zbmath.org/authors/?q=ai:shreyas.s-r"Joseph, Mayamma"https://zbmath.org/authors/?q=ai:joseph.mayammaSummary: If \(G = (V, E, \sigma)\) is a finite signed graph, a function \(f : V \rightarrow \{-1, 0, 1\}\) is a minus dominating function (MDF) of \(G\) if \(f(u) +\sum_{v \in N(u)}\sigma(uv)f(v) \geq 1\) for all \(u\in V\). In this paper, we characterize signed paths and cycles admitting an MDF.The topological ordering of covering nodes.https://zbmath.org/1449.051232021-01-08T12:24:00+00:00"Shirdel, Gholam Hassan"https://zbmath.org/authors/?q=ai:shirdel.gholamhassan"Kahkeshani, Nasrin"https://zbmath.org/authors/?q=ai:kahkeshani.nasrinSummary: The topological ordering algorithm sorts nodes of a directed graph such that the order of the tail of each arc is lower than the order of its head. In this paper, we introduce the notion of covering between nodes of a directed graph. Then, we apply the topological ordering algorithm on graphs containing the covering nodes. We show that there exists a cut set with forward arcs in these graphs and the order of the covering nodes is successive.On the edge geodetic and edge geodetic domination numbers of a graph.https://zbmath.org/1449.052032021-01-08T12:24:00+00:00"Samodivkin, Vladimir"https://zbmath.org/authors/?q=ai:samodivkin.vladimir|samodivkin.vladimir-dSummary: In this paper, we study both concepts of geodetic dominating and edge geodetic dominating sets and derive some tight upper bounds on the edge geodetic and the edge geodetic domination numbers. We also obtain attainable upper bounds on the maximum number of elements in a partition of a vertex set of a connected graph into geodetic sets, edge geodetic sets, geodetic dominating sets and edge geodetic dominating sets, respectively.Total double Roman domination in graphs.https://zbmath.org/1449.052002021-01-08T12:24:00+00:00"Hao, Guoliang"https://zbmath.org/authors/?q=ai:hao.guoliang"Volkmann, Lutz"https://zbmath.org/authors/?q=ai:volkmann.lutz"Mojdeh, Doost Ali"https://zbmath.org/authors/?q=ai:mojdeh.doost-aliSummary: Let \(G\) be a simple graph with vertex set \(V\). A double Roman dominating function (DRDF) on \(G\) is a function \(f:V\rightarrow\{0,1,2,3\}\) satisfying that if \(f(v)=0\), then the vertex \(v\) must be adjacent to at least two vertices assigned \(2\) or one vertex assigned \(3\) under \(f\), whereas if \(f(v)=1\), then the vertex \(v\) must be adjacent to at least one vertex assigned \(2\) or \(3\). The weight of a DRDF \(f\) is the sum \(sum_{v\in V}f(v)\). A total double Roman dominating function (TDRDF) on a graph \(G\) with no isolated vertex is a DRDF \(f\) on \(G\) with the additional property that the subgraph of \(G\) induced by the set \(\{v\in V:f(v)\neq 0\}\) has no isolated vertices. The total double Roman domination number \(\gamma_{\mathrm{tdR}}(G)\) is the minimum weight of a TDRDF on \(G\). In this paper, we give several relations between the total double Roman domination number of a graph and other domination parameters and we determine the total double Roman domination number of some classes of graphs.A note on the Roman domatic number of a digraph.https://zbmath.org/1449.052052021-01-08T12:24:00+00:00"Volkmann, Lutz"https://zbmath.org/authors/?q=ai:volkmann.lutz"Meierling, D."https://zbmath.org/authors/?q=ai:meierling.dirkSummary: A Roman dominating function on a digraph \(D\) with vertex set \(V(D)\) is a labeling \(f:V(D)\to \{0, 1, 2\}\) such that every vertex with label \(0\) has an in-neighbor with label \(2\). A set \(\{f_1,f_2,\dots,f_d\}\) of Roman dominating functions on \(D\) with the property that \(\sum_{i=1}^d f_i(v)\leq 2\) for each \(v\in V(D)\), is called a Roman dominating family (of functions) on \(D\). The maximum number of functions in a Roman dominating family on \(D\) is the Roman domatic number of \(D\), denoted by \(d_R(D)\). In this note, we study the Roman domatic number in digraphs, and we present some sharp bounds for \(d_R(D)\). In addition, we determine the Roman domatic number of some digraphs. Some of our results are extensions of well-known properties of the Roman domatic number of undirected graphs.A study on some properties of leap graphs.https://zbmath.org/1449.050612021-01-08T12:24:00+00:00"Naji, Ahmed M."https://zbmath.org/authors/?q=ai:naji.ahmed-mohammed"Davvaz, B."https://zbmath.org/authors/?q=ai:davvaz.bijan|davvaz.bijn"Mahde, Sultan S."https://zbmath.org/authors/?q=ai:mahde.sultan-senan"Soner, N. D."https://zbmath.org/authors/?q=ai:soner.nandappa-dSummary: In a graph \(G\), the first and second degrees of a vertex \(v\) are equal to the number of their first and second neighbors and are denoted by \(d(v/G)\) and
\(d_2 (v/G)\), respectively. The first, second and third leap Zagreb indices are the sum of squares of second degrees of vertices of \(G\), the sum of products of second degrees of pairs of adjacent vertices in \(G\) and the sum of products of first and second degrees of vertices of \(G\), respectively. In this paper, we initiate in studying a new class of graphs depending on the relationship between first and second degrees of vertices and is so-called a leap graph. Some properties of the leap graphs are presented. All leap trees and \(\{C_3, C_4\}\)-free leap graphs are characterized.The minimal-ABC trees with \(B_2\)-branches.https://zbmath.org/1449.050562021-01-08T12:24:00+00:00"Du, Zhibin"https://zbmath.org/authors/?q=ai:du.zhibin"Dimitrov, Darko"https://zbmath.org/authors/?q=ai:dimitrov.darkoSummary: The atom-bond connectivity (ABC) index is a degree-based graph topological index with a lot of chemical applications, including those of predicting the stability of alkanes and the strain energy of cycloalkanes. It is known [\textit{J. Chen} and \textit{X. Guo}, MATCH Commun. Math. Comput. Chem. 65, No. 3, 713--722 (2011; Zbl 1265.05569); \textit{K. C. Das} et al., ibid. 76, No. 1, 159--170 (2016; Zbl 06750351)] that among all connected graphs, trees minimize the ABC index (such trees are called minimal-ABC trees). Several structural properties of minimal-ABC trees were proved in the past several years. Here we continue to make a step forward towards the complete characterization of the minimal-ABC trees. In [the second author, Discrete Appl. Math. 204, 90--116 (2016; Zbl 1333.05088)], it was shown that a minimal-ABC tree cannot contain more than 11 so-called \(B_2\)-branches. We improve this result by showing that if a minimal-ABC tree of order larger than 39 contains so-called \(B_1\)-branches, then it contains exactly one \(B_2\)-branch, and if a minimal-ABC tree of order larger than 163 contains no \(B_1\)-branch, then it contains at most two \(B_2\)-branches.Study of dimer-monomer on the generalized Hanoi graph.https://zbmath.org/1449.050322021-01-08T12:24:00+00:00"Li, Wei-Bang"https://zbmath.org/authors/?q=ai:li.weibang"Chang, Shu-Chiuan"https://zbmath.org/authors/?q=ai:chang.shu-chiuanSummary: We study the number of dimer-monomers \(M_d(n)\) on the Hanoi graphs \(H_d(n)\) at stage \(n\) with dimension \(d\) equal to 3 and 4. The entropy per site is defined as \(z_{H_d}=\lim_{v \rightarrow \infty}\ln M_d(n)/v\), where \(v\) is the number of vertices on \(H_d(n)\). We obtain the lower and upper bounds of the entropy per site, and the convergence of these bounds approaches to zero rapidly when the calculated stage increases. The numerical values of \(z_{H_d}\) for \(d=3, 4\) are evaluated to more than a hundred digits correct. Using the results with \(d\) less than or equal to 4, we predict the general form of the lower and upper bounds for \(z_{H_d}\) with arbitrary \(d\).Revisiting Narayana's approach to the Chung-Feller theorem.https://zbmath.org/1449.050162021-01-08T12:24:00+00:00"Ghoraishi, Sharaki Seyed Mohsen"https://zbmath.org/authors/?q=ai:ghoraishi.sharaki-seyed-mohsenSummary: Using cyclic permutations, Narayana investigated the relation between the area under north-east paths from the origin to the point \((n,n)\) and the number of the flaws of the paths. His result implies a proof to the Chung-Feller theorem. In this paper by revising the Narayana's approach, we offer short proofs to the theorems of Narayana and Chung-Feller.On the spectra of strong power graphs of finite groups.https://zbmath.org/1449.051332021-01-08T12:24:00+00:00"Fu, Ruiqin"https://zbmath.org/authors/?q=ai:fu.ruiqin"Ma, Xuanlong"https://zbmath.org/authors/?q=ai:ma.xuanlongSummary: Let \(G\) be a finite group of order \(n\). The strong power graph of \(G\) is the undirected graph whose vertex set is \(G\) and two distinct vertices \(x\) and \(y\) are adjacent if \({x^{{n_1}}} = {y^{{n_2}}}\) for some positive integers \({n_1}, {n_2} < n\). In this paper, we give the characteristic polynomials of the distance and adjacency matrix of the strong power graph of \(G\), and compute its distance and adjacency spectrum.Light dual multinets of order six in the projective plane.https://zbmath.org/1449.050392021-01-08T12:24:00+00:00"Bogya, N."https://zbmath.org/authors/?q=ai:bogya.n"Nagy, G. P."https://zbmath.org/authors/?q=ai:nagy.gabor-peterLet \(\mathbb{K}\) be a field, \(Q\) a quasigroup, and for \(i = 1, 2, 3\), let \(\alpha_i : Q \rightarrow \mathrm{PG}(2,\mathbb{K})\) be maps such that the points \(\alpha_1(x), \alpha_2(y)\) and \(\alpha_3(x \cdot y)\) are collinear for all \(x, y \in Q\). Define the multisets \(\Lambda_i = \alpha_i(Q), \ i = 1, 2, 3\). Then \((\Lambda_1, \Lambda_2, \Lambda_3)\) is a dual multinet, labeled by \(Q\). If the maps \(\alpha_i\) are injective and their images \(\Lambda_i\) are disjoint, then the dual multinet is called light. If a line \(\ell\) intersects two components \(\Lambda_i\), \(\Lambda_j\) then there is an integer \(r\) such that \(r = |\ell \cap \Lambda_1| = |\ell \cap \Lambda_2| = |\ell \cap \Lambda_3|\); this integer \(r\) is called the length of \(\ell\) with respect to \((\Lambda_1, \Lambda_2, \Lambda_3)\). According to the authors, previous work suggests that ``the length \(r>1\) of lines of the light dual multinet makes a big difference in their geometric structure. While for \(r \geq 9\), the light dual multinet is well structured in (the) geometric and algebraic sense, the case of small \(r\), especially \(r=2\) shows many irregularities''. In this paper, the authors classify all abstract light dual multinets of order 6 with a unique line of length \(r>1\), and they compute all possible realizations of these abstract light dual multinets in projective planes over fields of characteristic zero.
Reviewer: Juan C. Migliore (Notre Dame)On the extendability of I-graphs.https://zbmath.org/1449.052162021-01-08T12:24:00+00:00"Wang, Jinwei"https://zbmath.org/authors/?q=ai:wang.jinwei"He, Mingwei"https://zbmath.org/authors/?q=ai:he.mingweiSummary: A connected graph I is \(n\)-extendable if \(n\) edges which do not have a common vertex are contained in a perfect matching of the graph. In this paper, we show that the proper I-graph \(I (n, j, k)\) is 1-extendable and 2-extendable where \(n \ne 3j\) or \(3k\).On the permanental sum of bicyclic graphs.https://zbmath.org/1449.051442021-01-08T12:24:00+00:00"Wu, Tingzeng"https://zbmath.org/authors/?q=ai:wu.tingzeng"Das, Kinkar Chandra"https://zbmath.org/authors/?q=ai:das.kinkar-chandraSummary: Let \(A(G)\) be the adjacency matrix of a graph \(G\). The permanental polynomial of \(G\) is defined as \(\pi (G,x)=\mathrm{per}(xI-A(G))\). The permanental sum of \(G\) can be defined as the sum of the absolute values of the coefficients of \(\pi (G,x)\). In this paper, we investigate the properties of the permanental sum of bicyclic graphs. We present upper and lower bounds of the permanental sum of bicyclic graphs, and the corresponding extremal bicyclic graphs are also determined.On permutations avoiding 1243, 2134, and another 4-letter pattern.https://zbmath.org/1449.050132021-01-08T12:24:00+00:00"Callan, David"https://zbmath.org/authors/?q=ai:callan.david"Mansour, Toufik"https://zbmath.org/authors/?q=ai:mansour.toufikSummary: We enumerate permutations avoiding 1243, 2134, and a third 4-letter pattern \(\tau\), a step toward the goal of enumerating avoiders for all triples of 4-letter patterns. The enumeration is already known for all but five patterns \(\tau\), which are treated in this paper.On permutations avoiding 1324, 2143, and another 4-letter pattern.https://zbmath.org/1449.050122021-01-08T12:24:00+00:00"Callan, David"https://zbmath.org/authors/?q=ai:callan.david"Mansour, Toufik"https://zbmath.org/authors/?q=ai:mansour.toufikSummary: We enumerate permutations avoiding 1324, 2143, and a third 4-letter pattern \(\tau\), a step toward the goal of enumerating avoiders for all triples of 4-letter patterns. The enumeration is already known for all but five patterns \(\tau\), which are treated in this paper.Coloring decompositions of complete geometric graphs.https://zbmath.org/1449.050982021-01-08T12:24:00+00:00"Huemer, C."https://zbmath.org/authors/?q=ai:huemer.clemens"Lara, D."https://zbmath.org/authors/?q=ai:lara.dolores"Rubio-Montiel, C."https://zbmath.org/authors/?q=ai:rubio-montiel.christianA geometric graph \(G\) is a drawing in the plane of a simple graph \(G\) such that no three vertices are on a line and edges are straight-line segments. Two geometric graphs have nonempty intersection if they share a vertex or there exists a pair of crossing edges, one from each graph. A decomposition of a geometric graph \(G\) is a pair \([G, P]\) such that \(P\) is a partition of the edges of \(G\). A \(k\)-\(P\)-coloring of a decomposition \([G, P]\) is a mapping from edges of \(G\) to a set of \(k\) colors satisfying the following conditions. (1) All edges of a member in \(P\) are colored the same. (2) If \(H_1, H_2 \in P\) have nonempty intersection, then their edges are colored differently. The chromatic index of \([G, P]\), denoted by \(\chi^\prime([G, P])\), is the smallest positive integer \(k\) for which there is a \(k\)-\(P\)-coloring of \([G, P]\).
Let \([K_n, P]\) be a decomposition of the complete geometric graph \(K_n\). Then \(\chi^\prime([K_n, P]) \leq \frac{n^2}{6}+O(n^{3/2})\). The upper bound can be strengthened to \(\frac{n^2}{12}+O(n^{3/2})\) if \(P\) does not contain triangles. For every natural number \(n\), there exists some \([K_n, P]\) such that \(\chi^\prime([K_n, P]) \geq \frac{n^2}{24.5}+\Theta (n)\). When the vertices of a complete graph are drawn as the vertices of a regular \(n\)-gon, this complete convex geometric graph is denoted by \(K^c_n\). Then the above lower bound can be raised to \(\chi^\prime([K^c_n, P]) \geq \frac{n^2}{9}-O(n)\). It is also proved that, for every \([K^c_n, P]\) such that all elements in \(P\) are triangles, \(\chi^\prime([K^c_n, P]) \geq \frac{n^2}{119}-O(n)\). Finally, the authors propose the so-called Erdős-Faber-Lovász conjecture for complete geometric graphs as follows. Let \([K_n, P]\) be a decomposition of \(K_n\), then \(\chi^\prime([K_n, P]) \leq \frac{n^2}{9}+\Theta(n)\).
Reviewer: Ko-Wei Lih (Taipei)Recurrence calculation of the perfect matchings number of two types of graphs.https://zbmath.org/1449.052122021-01-08T12:24:00+00:00"Tang, Baoxiang"https://zbmath.org/authors/?q=ai:tang.baoxiang"Ren, Han"https://zbmath.org/authors/?q=ai:ren.hanSummary: By the methods of partition, summation and then nested recursion, the perfect matching counting problem of two types of special graphs is studied. The formulas of the perfect matching numbers of the graphs \(3 - n{C_{6, 3}}\) and \(3 - n{P_{2, 4}}\) are given. By the method presented in this paper, the number of all perfect matchings of many graphs can be calculated. Therefore, this provides the theory to support the application of perfect matching in graph.The normalized Laplacian spectrum of pentagonal graphs and its applications.https://zbmath.org/1449.051772021-01-08T12:24:00+00:00"Xu, Xiaojing"https://zbmath.org/authors/?q=ai:xu.xiaojing"Wang, Peiwen"https://zbmath.org/authors/?q=ai:wang.peiwen"Wang, Zhiping"https://zbmath.org/authors/?q=ai:wang.zhipingSummary: The eigenvalues of the normalized Laplacian of a graph provide information on its structural properties and also on some relevant dynamical aspects, in particular those related to random walks. In this paper, we give the spectra of the normalized Laplacian of iterated pentagonal of a simple connected graph. As an application, we also find a significant formulae for their multiplicative degree-Kirchhoff index, Kemeny's constant and number of spanning trees.A new matrix inversion for Bell polynomials and its applications.https://zbmath.org/1449.150062021-01-08T12:24:00+00:00"Wang, Jin"https://zbmath.org/authors/?q=ai:wang.jinSummary: The present paper gives a new Bell matrix inversion which arises from the classical Lagrange inversion formula. Some new relations for the Bell polynomials are obtained, including a Bell matrix inversion in closed form and an inverse form of the classical Faa di Bruno formula.Independence and matching numbers of unicyclic graphs from null space.https://zbmath.org/1449.051652021-01-08T12:24:00+00:00"Allem, L. Emilio"https://zbmath.org/authors/?q=ai:allem.luiz-emilio"Jaume, Daniel A."https://zbmath.org/authors/?q=ai:jaume.daniel-a"Molina, Gonzalo"https://zbmath.org/authors/?q=ai:molina.gonzalo"Toledo, Maikon M."https://zbmath.org/authors/?q=ai:toledo.maikon-m"Trevisan, Vilmar"https://zbmath.org/authors/?q=ai:trevisan.vilmarSummary: We characterize unicyclic graphs that are singular using the support of the null space of their pendant trees. From this, we obtain closed formulas for the independence and matching numbers of a unicyclic graph, based on the support of its subtrees. These formulas allows one to compute independence and matching numbers of unicyclic graphs using linear algebra methods.On the maximal minimal cube lengths in distinct DNF tautologies.https://zbmath.org/1449.050182021-01-08T12:24:00+00:00"Kauers, Manuel"https://zbmath.org/authors/?q=ai:kauers.manuel"Seidl, Martina"https://zbmath.org/authors/?q=ai:seidl.martina"Zeilberger, Doron"https://zbmath.org/authors/?q=ai:zeilberger.doronSummary: Inspired by a recent article by \textit{A. Zaleski} and \textit{D. Zeilberger} [``Boolean function analogs of covering systems'', Preprint, \url{arXiv:1801.05097}], we investigate the question of determining the largest \(k\) for which there exist Boolean formulas in disjunctive normal form (DNF) with \(n\) variables, which are tautologies, whose conjunctions have distinct sets of variables, and such that all the conjunctions have at leastkliterals. Using a SAT solver, we answer the question for some sizes which Zaleski and Zeilberger [loc. cit.] left open. We also determine the corresponding numbers for DNFs obeying certain symmetries.A description of the automorphism groups of the convex regular 4-polytopes.https://zbmath.org/1449.051312021-01-08T12:24:00+00:00"Cai, Qi"https://zbmath.org/authors/?q=ai:cai.qi"Yu, Lu"https://zbmath.org/authors/?q=ai:yu.lu"Zhang, Hua"https://zbmath.org/authors/?q=ai:zhang.huaSummary: In combinatorial mathematics, it is an important and often a difficult problem of determining the automorphism group of a graph or various combinatorial structures. In this paper, we depict the automorphism groups of the convex regular 4-polytopes by using the basic theory of graphs and permutation groups.Some properties of the maximal graph of a commutative ring.https://zbmath.org/1449.051342021-01-08T12:24:00+00:00"Mahmudi, F."https://zbmath.org/authors/?q=ai:mahmudi.fatemeh"Soleimani, M."https://zbmath.org/authors/?q=ai:soleimani.manuchehr|soleimani.mohammad|soleimani.meisam|soleimani.m-j|soleimani.majid"Naderi, M. H."https://zbmath.org/authors/?q=ai:naderi.mohammad-hossein|naderi.mohamad-hosein|naderi.mohammad-hassanSummary: Let \(R\) be a commutative ring with identity. The maximal graph of \(R\) is the graph whose vertices are elements of \(R\), where two distinct vertices \(x\) and \(y\) are adjacent if and only if there is a maximal ideal of \(R\) containing both. In this paper we investigate some properties of two subgraphs of this graph.A method of constructing families of equienergetic graphs.https://zbmath.org/1449.051742021-01-08T12:24:00+00:00"Wang, Hongbo"https://zbmath.org/authors/?q=ai:wang.hongbo"Lin, Hong"https://zbmath.org/authors/?q=ai:lin.hongSummary: As an important graph index the energy of a graph is defined as the absolute sum of eigenvalues of the adjacency matrix of the graph. By matrix theory the characterization of the spectrum of a join union graph is given, which means that the spectrum of the joined union graph \(G[{G_1}, {G_2}, \dots, {G_n}]\) generated by regular graphs \({G_1}, {G_2}, \dots, {G_n}\) consists of the spectra of \({G_1}, {G_2}, \dots, {G_n}\) (except for the first maximal eigenvalue of every \({G_i}\)) and the eigenvalues of an auxiliary matrix determined by graph \(G\). By this characterization a method of constructing equienergetic graphs is given. As its application, we give some examples of equienergetic graphs.Odd harmonious labeling of some new graphs.https://zbmath.org/1449.052252021-01-08T12:24:00+00:00"Jeyanthi, P."https://zbmath.org/authors/?q=ai:jeyanthi.pon"Philo, S."https://zbmath.org/authors/?q=ai:philo.sSummary: A graph \(G (p,q)\) is said to be odd harmonious if there exists an injection \(f:V (G)\to \{0,1,2,\dots, 2q-1\}\) such that the induced function \({f^\ast}:E (G) \to \{1,3,\dots, 2q-1\}\) defined by \({f^\ast} (uv) = f (u) + f (v)\) is a bijection. In this paper we prove that the \(m\)-shadow and the \(m\)-splitting of the graphs \({P_n}\), \({H_{n, m}}\), \({K_{r, s}}\), \({P_n} \oplus {\overline {K_2}}\) and \(Spl_m (C_n)\), \(n \equiv 0 \pmod 4\) are odd harmonious graphs.Turán's theorem for the Fano plane.https://zbmath.org/1449.051922021-01-08T12:24:00+00:00"Bellmann, Louis"https://zbmath.org/authors/?q=ai:bellmann.louis"Reiher, Christian"https://zbmath.org/authors/?q=ai:reiher.christianGiven a given natural number \(n\) and a 3-uniform hypergraph \(F\) which is the Fano plane, consider Turán's problem of determining the largest number of edges that a 3-uniform hypergraph \(H\) can have without containing \(F\) as a subhypergraph. The authors prove that for \(n\)> 8 the balanced, complete, bipartite hypergraph is indeed the only extremal configuration. For \(n=7\), there is exactly one other extremal configuration with the same number of edges.
Reviewer: Hang Lau (Montréal)New reciprocal sums involving finite products of second order recursions.https://zbmath.org/1449.110232021-01-08T12:24:00+00:00"Kılıç, Emrah"https://zbmath.org/authors/?q=ai:kilic.emrah"Ersanlı, Didem"https://zbmath.org/authors/?q=ai:ersanli.didemSummary: In this paper, we present new kinds of reciprocal sums of finite products of general second order linear recurrences. In order to evaluate explicitly them by \(q\)-calculus, first we convert them into their \(q\)-notation and then use the methods of partial fraction decomposition and creative telescoping.On one property of the weighed sums of equal powers as matrix products.https://zbmath.org/1449.110692021-01-08T12:24:00+00:00"Nikonov, Aleksandr Ivanovich"https://zbmath.org/authors/?q=ai:nikonov.aleksandr-ivanovichSummary: Finite sum of weighted sum of equal powers is represented in matrix form. This is expressed by the presence of two matrix components, the first of which does not contain, and the second contains the specified weights. It is significant that if the maximum power grounds in the amounts of this type has a value of no less important exponent related to its term, the first matrix component is the same for all amounts that meet the specified condition. Revealed common property of the matrix representation used to obtain the modified final sum from the increased number of weights.New upper bounds for the symmetric division deg index of graphs.https://zbmath.org/1449.050632021-01-08T12:24:00+00:00"Palacios, José Luis"https://zbmath.org/authors/?q=ai:palacios.jose-luisSummary: We find a new upper bound for the symmetric division deg index \(SDD(G)\) of a graph \(G\) with \(n\) vertices, in terms of the inverse degree index, that is attained by all regular, all complete multipartite graphs, \(K_{p_1,p_2,\ldots,p_r}\), and all \((n-1, d)\)-regular graphs of order \(n\), where \(1 \leq d < n-1\). This upper bound allows us to find further upper bounds in terms of other indices and other parameters. Along the way, we review some maximal results and upper bounds, and conjecture other results for \(c\)-cyclic graphs when \(c \geq 3\).Laplacian spectral characterization of 4-rose graphs.https://zbmath.org/1449.051702021-01-08T12:24:00+00:00"Ma, Xiaoling"https://zbmath.org/authors/?q=ai:ma.xiaolingSummary: A \(p\)-rose graph is a graph consisting of \(p\) cycles sharing a common vertex. Some previous researchers proved that all 3-rose graphs were determined by their Laplacian spectra (DLS for brevity) and conjectured that all \(p\)-rose graphs (\(p \ge 3\)) were DLS. In this paper, the Laplacian characteristic polynomials of 4-rose graph are firstly given, and then the aforementioned conjecture is proved to be valid for \(p = 4\). In other words, all 4-rose graphs are determined by their Laplacian spectra.A note on isomorphic generalized Petersen graphs with an application to the crossing number of \(GP[3k-1,k]\) and \(GP[3k+1,k]\).https://zbmath.org/1449.050772021-01-08T12:24:00+00:00"Gauci, John Baptist"https://zbmath.org/authors/?q=ai:gauci.john-baptist"Xuereb, Cheryl Zerafa"https://zbmath.org/authors/?q=ai:xuereb.cheryl-zerafaSummary: For positive integers \(n\) and \(k\), the generalized Petersen graph \(GP[n, k]\) is the graph on the \(2n\) vertices \(\{u_0, u_1,\ldots,u_{n -1}, x_0, x_1, \ldots , x_{n-1}\) and the edges \(\{\{u_i, x_i\},\{u_i, u_{i+1}\},\{x_i, x_{i+k}\}\}\), where \(i= 0,1,\ldots, n-1\), addition modulo \(n\). The crossing number of a graph \(G\) is defined as the least number of crossings of edges of \(G\) when \(G\) is drawn in a surface, which in our case will be the Euclidean plane. We prove a conjecture presented by \textit{Z. Zhou} and \textit{J. Wang} [Int. J. Math. Comb. 2012, No. 4, 116--123 (2012; Zbl 1263.05022)] on the crossing number of \(GP[3k-1, k]\) and derive a quick way to check if a result by \textit{M. E. Watkins} [J. Comb. Theory 6, 152--164 (1969; Zbl 0175.50303)] can be used to establish whether two generalized Petersen graphs on different parameters are isomorphic.On a conjecture about the second Zagreb index.https://zbmath.org/1449.050552021-01-08T12:24:00+00:00"Das, Kinkar Chandra"https://zbmath.org/authors/?q=ai:das.kinkar-chandra"Ali, Akbar"https://zbmath.org/authors/?q=ai:ali.akbar|ali.akbar.1Summary: The cyclomatic number \(\nu\) of a graph \(G\) is the minimum number of those edges of \(G\) whose removal makes \(G\) acyclic. The second Zagreb index \(M_2\) for a graph \(G\) is the sum of the products of degrees of adjacent vertices of \(G\). For \(\nu =\binom{k-1}{2}+t\) with \(1 \leq t \leq k -1\) and \(4 \leq k \leq n -2\), let \(G^{\ast}\) be the graph having maximum \(M_2\) value in the class of all connected graphs with ordernand cyclomatic number \(\nu \). \textit{K. Xu} et al. [MATCH Commun. Math. Comput. Chem. 72, No. 3, 641--654 (2014; Zbl 06704632)] posed a conjecture concerning the exact structure of the graph \(G^{\ast}\). In this note, a partial progress is made on this conjecture by proving that \(G^{\ast}\) has a specific type of subgraph with the size \(\binom {k-1}{2} + t\) and minimum degree at least one.