Recent zbMATH articles in MSC 05Chttps://zbmath.org/atom/cc/05C2024-05-13T19:39:47.825584ZUnknown authorWerkzeugTaking music seriously: on the dynamics of `mathemusical' research with a focus on hexachordal theoremshttps://zbmath.org/1532.000202024-05-13T19:39:47.825584Z"Andreatta, Moreno"https://zbmath.org/authors/?q=ai:andreatta.moreno"Guichaoua, Corentin"https://zbmath.org/authors/?q=ai:guichaoua.corentin"Juillet, Nicolas"https://zbmath.org/authors/?q=ai:juillet.nicolasSummary: After presenting the general framework of ``mathemusical'' dynamics, we focus on one music-theoretical problem concerning a special case of homometry theory applied to music composition, namely Milton Babbitt's hexachordal theorem. We briefly discuss some historical aspects of homometric structures and their ramifications in crystallography, spectral analysis and music composition via the construction of rhythmic canons tiling the integer line. We then present the probabilistic generalization of Babbitt's result we recently introduced in a paper entitled ``New hexachordal theorems in metric spaces with probability measure'' and illustrate the new approach with original constructions and examples.Remarks on generic stability in independent theorieshttps://zbmath.org/1532.030512024-05-13T19:39:47.825584Z"Conant, Gabriel"https://zbmath.org/authors/?q=ai:conant.gabriel"Gannon, Kyle"https://zbmath.org/authors/?q=ai:gannon.kyleSummary: In NIP theories, generically stable Keisler measures can be characterized in several ways. We analyze these various forms of ``generic stability'' in arbitrary theories. Among other things, we show that the standard definition of generic stability for types coincides with the notion of a frequency interpretation measure. We also give combinatorial examples of types in NSOP theories that are finitely approximated but not generically stable, as well as \(\varphi \)-types in simple theories that are definable and finitely satisfiable in a small model, but not finitely approximated. Our proofs demonstrate interesting connections to classical results from Ramsey theory for finite graphs and hypergraphs.Stanley-Wilf limits for patterns in rooted labeled forestshttps://zbmath.org/1532.050052024-05-13T19:39:47.825584Z"Ren, Michael"https://zbmath.org/authors/?q=ai:ren.michael-sSummary: Building off recent work of \textit{S. Garg} and \textit{A. Peng} [J. Comb. Theory, Ser. A 194, Article ID 105699, 52 p. (2023; Zbl 1502.05004)], we continue the investigation into classical and consecutive pattern avoidance in rooted forests. We prove a forest analogue of the Stanley-Wilf conjecture for avoiding a single pattern as well as certain other sets of patterns. Our techniques are analytic, easily generalizing to different types of pattern avoidance and allowing for computations of convergent lower bounds of the forest Stanley-Wilf limit in the cases covered by our result. We end with several open questions and directions for future research, including some on the limit distributions of certain statistics of pattern-avoiding forests.Some cubic time regularity algorithms for triple systemshttps://zbmath.org/1532.050192024-05-13T19:39:47.825584Z"Nagle, Brendan"https://zbmath.org/authors/?q=ai:nagle.brendan"Theado, John"https://zbmath.org/authors/?q=ai:theado.johnSummary: Szemerédi's regularity lemma guarantees that, for fixed \(\varepsilon>0\), every graph \(G=(V,E)\) admits an \(\varepsilon\)-regular and \(t\)-equitable partition \(\Pi(G)\), where \(t=O(1)\). These partitions are constructed by \textit{Y. Kohayakawa} et al. [in: Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2002, San Francisco, CA, USA, January 6--8, 2002. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 277--284 (2002; Zbl 1093.68623)] in time \(O(|V|^2)\). Analogous partitions of \(k\)-graphs \(H^{(k)}\) are constructed by \textit{A. Czygrinow} and \textit{V. Rödl} [SIAM J. Comput. 30, No. 4, 1041--1066 (2000; Zbl 0971.05084)] in time \(O(|V|^{2k-1} \log^5|V|)\). For \(k=3\), we construct these partitions (and others with slightly stronger regularity) in time \(O(|V|^3)\). We also discuss some applications.Enumeration of Latin squares with conjugate symmetryhttps://zbmath.org/1532.050232024-05-13T19:39:47.825584Z"McKay, Brendan D."https://zbmath.org/authors/?q=ai:mckay.brendan-d"Wanless, Ian M."https://zbmath.org/authors/?q=ai:wanless.ian-mA Latin square of order \(n\) can be thought of as an \(n\times n\) matrix where each row and column is a permutation of a symbol set of order \(n\) which we take to be \([n]=\{1,2,\ldots n\}\). Equivalently it can be thought of as a set of \(n^{2}\) triples of the form (row, column, symbol) and the Latin property means that no two triples agree in more than one coordinate. Each Latin square has six conjugates, corresponding to the six permutations of the three coordinates. A Latin square is said to have a conjugate symmetry if at least two of the six conjugates are equal, and is totally symmetric if it is equal to all six of its conjugates. It is semisymmetric if it is equal to at least three of its conjugates (which must include the \((1,2,3), (2,3,1)\) and \((3,1,2)\) conjugates), and symmetric if it equals its \((2,1,3)\)-conjugate. The aim of the paper under review is to count all Latin squares of small order which have a conjugate symmetry -- it is enough to count the totally symmetric, semisymmetric, and symmetric Latin squares.
In each case, the authors also give the number of Latin squares which, in addition to being totally symmetric, semisymmetric, and symmetric, have one of the following properties: being unipotent (i.e. all entries on the main diagonal are the same symbol), diagonal (i.e. all entries on the main diagonal are distinct) idempotent (i.e. it is diagonal and the symbols occur in the natural order on the diagonal) or reduced (having the first row and first column being in the natural order). In some cases, somewhat more breakdown is given. The research revealed some errors in earlier work by \textit{A. Sade} [Univ. Lisboa, Revista Fac. Ci., II. Ser., A 11, 121--136 (1965; Zbl 0149.02303)], which is discussed in Section 4 of the paper, and the calculations suggested some conjectures which the authors could then prove.
Both authors carried out the calculations reported in the paper independently using non-identical algorithms. Much of the information produced is available at \url{https://users.monash.edu.au/~iwanless/data/index.html}.
Reviewer: David B. Penman (Colchester)The binary rank of circulant block matriceshttps://zbmath.org/1532.050252024-05-13T19:39:47.825584Z"Haviv, Ishay"https://zbmath.org/authors/?q=ai:haviv.ishay"Parnas, Michal"https://zbmath.org/authors/?q=ai:parnas.michalSummary: The binary rank of a \(0, 1\) matrix is the smallest size of a partition of its ones into monochromatic combinatorial rectangles. A matrix \(M\) is called \(( k_1, \ldots, k_m; n_1, \ldots, n_m)\) circulant block diagonal if it is a block matrix with \(m\) diagonal blocks, such that for each \(i \in [m]\), the \(i\)th diagonal block of \(M\) is the circulant matrix whose first row has \(k_i\) ones followed by \(n_i - k_i\) zeros, and all of whose other entries are zeros. In this work, we study the binary rank of these matrices as well as the binary rank of their complement, obtained by replacing the zeros by ones and the ones by zeros. In particular, we compare the binary rank of these matrices to their rank over the reals, which forms a lower bound on the former.
We present a general method for proving upper bounds on the binary rank of block matrices that have diagonal blocks of some specified structure and ones elsewhere. Using this method, we prove that the binary rank of the complement of a \(( k_1, \ldots, k_m; n_1, \ldots, n_m)\) circulant block diagonal matrix for integers satisfying \(n_i > k_i > 0\) for each \(i \in [m]\) exceeds its real rank by no more than the maximum of \(\gcd( n_i, k_i) - 1\) over all \(i \in [m]\). We further present several sufficient conditions for the binary rank of these matrices to strictly exceed their real rank. By combining the upper and lower bounds, we determine the exact binary rank of various families of matrices and, in addition, significantly generalize a result of \textit{D. A. Gregory} [J. Comb. Math. Comb. Comput. 6, 183--187 (1989; Zbl 0691.05017)].
Motivated by a question of \textit{N. J. Pullman} [``Ranks of binary matrices with constant line sums'', Linear Algebra Appl. 104, 193--197 (1988)], we study the binary rank of \(k\)-regular \(0, 1\) matrices, those having precisely \(k\) ones in every row and column, and the binary rank of their complement. As an application of our results on circulant block diagonal matrices, we show that for every \(k \geq 2\), there exist \(k\)-regular \(0, 1\) matrices whose binary rank is strictly larger than that of their complement. Furthermore, we exactly determine for every integer \(r\), the smallest possible binary rank of the complement of a 2-regular \(0, 1\) matrix with binary rank \(r\).New infinite classes of 2-chromatic Steiner quadruple systemshttps://zbmath.org/1532.050292024-05-13T19:39:47.825584Z"Ji, Lijun"https://zbmath.org/authors/?q=ai:ji.lijun"Liu, Shuangqing"https://zbmath.org/authors/?q=ai:liu.shuangqing"Yang, Ye"https://zbmath.org/authors/?q=ai:yang.yeSummary: \textit{J. Doyen} and \textit{M. Vandensavel} [Bull. Soc. Math. Belg. 23, 393--410 (1971; Zbl 0252.05012)] gave a special doubling construction that gives a direct construction of 2-chromatic Steiner quadruple system of order \(\nu\) (SQS\((\nu))\) for all \(\nu\equiv 4\) or \(8\pmod{12}\). The first author presented a construction for 2-chromatic SQSs based on 2-chromatic candelabra quadruple systems and \(s\)-fan designs. In this paper, it is proved that a 2-chromatic SQS\((\nu)\) also exists if \(\nu\equiv 10\pmod{12}\), or if \(\nu\equiv 2\pmod{24}\).Almost every matroid has an \(M(K_4)\)- or a \(\mathcal{W}^3\)-minorhttps://zbmath.org/1532.050332024-05-13T19:39:47.825584Z"van der Pol, Jorn"https://zbmath.org/authors/?q=ai:van-der-pol.jorn-gSummary: We show that almost every matroid contains the rank-3 whirl \(\mathcal{W}^3\) or the complete-graphic matroid \(M(K_4)\) as a minor.Tiered trees and theta operatorshttps://zbmath.org/1532.050362024-05-13T19:39:47.825584Z"D'Adderio, Michele"https://zbmath.org/authors/?q=ai:dadderio.michele"Iraci, Alessandro"https://zbmath.org/authors/?q=ai:iraci.alessandro"Le Borgne, Yvan"https://zbmath.org/authors/?q=ai:le-borgne.yvan"Romero, Marino"https://zbmath.org/authors/?q=ai:romero.marino"Vanden Wyngaerd, Anna"https://zbmath.org/authors/?q=ai:vanden-wyngaerd.annaSummary: In [\textit{W. Dugan} et al., J. Comb. Theory, Ser. A 164, 24--49 (2019; Zbl 1407.05048)], the authors introduced tiered trees to define combinatorial objects counting absolutely indecomposable representations of certain quivers and torus orbits on certain homogeneous varieties. In this paper, we use Theta operators, introduced in [\textit{M. D'Adderio} et al., Adv. Math. 376, Article ID 107447, 60 p. (2021; Zbl 1453.05135)], to give a symmetric function formula that enumerates these trees. We then formulate a general conjecture that extends this result, a special case of which might give some insight about how to formulate a unified Delta conjecture [\textit{J. Haglund} et al., Trans. Am. Math. Soc. 370, No. 6, 4029--4057 (2018; Zbl 1383.05308)].A spanning tree with at most \(k\) leaves in a \(K_{1,p}\)-free graphhttps://zbmath.org/1532.050372024-05-13T19:39:47.825584Z"Ozeki, Kenta"https://zbmath.org/authors/?q=ai:ozeki.kenta"Tsugaki, Masao"https://zbmath.org/authors/?q=ai:tsugaki.masaoSummary: For an integer \(k \geqslant 2\), a tree is called a \(k\)-ended tree if it has at most \(k\) leaves. It was shown that some \(\sigma_{k+1}(G)\) conditions assure the existence of a spanning \(k\)-ended tree in a connected \(K_{1, p}\)-free graph \(G\) for the pairs \((p,k)\) with \(p \leq 4\), or \(p= 5\) and \(k=4,6\), where \(\sigma_{k+1}(G)\) is the minimum degree sum of pairwise non-adjacent \(k+1\) vertices of \(G\). In this paper, we extend those results to the case with any integer \(p \geq 3\) by proving that for any \(k \geqslant 2\) and \(p \geqslant 3\), there exists a constant \(f(p,k)\) depending only on \(k\) and \(p\) such that if a connected \(K_{1, p}\)-free graph satisfies \(\sigma_{k+1}(G) \geqslant |G|+ f(p,k)\), then \(G\) has a spanning \(k\)-ended tree. The coefficient \(1\) of \(|G|\) in the \(\sigma_{k+1}(G)\) condition is best possible.The structure of minimally \(t\)-tough, \(2K_2\)-free graphshttps://zbmath.org/1532.050382024-05-13T19:39:47.825584Z"Ma, Hui"https://zbmath.org/authors/?q=ai:ma.hui"Hu, Xiaomin"https://zbmath.org/authors/?q=ai:hu.xiaomin"Yang, Weihua"https://zbmath.org/authors/?q=ai:yang.weihuaSummary: A graph \(G\) is minimally \(t\)-tough if the toughness of \(G\) is \(t\) and deletion of any edge from \(G\) decreases its toughness. Kriesell conjectured that the minimum degree of a minimally 1-tough graph is 2, and \textit{G. Y. Katona} et al. [Discrete Math. 341, No. 1, 221--231 (2018; Zbl 1372.05108)] proposed a generalized version of the conjecture that the minimum degree of a minimally \(t\)-tough graph is \(\lceil 2 t \rceil\). In this paper, we characterize the minimally \(1/a\)-tough, \(2K_2\)-free graphs for an integer \(a\).Irregularity of graphs respecting degree boundshttps://zbmath.org/1532.050392024-05-13T19:39:47.825584Z"Rautenbach, Dieter"https://zbmath.org/authors/?q=ai:rautenbach.dieter"Werner, Florian"https://zbmath.org/authors/?q=ai:werner.florianSummary: \textit{M. O. Albertson} [Ars Comb. 46, 219--225 (1997; Zbl 0933.05073)] defined the irregularity of a graph \(G\) as \[\operatorname{irr}(G)=\sum\limits_{uv\in E(G)}|d_G(u)-d_G(v)|.\] For a graph \(G\) with \(n\) vertices, \(m\) edges, maximum degree \(\Delta \), and \(d=\left\lfloor \frac{\Delta m}{\Delta n-m}\right\rfloor \), we show \[\operatorname{irr}(G)\leq d(d+1)n+\frac{1}{\Delta}\left(\Delta^2-(2d+1)\Delta-d^2-d\right)m.\]Retraction notice to: ``Computing first and second fuzzy Zagreb indices of linear and multiacyclic hydrocarbons''https://zbmath.org/1532.050402024-05-13T19:39:47.825584ZRetraction notice to the article [\textit{Z. S. Mufti} et al., J. Funct. Spaces 2022, Article ID 6281592, 8 p. (2022; Zbl 1487.05064)].
From the text:
This article has been retracted by Hindawi following an investigation undertaken by the publisher. This investigation
has uncovered evidence of one or more of the following indicators of systematic manipulation of the publication process.Retraction notice to: ``On topological properties of degree-based entropy of hex-derived network of type 3''https://zbmath.org/1532.050412024-05-13T19:39:47.825584ZRetraction notice to the article [\textit{C.-B. Zhu} et al., J. Funct. Spaces 2022, Article ID 2557696, 7~p. (2022; Zbl 1491.05057)].
From the text: This article has been retracted by Hindawi following an investigation undertaken by the publisher. This investigation
has uncovered evidence of one or more of the following indicators of systematic manipulation of the publication process.Retraction notice to: ``Analysis of eccentricity-based topological invariants with zero-divisor graphs''https://zbmath.org/1532.050422024-05-13T19:39:47.825584ZRetraction notice to the article [\textit{Z.-h. Hui} et al., J. Funct. Spaces 2022, Article ID 6911654, 10~p. (2022; Zbl 1493.05074)].
From the text: This article has been retracted by Hindawi following an investigation undertaken by the publisher. This investigation
has uncovered evidence of one or more of the following indicators of systematic manipulation of the publication process.Irregularity Sombor indexhttps://zbmath.org/1532.050432024-05-13T19:39:47.825584Z"Gutman, Ivan"https://zbmath.org/authors/?q=ai:gutman.ivan-m"Kulli, Veerabhadrappa R."https://zbmath.org/authors/?q=ai:kulli.veerabhadrappa-r"Redžepović, Izudin"https://zbmath.org/authors/?q=ai:redzepovic.izudinSummary: The irregularity Sombor index \textit{ISO} is a recently introduced measure for graph irregularity, defined as the sum over all pairs of adjacent vertices \(u,v\) of the term \(\sqrt{|d_u^2 -d_v^2|}\), where \(d_u\) is the degree of the vertex \(u\). Some basic mathematical properties of \textit{ISO} are established.Fractal version of Zagreb eccentricity indexhttps://zbmath.org/1532.050442024-05-13T19:39:47.825584Z"Xu, Jiajun"https://zbmath.org/authors/?q=ai:xu.jiajun"Lu, Ying"https://zbmath.org/authors/?q=ai:lu.ying.2|lu.ying"Xi, Lifeng"https://zbmath.org/authors/?q=ai:xi.lifeng(no abstract)On a relation between bipartite biregular cages, block designs and generalized polygonshttps://zbmath.org/1532.050452024-05-13T19:39:47.825584Z"Araujo-Pardo, Gabriela"https://zbmath.org/authors/?q=ai:araujo-pardo.gabriela"Jajcay, Robert"https://zbmath.org/authors/?q=ai:jajcay.robert"Ramos-Rivera, Alejandra"https://zbmath.org/authors/?q=ai:ramos-rivera.alejandra"Szőnyi, Tamás"https://zbmath.org/authors/?q=ai:szonyi.tamasSummary: A bipartite biregular \((m,n;g)\)-graph \(\Gamma\) is a bipartite graph of even girth \(g\) having the degree set \(\{m,n\}\) and satisfying the additional property that the vertices in the same partite set have the same degree. An \((m,n;g)\)-bipartite biregular cage is a bipartite biregular \((m,n;g)\)-graph of minimum order. \textit{S. Filipovski} et al. [Discrete Math. 342, No. 7, 2066--2076 (2019; Zbl 1479.05170)] present lower bounds on the orders of bipartite biregular \((m,n;g)\)-graphs, and call the graphs that attain these bounds bipartite biregular Moore cages. In our paper, we improve the lower bounds obtained in the above paper. Furthermore, in parallel with the well-known classical results relating the existence of \(k\)-regular Moore graphs of even girths \(g=6,8\), and 12 to the existence of projective planes, generalized quadrangles, and generalized hexagons, we prove that the existence of an \(S(2,k,\nu)\)-Steiner system yields the existence of a bipartite biregular \(\left(k,\frac{\nu-1}{k-1};6\right)\)-cage, and, vice versa, the existence of a bipartite biregular \((k,n;6)\)-cage whose order is equal to one of our lower bounds yields the existence of an \(S(2,k,1+n(k-1))\)-Steiner system. Moreover, with regard to the special case of Steiner triple systems, we completely solve the problem of determining the orders of \((3,n;6)\)-bipartite biregular cages for all integers \(n\ge 4\). Considering girths higher than 6, we relate the existence of generalized polygons (quadrangles, hexagons, and octagons) to the existence of \((n+1,n^2+1;8)\)-, \((n^2+1,n^3+1;8)\)-, \((n,n+2;8)\)-, \((n+1,n^3+1;12)\)- and \((n+1,n^2+1;16)\)-bipartite biregular cages, respectively. Using this connection, we also derive improved upper bounds for the orders of other classes of bipartite biregular cages of girths 8, 12, and 14.Integer superharmonic matrices on the \(F\)-latticehttps://zbmath.org/1532.050462024-05-13T19:39:47.825584Z"Bou-Rabee, Ahmed"https://zbmath.org/authors/?q=ai:bou-rabee.ahmedSummary: We prove that the set of quadratic growths achievable by integer superharmonic functions on the \(F\)-lattice, a periodic subgraph of the square lattice with oriented edges, has the structure of an overlapping circle packing. The proof recursively constructs a distinct pair of recurrent functions for each rational point on a hyperbola. This proves a conjecture of \textit{C. K. Smart} [``AIM chip firing 2013: the \(F\)-lattice'', Preprint] and completely describes the scaling limit of the Abelian sandpile on the \(F\)-lattice.2-distance coloring of planar graphs without adjacent 5-cycleshttps://zbmath.org/1532.050472024-05-13T19:39:47.825584Z"Bu, Yuehua"https://zbmath.org/authors/?q=ai:bu.yuehua"Zhang, Zewei"https://zbmath.org/authors/?q=ai:zhang.zewei"Zhu, Hongguo"https://zbmath.org/authors/?q=ai:zhu.hongguoSummary: The \(k\)-\(2\)-distance coloring of graph \(G\) is a mapping \(c:V(G)\rightarrow \{1,2,\ldots, k\}\) such that any two vertices at distance at most two from each other get different colors. The 2-distance chromatic number is the smallest integer \(k\) such that \(G\) has a \(k\)-\(2\)-distance coloring, denoted by \(\chi_2 (G)\). In this paper, we prove that every planar graph \(G\) without adjacent 5-cycles and \(g(G)\geq 5\) and \(\Delta (G)\geq 17\) has \(\chi_2 (G)\leq \Delta +3\).Non-existence of annular separators in geometric graphshttps://zbmath.org/1532.050482024-05-13T19:39:47.825584Z"Ebrahimnejad, Farzam"https://zbmath.org/authors/?q=ai:ebrahimnejad.farzam"Lee, James R."https://zbmath.org/authors/?q=ai:lee.james-rSummary: \textit{I. Benjamini} and \textit{P. Papasoglu} [Proc. Am. Math. Soc. 139, No. 11, 4105--4111 (2011; Zbl 1241.53035)] showed that planar graphs with uniform polynomial volume growth admit 1-dimensional annular separators: The vertices at graph distance \(R\) from any vertex can be separated from those at distance \(2R\) by removing at most \(O(R)\) vertices. They asked whether geometric \(d\)-dimensional graphs with uniform polynomial volume growth similarly admit \((d-1)\)-dimensional annular separators when \(d>2\). We show that this fails in a strong sense: For any \(d \geq 3\) and every \(s \geq 1\), there is a collection of interior-disjoint spheres in \(\mathbb{R}^d\) whose tangency graph \(G\) has uniform polynomial growth, but such that all annular separators in \(G\) have cardinality at least \(R^s\).On the enumeration of plane bipolar posets and transversal structureshttps://zbmath.org/1532.050492024-05-13T19:39:47.825584Z"Fusy, Éric"https://zbmath.org/authors/?q=ai:fusy.eric"Narmanli, Erkan"https://zbmath.org/authors/?q=ai:narmanli.erkan"Schaeffer, Gilles"https://zbmath.org/authors/?q=ai:schaeffer.gillesSummary: We show that plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) and transversal structures can be set in correspondence to certain (weighted) models of quadrant walks, via suitable specializations of a bijection due to \textit{R. Kenyon} et al. [Ann. Probab. 47, No. 3, 1240--1269 (2019; Zbl 1466.60170)]. We then derive exact and asymptotic counting results. In particular we prove (computationally and then bijectively) that the number of plane bipolar posets on \(n + 2\) vertices equals the number of plane permutations (i.e., avoiding the vincular pattern \(2\underbrace{14}3\)) of size \(n\). Regarding transversal structures, for each \(v \geq 0\) we consider \(t_n ( v )\) the number of such structures with \(n + 4\) vertices and weight \(v\) per quadrangular inner face (the case \(v = 0\) corresponds to having only triangular inner faces). We obtain a recurrence to compute \(t_n ( v )\), and an asymptotic formula that for \(v = 0\) gives \(t_n ( 0 ) \sim c ( 27 / 2 )^n n^{- 1 - \pi / \arccos ( 7 / 8 )}\) for some \(c > 0\), which also ensures that the associated generating function is not D-finite.Intersecting diametral balls induced by a geometric graphhttps://zbmath.org/1532.050502024-05-13T19:39:47.825584Z"Pirahmad, Olimjoni"https://zbmath.org/authors/?q=ai:pirahmad.olimjoni"Polyanskii, Alexandr"https://zbmath.org/authors/?q=ai:polyanskii.aleksandr-a"Vasilevskii, Alexey"https://zbmath.org/authors/?q=ai:vasilevskii.alexeySummary: For a graph whose vertex set is a finite set of points in the Euclidean \(d\)-space consider the closed (open) balls with diameters induced by its edges. The graph is called \(a\) (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of halving lines, we show that (i) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; (ii) for any \(n\) red and \(n\) blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Also, we prove that (iii) for any even set of points in the Euclidean \(d\)-space, there exists a perfect matching that is an open Tverberg graph; (iv) for any \(n\) red and \(n\) blue points in the Euclidean \(d\)-space, there exists a perfect red-blue matching that is a Tverberg graph.Planar graphs with the maximum number of induced 6-cycleshttps://zbmath.org/1532.050512024-05-13T19:39:47.825584Z"Savery, Michael"https://zbmath.org/authors/?q=ai:savery.michaelSummary: For large \(n\) we determine the maximum number of induced 6-cycles which can be contained in a planar graph on \(n\) vertices, and we classify the graphs which achieve this maximum. In particular we show that the maximum is achieved by the graph obtained by blowing up three pairwise non-adjacent vertices in a 6-cycle to sets of as even size as possible, and that every extremal example closely resembles this graph. This extends previous work by the author [``Planar graphs with the maximum number of induced 4-cycles or 5-cycles'', Preprint, \url{arXiv:2108.00526}] which solves the problem for 4-cycles and 5-cycles. The 5-cycle problem was also solved independently by \textit{D. Ghosh} et al. [J. Graph Theory 99, No. 3, 378--398 (2022; Zbl 1522.05206)].The crossing number of the generalized Petersen graph \(P(3k, k)\) in the projective planehttps://zbmath.org/1532.050522024-05-13T19:39:47.825584Z"Wang, Jing"https://zbmath.org/authors/?q=ai:wang.jing.3"Zhang, Zuozheng"https://zbmath.org/authors/?q=ai:zhang.zuozhengSummary: The crossing number of a graph \(G\) in a surface \(\Sigma\), denoted by \(cr_{\Sigma}(G)\), is the minimum number of pairwise intersections of edges in a drawing of \(G\) in \(\Sigma\). Let \(k\) be an integer satisfying \(k \geq 3\), the generalized Petersen graph \(P(3k, k)\) is the graph with vertex set \(V(P(3k, k)) = \{u_{i}, v_{i} \mid i = 1, 2, \dots, 3k\}\) and edge set \(E(P(3k, k)) = \{u_{i} u_{i + 1}, u_{i} v_{i}, v_{i} v_{k + i} \mid i = 1, 2, \dots, 3k\}\), the subscripts are read modulo \(3k\). In this paper we investigate the crossing number of \(P(3k, k)\) in the projective plane. We determine the exact value of \(cr_{N_1} (P(3k, k))\) is \(k - 2\) when \(3 \leq k \leq 7\), moreover, for \(k \geq 8\), we get that \(k - 2 \leq cr_{N_1} (P(3k, k)) \leq k - 1\).Non-crossing shortest paths lengths in planar graphs in linear timehttps://zbmath.org/1532.050532024-05-13T19:39:47.825584Z"Balzotti, Lorenzo"https://zbmath.org/authors/?q=ai:balzotti.lorenzo"Franciosa, Paolo G."https://zbmath.org/authors/?q=ai:franciosa.paolo-giulioSummary: Given a plane graph it is known how to compute the union of non-crossing shortest paths. These algorithms do not allow neither to list each single shortest path nor to compute length of shortest paths. Given the union of non-crossing shortest paths, we introduce the concept of shortcuts that allows us to establish whether a path is a shortest path by checking local properties on faces of the graph. By using shortcuts we can compute the length of each shortest path, given their union, in total linear time, and we can list each shortest path \(p\) in \(O(\max \{\ell, \ell \log \log \frac{k}{\ell}\})\), where \(\ell\) is the number of edges in \(p\) and \(k\) the number of shortest paths.The oriented diameter of graphs with given connected domination number and distance domination numberhttps://zbmath.org/1532.050542024-05-13T19:39:47.825584Z"Dankelmann, Peter"https://zbmath.org/authors/?q=ai:dankelmann.peter"Morgan, Jane"https://zbmath.org/authors/?q=ai:morgan.jane"Rivett-Carnac, Emily"https://zbmath.org/authors/?q=ai:rivett-carnac.emilySummary: Let \(G\) be a bridgeless graph. An orientation of \(G\) is a digraph obtained from \(G\) by assigning a direction to each edge. The oriented diameter of \(G\) is the minimum diameter among all strong orientations of \(G\). The connected domination number \(\gamma_c (G)\) of \(G\) is the minimum cardinality of a set \(S\) of vertices of \(G\) such that every vertex of \(G\) is in \(S\) or adjacent to some vertex of \(S\), and which induces a connected subgraph in \(G\). We prove that the oriented diameter of a bridgeless graph \(G\) is at most \(2 \gamma_c (G) +3\) if \(\gamma_c (G)\) is even and \(2 \gamma_c (G) +2\) if \(\gamma_c (G)\) is odd. This bound is sharp. For \(d \in\mathbb{N}\), the \(d\)-distance domination number \(\gamma^d (G)\) of \(G\) is the minimum cardinality of a set \(S\) of vertices of \(G\) such that every vertex of \(G\) is at distance at most \(d\) from some vertex of \(S\). As an application of a generalisation of the above result on the connected domination number, we prove an upper bound on the oriented diameter of the form \((2d+1)(d+1)\gamma^d (G)+O(d)\). Furthermore, we construct bridgeless graphs whose oriented diameter is at least \((d+1)^2 \gamma^d (G)+O(d)\), thus demonstrating that our above bound is best possible apart from a factor of about 2.On the connectivity and diameter of geodetic graphshttps://zbmath.org/1532.050552024-05-13T19:39:47.825584Z"Etgar, Asaf"https://zbmath.org/authors/?q=ai:etgar.asaf"Linial, Nati"https://zbmath.org/authors/?q=ai:linial.nathanSummary: A graph \(G\) is geodetic if between any two vertices there exists a unique shortest path. \textit{Ø. Ore} [Theory of graphs. American Mathematical Society (AMS), Providence, RI (1962; Zbl 0105.35401)] raised the challenge to characterize geodetic graphs, but despite many attempts, such characterization still seems well beyond reach. We may assume, of course, that \(G\) is 2-connected, and here we consider only graphs with no vertices of degree 1 or 2. We prove that all such graphs are, in fact 3-connected. We also construct an infinite family of such graphs of the largest known diameter, namely 5.Induced forests in some distance-regular graphshttps://zbmath.org/1532.050562024-05-13T19:39:47.825584Z"Gunderson, Karen"https://zbmath.org/authors/?q=ai:gunderson.karen"Meagher, Karen"https://zbmath.org/authors/?q=ai:meagher.karen"Morris, Joy"https://zbmath.org/authors/?q=ai:morris.joy"Pantangi, Venkata Raghu Tej"https://zbmath.org/authors/?q=ai:pantangi.venkata-raghu-tejSummary: In this article, we study the order and structure of the largest induced forests in some families of graphs. First we prove a variation of the Delsarte-Hoffman ratio bound for cocliques that gives an upper bound on the order of the largest induced forest in a graph. Next we define a canonical induced forest to be a forest that is formed by adding a vertex to a coclique and give several examples of graphs where the maximal forest is a canonical induced forest. These examples are all distance-regular graphs with the property that the Delsarte-Hoffman ratio bound for cocliques holds with equality. We conclude with some examples of related graphs where there are induced forests that are larger than a canonical forest.Unimodal eccentricity in treeshttps://zbmath.org/1532.050572024-05-13T19:39:47.825584Z"Gylfason, Jökull S."https://zbmath.org/authors/?q=ai:gylfason.jokull-snaer"Hilmarsson, Bernhard L."https://zbmath.org/authors/?q=ai:hilmarsson.bernhard-l"Tonoyan, Tigran"https://zbmath.org/authors/?q=ai:tonoyan.tigranSummary: Jordan's classic theorem states that the center of every tree (the set of minimum eccentricity vertices) forms a complete subgraph. This property, which we refer to as the ``Jordan property,'' has been established for various definitions of eccentricity, the most popular being the maximum and average distances of a vertex to the others. In this note, we consider unimodal eccentricity functions, such that in every tree, the eccentricity strictly increases along every center-to-leaf path (whose second vertex is not in the center). Unimodal eccentricity implies the Jordan property. We prove that every function of distances with appropriate convexity and monotonicity is a unimodal eccentricity function. This covers many functions of distances that have been known to satisfy the Jordan property, and many others for which the Jordan property was not known prior to this work. Most of our results hold for trees with arbitrary positive weights on edges.
{{\copyright} 2020 Wiley Periodicals LLC}On the metric dimension of bipartite graphshttps://zbmath.org/1532.050582024-05-13T19:39:47.825584Z"Jothi, M. Anandha"https://zbmath.org/authors/?q=ai:jothi.m-anandha"Sankar, K."https://zbmath.org/authors/?q=ai:sankar.krishna|sankar.krishanu-roy|sankar.kasinathanSummary: For an ordered subset \(W = \{w_1, w_2, \dots, w_k\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the ordered \(k\)-vector \(r (v | W) = (d (v, w_1), d (v, w_2), \dots, d (v, w_k))\) is called the representation of \(v\) with respect to \(W\), where \(d (v, w_i)\) is the distance between \(v\) and \(w_i\), for \(1 \leq i \leq k\). The set \(W\) is called a \textit{resolving set} of \(G\) if \(r (u | W) \neq r (v | W)\), for every pair \(u, v \in V(G)\). The minimum positive integer \(k\) for which \(G\) has a resolving set of cardinality \(k\) is the metric dimension of \(G\), denoted as \(\dim (G)\). A resolving set of \(G\) of cardinality \(\dim (G)\) is a metric basis of \(G\). For a bipartite graph \(G\), projection is defined as a graph with the vertices of one of the partite sets, where two vertices are adjacent if they have at least one common neighbor in the other partite set. In this paper, we investigate the relation between the metric dimension of a bipartite graph and its projections. Furthermore, we present some realization results for the bounds on the metric dimension of a bipartite graph.The difference between several metric dimension graph invariantshttps://zbmath.org/1532.050592024-05-13T19:39:47.825584Z"Milivojević Danas, Milica"https://zbmath.org/authors/?q=ai:milivojevic-danas.milicaIn this paper, the author mainly studies the difference between mixed metric dimension \(\beta_M(G)\) and edge metric dimension of a graph \(\beta_E(G)\). It is proved that \((\beta_m-\beta_E)(3)=1\). For \(n\geq 4\), the bounds for \((\beta_M-\beta_E)(n)\) are determined. Also, the author studies the difference between strong metric dimension \(\beta_S(G)\) and mixed metric dimension \(\beta_M(G)\) of a graph. For the range \(3\leq n \leq 6\), exact values of the difference \((\beta_S-\beta_M )(n)\) are determined and extremal graphs \(H_n^\prime\) are presented. For \(n\geq 4\), the bounds for \((\beta_S-\beta_M)(n)\) are determined.
Reviewer: K. Ganesamoorthy (Coimbatore)On the metric representation of the vertices of a graphhttps://zbmath.org/1532.050602024-05-13T19:39:47.825584Z"Mora, Mercè"https://zbmath.org/authors/?q=ai:mora.merce"Puertas, María Luz"https://zbmath.org/authors/?q=ai:puertas.maria-luzLet \(G\) be a connected graph with vertex set \(V(G)\) and let \(d(u,w)\) denote the minimum number of edges connecting vertices \(u\) and \(w\) in \(G\). For an ordered set \(S=\{u_1, u_2, \ldots, u_k\}\subseteq V(G)\), the metric code of a vertex \(w\in V(G)\) with respect to \(S\), denoted by \(\operatorname{code}_G(w,S)\), is the \(k\)-vector \((d(w, u_1), d(w, u_2), \ldots, d(w, u_k))\).
A set \(S\subseteq V(G)\) is a resolving set of \(G\) if, for any pair of distinct vertices \(x,y\in V(G)\), there exists \(z\in S\) such that \(d(x,z)\neq d(y,z)\). A set \(S\subseteq V(G)\) is a strong resolving set of \(G\) if, for any pair of distinct vertices \(x,y\in V(G)\), there exists \(z\in S\) such that either \(x\) lies on a shortest \(y-z\) path or \(y\) lies on a shortest \(x-z\) path in \(G\).
\textit{A. Sebö} and \textit{E. Tannier} [Math. Oper. Res. 29, No. 2, 383--393 (2004; Zbl 1082.05032)] provide an example showing that there exist non-isomorphic graphs \(G_1\) and \(G_2\) on a common vertex set \(V\) with a common resolving set \(S\subseteq V\) such that \(\operatorname{code}_{G_1}(w, S)=\operatorname{code}_{G_2}(w, S)\) for each vertex \(w\in V\). On the other hand, Sebö and Tannier [loc. cit.] state that if \(S\) is a strong resolving set of a graph, the collection \(\{\operatorname{code}_G(w, S): w\in V(G)\}\) uniquely determines a graph \(G\); a proof for this claim is provided by \textit{C. X. Kang} and \textit{E. Yi} [Lect. Notes Comput. Sci. 8287, 84--95 (2013; Zbl 1407.05078)].
The authors of the current paper attempt to answer the following questions:
\begin{itemize}
\item[(1)] Is a finite subset \(\mathcal{C} \subseteq \mathbb{Z}^n\) realizable as a set of metric codes of a graph \(G\) with respect to a resolving set \(S\)?
\item[(2)] If the set \(\mathcal{C}\subseteq \mathbb{Z}^n\) is realizable, does \(\mathcal{C}\) uniquely determine a graph?
\end{itemize}
The authors provide an answer to (1) by characterizing the conditions for which \(\{\operatorname{code}_G(w, S): w\in V(G)\}\) is a realizable set of a graph with respect to a resolving \(S\). Regarding (2), the authors characterize the collection \(\mathcal{C}=\{\operatorname{code}_G(w, S): w\in V(G)\}\) that are uniquely realizable when \(|S|=2\).
Reviewer: Eunjeong Yi (Galveston)Chromatic polynomials of 2-edge-coloured graphshttps://zbmath.org/1532.050612024-05-13T19:39:47.825584Z"Beaton, Iain"https://zbmath.org/authors/?q=ai:beaton.iain"Cox, Danielle"https://zbmath.org/authors/?q=ai:cox.danielle"Duffy, Christopher"https://zbmath.org/authors/?q=ai:duffy.christopher"Zolkavich, Nicole"https://zbmath.org/authors/?q=ai:zolkavich.nicoleSummary: Using the definition of colouring of \(2\)-edge-coloured graphs derived from 2-edge-coloured graph homomorphism, we extend the definition of chromatic polynomial to 2-edge-coloured graphs. We find closed forms for the first three coefficients of this polynomial that generalize the known results for the chromatic polynomial of a graph. We classify those graphs that admit a 2-edge-colouring for which the chromatic polynomial of the graph and the chromatic polynomial of the 2-edge-colouring is equal. Finally, we examine the behaviour of the roots of this polynomial, highlighting behaviours not seen in chromatic polynomials of graphs.Separating the online and offline DP-chromatic numbershttps://zbmath.org/1532.050622024-05-13T19:39:47.825584Z"Bradshaw, Peter"https://zbmath.org/authors/?q=ai:bradshaw.peter-t-j|bradshaw.peter-a|bradshaw.peter-jSummary: The DP-coloring problem is a generalization of the list-coloring problem in which the goal is to find an independent transversal in a certain topological cover of a graph \(G\). In the online DP-coloring problem, the cover of \(G\) is revealed one component at a time, and the independent transversal of the cover must be constructed in parts based on incomplete information. \textit{S.-J. Kim} et al. [Discrete Appl. Math. 285, 443--453 (2020; Zbl 1447.05086)] asked whether the chromatic numbers corresponding to these two graph coloring problems can have an arbitrarily large difference in a single graph. We answer this question in the affirmative by constructing graphs for which the gap between the online DP-chromatic number and the offline DP-chromatic number is arbitrarily large.Borodin-Kostochka conjecture holds for odd-hole-free graphshttps://zbmath.org/1532.050632024-05-13T19:39:47.825584Z"Chen, Rong"https://zbmath.org/authors/?q=ai:chen.rong"Lan, Kaiyang"https://zbmath.org/authors/?q=ai:lan.kaiyang"Lin, Xinheng"https://zbmath.org/authors/?q=ai:lin.xinheng"Zhou, Yidong"https://zbmath.org/authors/?q=ai:zhou.yidongSummary: The Borodin-Kostochka Conjecture states that for a graph \(G\), if \(\Delta (G)\geq 9\), then \(\chi (G)\leq \max \{\Delta (G)-1,\omega (G)\}\). In this paper, we prove the Borodin-Kostochka Conjecture holding for odd-hole-free graphs.On the chromatic number of 2-dimensional sphereshttps://zbmath.org/1532.050642024-05-13T19:39:47.825584Z"Cherkashin, Danila"https://zbmath.org/authors/?q=ai:cherkashin.danila-d"Voronov, Vsevolod"https://zbmath.org/authors/?q=ai:voronov.vsevolod-aleksandrovichSummary: \textit{G. J. Simmons} [J. Aust. Math. Soc., Ser. A 21, 473--480 (1976; Zbl 0333.52011)] conjectured that every coloring of a 2-dimensional sphere of radius strictly greater than 1/2 in three colors has a pair of monochromatic points at distance 1 apart. We prove this conjecture.On the chromatic number of some generalized Kneser graphshttps://zbmath.org/1532.050652024-05-13T19:39:47.825584Z"D'haeseleer, Jozefien"https://zbmath.org/authors/?q=ai:dhaeseleer.jozefien"Metsch, Klaus"https://zbmath.org/authors/?q=ai:metsch.klaus"Werner, Daniel"https://zbmath.org/authors/?q=ai:werner.danielSummary: We determine the chromatic number of the Kneser graph \(q\Gamma_{7,\{3,4\}}\) of flags of vectorial type \(\{3,4\}\) of a rank 7 vector space over the finite field \(\text{GF}(q)\) for large \(q\) and describe the colorings that attain the bound. This result relies heavily, not only on the independence number, but also on the structure of all large independent sets. Furthermore, our proof is more general in the following sense: it provides the chromatic number of the Kneser graphs \(q\Gamma_{2d+1,\{d,d+1\}}\) of flags of vectorial type \(\{d,d+1\}\) of a rank \(2d+1\) vector space over \(\text{GF}(q)\) for large \(q\) as long as the large independent sets of the graphs are only the ones that are known.
{{\copyright} 2023 Wiley Periodicals LLC.}Total colorings -- a surveyhttps://zbmath.org/1532.050662024-05-13T19:39:47.825584Z"Geetha, Jayabalan"https://zbmath.org/authors/?q=ai:geetha.jayabalan"Narayanan, Narayanan"https://zbmath.org/authors/?q=ai:narayanan.narayanan"Somasundaram, Kanagasabapathi"https://zbmath.org/authors/?q=ai:somasundaram.kanagasabapathiSummary: The smallest integer \(k\) needed for the assignment of \(k\) colors to the elements so that the coloring is proper (vertices and edges) is called the total chromatic number of a graph. \textit{V. G. Vizing} [``On an estimate of the chromatic class of a \(p\)-graph'', Diskret. Analiz 3, 25--30 (1964)] and \textit{M. Behzad} [Graphs and their chromatic numbers. East Lansing, MI: Michigan State University (PhD Thesis) (1965)] conjectured that the total coloring can be done using at most \(\Delta(G) + 2\) colors, where \(\Delta(G)\) is the maximum degree of \(G\). It is not settled even for planar graphs. In this paper, we give a survey on the total coloring of graphs.Generalized Heawood numbershttps://zbmath.org/1532.050672024-05-13T19:39:47.825584Z"Kühnel, Wolfgang"https://zbmath.org/authors/?q=ai:kuhnel.wolfgangSummary: This survey explains the origin and the further development of the Heawood inequalities, the Heawood number, and generalizations to higher dimensions with results and further conjectures.On the AVDTC of Sierpiński-type graphshttps://zbmath.org/1532.050682024-05-13T19:39:47.825584Z"Palma, Miguel A. D. R."https://zbmath.org/authors/?q=ai:palma.miguel-a-d-r"León, Adriana J."https://zbmath.org/authors/?q=ai:leon.adriana-j"Dantas, Simone"https://zbmath.org/authors/?q=ai:dantas.simoneSummary: The Adjacent-Vertex-Distinguishing Total Coloring (AVDTC) conjecture asserts that every simple graph can be colored with an AVDTC using at most \(\varDelta + 3\) colors. We show that this conjecture is satisfied for all the Sierpiński graphs \(S_p^n\), their regularizations \(+ S_p^n\) and \(+ + S_p^n\) and the fractals obtained as limit space of these graphs. Moreover, we construct explicit total colorings (with at most \(\varDelta + 2\) colors) for Sierpiński triangles graphs \(ST_p^n\) and Sierpiński triangle fractal with the limit space \(ST_p^\infty\), for \(p \in \{3, 4, 5, 6\}\), and prove that the AVDTC conjecture is also valid for these cases.On graphs with equal coprime index and clique numberhttps://zbmath.org/1532.050692024-05-13T19:39:47.825584Z"Patil, Chetan"https://zbmath.org/authors/?q=ai:patil.chetan"Khandekar, Nilesh"https://zbmath.org/authors/?q=ai:khandekar.nilesh"Joshi, Vinayak"https://zbmath.org/authors/?q=ai:joshi.vinayak-vSummary: Recently, \textit{S. A. Katre} et al. [Electron. Notes Discrete Math. 60, 77--82 (2017; Zbl 1377.05172)] introduced the concept of the coprime index of a graph. They asked to characterize the graphs for which the coprime index is the same as the clique number. In this paper, we partially solve this problem. In fact, we prove that the clique number and the coprime index of a zero-divisor graph of an ordered set and the zero-divisor graph of a ring \(\mathbb{Z}_{p^n}\) coincide. Also, it is proved that the annihilating ideal graphs, the co-annihilating ideal graphs and the comaximal ideal graphs of commutative rings can be realized as the zero-divisor graphs of specially constructed posets. Hence the coprime index and the clique number coincide for these graphs as well.Burling graphs revisited. II: Structurehttps://zbmath.org/1532.050702024-05-13T19:39:47.825584Z"Pournajafi, Pegah"https://zbmath.org/authors/?q=ai:pournajafi.pegah"Trotignon, Nicolas"https://zbmath.org/authors/?q=ai:trotignon.nicolasSummary: The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Any induced subgraph of a graph in this sequence is called a Burling graph. These graphs have attracted some attention because on one hand they have geometric representations, and on the other hand they provide counter-examples to several conjectures about bounding the chromatic number in classes of graphs. Using an equivalent definition from the first part of this work (called derived graphs), we study several structural properties of Burling graphs. In particular, we give decomposition theorems for the class using in-star cutsets, study holes and their interactions in Burling graphs, and analyze the effect of subdividing some arcs of a Burling graph. Using mentioned results, we introduce new techniques for providing new triangle-free graph that are not Burling graphs. Among other applications, we prove that wheels are not Burling graphs. This answers an open problem of the second author [``Perfect graphs: a survey'', Preprint, arXiv:1301.5149 [math.CO] (2013)] and disproves a conjecture of \textit{A. Scott} and \textit{P. Seymour} [personal communication (2017)].Burling graphs revisited. III: Applications to \(\chi \)-boundednesshttps://zbmath.org/1532.050712024-05-13T19:39:47.825584Z"Pournajafi, Pegah"https://zbmath.org/authors/?q=ai:pournajafi.pegah"Trotignon, Nicolas"https://zbmath.org/authors/?q=ai:trotignon.nicolasSummary: The Burling sequence is a sequence of triangle-free graphs of unbounded chromatic number. The class of Burling graphs consists of all the induced subgraphs of the graphs of this sequence. In the first and second parts of this work, we introduced derived graphs, a class of graphs, equal to the class of Burling graphs, and proved several geometric and structural results about them. In this third part, we use those results to find some Burling and non-Burling graphs, and we see some applications of this in the theory of \(\chi \)-boundedness. Specifically, we show that several graphs, like \(K_5\), some series-parallel graphs that we call necklaces, and some other graphs are not weakly pervasive.
For Part II see [the authors, ibid. 116, Article ID 103849, 24 p. (2024; Zbl.07799818)].Rainbow clique subdivisionshttps://zbmath.org/1532.050722024-05-13T19:39:47.825584Z"Wang, Yan"https://zbmath.org/authors/?q=ai:wang.yan.204|wang.yan.200|wang.yan.127|wang.yan.209|wang.yan.138|wang.yan.214|wang.yan.13|wang.yan.128|wang.yan.111|wang.yan.32|wang.yan.179|wang.yan.103|wang.yan.7|wang.yan.201|wang.yan.2|wang.yan.121|wang.yan.118|wang.yan.206|wang.yan.159|wang.yan.205|wang.yan.163|wang.yan.186|wang.yan.41|wang.yan.151|wang.yan.105|wang.yan.213|wang.yan.49|wang.yan.202|wang.yan.169|wang.yan.207|wang.yan.36|wang.yan.58|wang.yan.27|wang.yan.211|wang.yan.208|wang.yan.19|wang.yan.18|wang.yan.212|wang.yan.12|wang.yan.42|wang.yan.203|wang.yan.47|wang.yan.28|wang.yan.1|wang.yan.3|wang.yan.34|wang.yan.14|wang.yan.57|wang.yan|wang.yan.144|wang.yan.210|wang.yan.52|wang.yan.142|wang.yan.145|wang.yan.59|wang.yan.53|wang.yan.35Summary: We show that for any integer \(t \geq 2\), every properly edge colored \(n\)-vertex graph with average degree at least \(( \log n )^{2 + o ( 1 )}\) contains a rainbow subdivision of a complete graph of size \(t\). Note this bound is within \(( \log n )^{1 + o ( 1 )}\) factor of the lower bound. This also implies a result on the rainbow Turán number of cycles.Strongly perfect claw-free graphs -- a short proofhttps://zbmath.org/1532.050732024-05-13T19:39:47.825584Z"Chudnovsky, Maria"https://zbmath.org/authors/?q=ai:chudnovsky.maria"Dibek, Cemil"https://zbmath.org/authors/?q=ai:dibek.cemilA graph is strongly perfect if every induced subgraph \(H\) of it has a stable set that meets every maximal clique of \(H\). A graph is claw-free if no vertex has three nonadjacent neighbors. \textit{G. Ravindra} [Discrete Math. 80, No. 1, 105--109 (1990; Zbl 0722.05053)] conjectured that claw-free strongly perfect graphs can be characterized by a specific set of forbidden induced subgraphs. This conjecture was proved by \textit{H.-Y. Wang} [ibid. 306, No. 19--20, 2602--2629 (2006; Zbl 1103.05035)]. The paper gives a short proof of Wang's result.
Reviewer: Eckhard Steffen (Paderborn)The existence of partitioned balanced tournament designshttps://zbmath.org/1532.050742024-05-13T19:39:47.825584Z"Araya, Makoto"https://zbmath.org/authors/?q=ai:araya.makoto"Tokihisa, Naoya"https://zbmath.org/authors/?q=ai:tokihisa.naoyaSummary: \textit{E. R. Lamken} [in: The CRC handbook of combinatorial designs. Boca Raton, FL: CRC Press. 238--241 (1996; Zbl 0849.05018)] proved that there exists a partitioned balanced tournament design of side \(n\), PBTD\((n)\), for \(n\) a positive integer, \(n\ge 5\), except possibly for \(n\in \{9,11,15\}\). In this article, we establish the existence of PBTD\((n)\) for \(n\in \{9,11,15\}\). As a consequence, the existence of PBTD\((n)\) has now been completely determined.Safe sets and in-dominating sets in digraphshttps://zbmath.org/1532.050752024-05-13T19:39:47.825584Z"Bai, Yandong"https://zbmath.org/authors/?q=ai:bai.yandong"Bang-Jensen, Jørgen"https://zbmath.org/authors/?q=ai:bang-jensen.jorgen"Fujita, Shinya"https://zbmath.org/authors/?q=ai:fujita.shinya"Ono, Hirotaka"https://zbmath.org/authors/?q=ai:ono.hirotaka"Yeo, Anders"https://zbmath.org/authors/?q=ai:yeo.andersSummary: A non-empty subset \(S\) of the vertices of a digraph \(D\) is a safe set if
\begin{itemize}
\item[(i)] for every strongly connected component \(M\) of \(D - S\), there exists a strongly connected component \(N\) of \(D [S]\) such that there exists an arc from \(M\) to \(N\); and
\item[(ii)] for every strongly connected component \(M\) of \(D - S\) and every strongly connected component \(N\) of \(D [S]\), we have \(|M| \leq |N|\) whenever there exists an arc from \(M\) to \(N\).
\end{itemize}
In the case of acyclic digraphs a set \(X\) of vertices is a safe set precisely when \(X\) is an in-dominating set, that is, every vertex not in \(X\) has at least one arc to \(X\). We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality safe (in-dominating) set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant \(c\), a polynomial algorithm for finding a minimum cardinality safe set in a tournament on \(n\) vertices in which no strong component has size more than \(c \log (n)\). Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every \(\epsilon > 0\) there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most \(\log^{1 + \epsilon} (n)\). We also discuss bounds on the cardinality of safe sets in tournaments.Digraph redicolouringhttps://zbmath.org/1532.050762024-05-13T19:39:47.825584Z"Bousquet, N."https://zbmath.org/authors/?q=ai:bousquet.nicolas"Havet, F."https://zbmath.org/authors/?q=ai:havet.frederic"Nisse, N."https://zbmath.org/authors/?q=ai:nisse.nicolas"Picasarri-Arrieta, L."https://zbmath.org/authors/?q=ai:picasarri-arrieta.lucas"Reinald, A."https://zbmath.org/authors/?q=ai:reinald.amadeusThe authors extend several known tough results concerning dicoloring of graphs and also raise some new conjectures. First, they establish that given two $k$-dicolourings of a digraph $D$, it is PSPACE-complete to decide whether one can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring at any step even for $k=2$ and for digraphs with maximum degree 5 or oriented planar graphs with maximum degree 6. They pose a new conjecture which is an analogue of Cereceda's conjecture for digraphs [\textit{L. Cereceda}, Mixing graph colourings. London: London School of Economics and Political Science (PhD Thesis) (2007)] and generalized it to digraphs with two new results supporting Cereceda's conjecture. Further, for the restricted version of oriented graphs, they prove that the dicolouring graph of any subcubic oriented graph on $k\geq 2$ colours is connected and has diameter at most $2n$. They also raise an open conjecture namely ``every non-2-mixing oriented graph has a maximum average degree of at least 4'' to the graph theory community by proving it for the special case of 2-freezable oriented graphs. They also show that every $k$-freezable oriented graph on \(n\) vertices must contain at least $kn + k(k-2)$ arcs and a family of $k$-freezable oriented graphs that reach this bound. For the general case, they prove a partial result that every non-2-mixing oriented graph has maximum average degree of at least 7.2.
Reviewer: V. Yegnanarayanan (Chennai)The structure of power digraph connected with the congruence \(a^{11}\equiv b\pmod{n}\)https://zbmath.org/1532.050772024-05-13T19:39:47.825584Z"Goswami, Pinkimani"https://zbmath.org/authors/?q=ai:goswami.pinkimani"Thakur, Sanjay Kumar"https://zbmath.org/authors/?q=ai:thakur.sanjay-kumar"Ray, Gautam Chandra"https://zbmath.org/authors/?q=ai:ray.gautam-chandraSummary: We assign to each positive integer \(n\) a digraph \(\Gamma(n, 11)\) whose set of vertices is \(\mathbb{Z}_n = \{0, 1, 2,\dots, n-1\}\) and there exists exactly one directed edge from \(a\) to \(b\) if and only if \(a^{11} \equiv b\pmod{n}\), where \(a, b \in \mathbb{Z}_n\). Let \(\Gamma_1(n, 11)\) be the subdigraph induced by the vertices which are coprime to \(n\). We discuss when the subdigraph \(\Gamma_1(n, 11)\) is regular or semi-regular. A formula for the number of fixed points of \(\Gamma(n, 11)\) is established. A necessary and sufficient condition for the symmetry of the digraph \(\Gamma(n, 11)\) is proved. Moreover, using Carmichaelś lambda function, the number of components and conditions for the existence of cycles in the digraph \(\Gamma(n, 11)\) is presented.Additively graceful signed graphshttps://zbmath.org/1532.050782024-05-13T19:39:47.825584Z"Pereira, Jessica"https://zbmath.org/authors/?q=ai:pereira.jessica"Singh, Tarkeshwar"https://zbmath.org/authors/?q=ai:singh.tarkeshwar.1"Arumugam, S."https://zbmath.org/authors/?q=ai:arumugam.subramanian|arumugam.sivabalan|arumugam.saravanan|arumugam.senthil-m|arumugam.sivaprakasamSummary: Let \(S = (V, E, \sigma)\) be a signed graph of order \(p\) and size \(q\). Let \(E^{+} : \{e \in E : \sigma (e) = +\}\), \(E^{-} = \{e \in E :\sigma (e) = -\}\), \(|E^{+}| = m\) and \(|E^{-}| = n\). Let \(f : V \to \{0, 1, 2, \cdots + \lceil \frac{n + 1}{2} \rceil\}\) be an injective function and let
\[
g_{f} (uv) =
\begin{cases}
|f (u) - f (v)| &\text{if } uv \in E^{+} \\
f (u) + f (v) & \text{if } uv \in E^{-}
\end{cases}
\]
The function \(f\) is called an additively graceful labeling of \(S\) if \(g_{f}(E^{+}) = \{1, 2, \dots, m\}\) and \(g_{f} (E^{-}) = \{1, 2, \dots, n\}\). In this paper we investigate the existence of additively graceful labeling of several classes of signed graphs.Short proof of the asymptotic confirmation of the Faudree-Lehel conjecturehttps://zbmath.org/1532.050792024-05-13T19:39:47.825584Z"Przybyło, Jakub"https://zbmath.org/authors/?q=ai:przybylo.jakub"Wei, Fan"https://zbmath.org/authors/?q=ai:wei.fan|wei.fan.1Summary: Given a simple graph \(G\), the irregularity strength of \(G\), denoted \(s(G)\), is the least positive integer \(k\) such that there is a weight assignment on edges \(f: E(G) \to \{1, 2, \dots, k\}\) for which each vertex weight \(f^V(v):= \sum_{u: \{u, v\} \in E(G)} f (\{u ,v\})\) is unique amongst all \(v\in V(G)\). In [in: Combinatorics. Proceedings of the 7th Hungarian colloquium held from July 5 to July 10, 1987 in Eger, Hungary. Amsterdam etc.: North-Holland; Budapest: János Bolyai Mathematical Society. 247--256 (1988; Zbl 0697.05048)], \textit{R. J. Faudree} and \textit{J. Lehel} conjectured that there is a constant \(c\) such that \(s(G) \leqslant n/d + c\) for all \(d\)-regular graphs \(G\) on \(n\) vertices with \(d>1\), whereas it is trivial that \(s(G) \geqslant n/d\). In this short note we prove that the Faudree-Lehel Conjecture holds when \(d \geqslant n^{0.8+\epsilon}\) for any fixed \(\epsilon >0\), with a small additive constant \(c=28\) for \(n\) large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed \(\beta\in(0,1/4)\) there is a constant \(C\) such that for all \(d\)-regular graphs \(G, s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28\), extending and improving a recent result of \textit{J. Przybyło} [J. Graph Theory 100, No. 1, 189--204 (2022; Zbl 1522.05406)] that \(s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})\) whenever \(d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]\) and \(n\) is large enough.On independence polynomials of quotient based graphs for finite abelian groupshttps://zbmath.org/1532.050802024-05-13T19:39:47.825584Z"Kiri, A. I."https://zbmath.org/authors/?q=ai:kiri.aliyu-ibrahim"Suleiman, A."https://zbmath.org/authors/?q=ai:suleiman.abbasSummary: In this paper we investigated the independence polynomial of quotient based graph \(\varphi_H (G)\) of an abelian group \(G\) relative to all it's subgroups since a subgroup \(H\) of an abelian group is normal . The graph \(\varphi_H (G)\) is a graph with condition of adjacency where two distinct elements \(x\), \(y \in G\) are adjacent in the graph iff \(xy \notin H\). A formula for computing the independence polynomial is obtained.Binomial edge ideals of weakly closed graphshttps://zbmath.org/1532.050812024-05-13T19:39:47.825584Z"Seccia, Lisa"https://zbmath.org/authors/?q=ai:seccia.lisaSummary: Closed graphs have been characterized by \textit{J. Herzog} et al. [Adv. Appl. Math. 45, No. 3, 317--333 (2010; Zbl 1196.13018)] as the graphs whose binomial edge ideals have a quadratic Gröbner basis with respect to a diagonal term order. In this paper, we focus on a generalization of closed graphs, namely weakly closed graphs (or co-comparability graphs). Building on some results about Knutson ideals of generic matrices, we characterize weakly closed graphs as the only graphs whose binomial edge ideals are Knutson ideals for a certain polynomial \(f\). In doing so, we re-prove \textit{K. Matsuda}'s theorem [Algebra Colloq. 25, No. 4, 567--578 (2018; Zbl 1401.05139)] about the F-purity of binomial edge ideals of weakly closed graphs in positive characteristic and we extend it to generalized binomial edge ideals. Furthermore, we give a characterization of weakly closed graphs in terms of the minimal primes of their binomial edge ideals and we characterize all minimal primes of Knutson ideals for this choice of \(f\).A graph with a locally projective vertex-transitive group of automorphisms \(\Aut(\mathrm{Fi}_{22})\) which has a nontrivial stabilizer of a ball of radius 2https://zbmath.org/1532.050822024-05-13T19:39:47.825584Z"Trofimov, V. I."https://zbmath.org/authors/?q=ai:trofimov.vladimir-iSummary: Earlier, to confirm that one of the possibilities for the structure of vertex stabilizers of graphs with projective suborbits is realizable, we announced [the author, in: Groups, combinatorics and geometry. Proceedings of the L. M. S. Durham symposium, Durham, UK, July 16--26, 2001. River Edge, NJ: World Scientific. 313--326 (2003; Zbl 1039.05033)] the existence of a connected graph \(\Gamma\) admitting a group of automorphisms \(G\) which is isomorphic to \(\Aut(\mathrm{Fi}_{22})\) and has the following properties. First, the group \(G\) acts transitively on the set of vertices of \(\Gamma \), but intransitively on the set of 3-arcs of \(\Gamma \). Second, the stabilizer in \(G\) of a vertex of \(\Gamma\) induces on the neighborhood of this vertex a group \(\mathrm{PSL}_3(3)\) in its natural doubly transitive action. Third, the pointwise stabilizer in \(G\) of a ball of radius 2 in \(\Gamma\) is nontrivial. In this paper, we construct such a graph \(\Gamma\) with \(G=\Aut(\Gamma)\).Perfect state transfer on quasi-abelian semi-Cayley graphshttps://zbmath.org/1532.050832024-05-13T19:39:47.825584Z"Wang, Shixin"https://zbmath.org/authors/?q=ai:wang.shixin"Arezoomand, Majid"https://zbmath.org/authors/?q=ai:arezoomand.majid"Feng, Tao"https://zbmath.org/authors/?q=ai:feng.tao.1Summary: Perfect state transfer on graphs has attracted extensive attention due to its application in quantum information and quantum computation. A graph is a semi-Cayley graph over a group \(G\) if it admits \(G\) as a semiregular subgroup of the full automorphism group with two orbits of equal size. A semi-Cayley graph \(\mathrm{SC}(G, R, L, S)\) is called quasi-abelian if each of \(R\), \(L\) and \(S\) is a union of some conjugacy classes of \(G\). This paper establishes necessary and sufficient conditions for a quasi-abelian semi-Cayley graph to have perfect state transfer. As a corollary, it is shown that if a quasi-abelian semi-Cayley graph over a finite group \(G\) has perfect state transfer between distinct vertices \(g\) and \(h\), and \(G\) has a faithful irreducible character, then \(gh^{-1}\) lies in the center of \(G\) and \(gh=hg\); in particular, \(G\) cannot be a non-abelian simple group. We also characterize quasi-abelian Cayley graphs over arbitrary groups having perfect state transfer, which is a generalization of previous works on Cayley graphs over abelian groups, dihedral groups, semi-dihedral groups and dicyclic groups.On edge-transitive metacyclic covers of cubic arc-transitive graphs of order twice a primehttps://zbmath.org/1532.050842024-05-13T19:39:47.825584Z"Wang, Xue"https://zbmath.org/authors/?q=ai:wang.xue.1"Zhou, Jin-Xin"https://zbmath.org/authors/?q=ai:zhou.jinxin"Lee, Jaeun"https://zbmath.org/authors/?q=ai:lee.jaeunSummary: Let \(p\) be a prime, and let \(\Lambda_{2p}\) be a connected cubic arc-transitive graph of order \(2p\). In the literature, a lot of works have been done on the classification of edge-transitive normal covers of \(\Lambda_{2p}\) for specific \(p\leq 7\). An interesting problem is to generalize these results to an arbitrary prime \(p\). \textit{J.-X. Zhou} and \textit{Y.-Q. Feng} [Combinatorica 34, No. 1, 115--128 (2014; Zbl 1313.05175)] classified edge-transitive cyclic or dihedral normal covers of \(\Lambda_{2p}\) for each prime \(p\). In our previous work, we classified all edge-transitive \(N\)-normal covers of \(\Lambda_{2p}\), where \(p\) is a prime and \(N\) is a metacyclic 2-group. In this paper, we give a classification of edge-transitive \(N\)-normal covers of \(\Lambda_{2p}\), where \(p\geq 5\) is a prime and \(N\) is a metacyclic group of odd prime power order.A note on regular sets in Cayley graphshttps://zbmath.org/1532.050852024-05-13T19:39:47.825584Z"Zhang, Junyang"https://zbmath.org/authors/?q=ai:zhang.junyang"Zhu, Yanhong"https://zbmath.org/authors/?q=ai:zhu.yanhongSummary: A subset \(R\) of the vertex set of a graph \(\Gamma\) is said to be \((\kappa ,\tau)\)-regular if \(R\) induces a \(\kappa\)-regular subgraph and every vertex outside \(R\) is adjacent to exactly \(\tau\) vertices in \(R\). In particular, if \(R\) is a \((\kappa ,\tau)\)-regular set of some Cayley graph on a finite group \(G\), then \(R\) is called a \((\kappa ,\tau)\)-regular set of \(G\). Let \(H\) be a nontrivial normal subgroup of \(G\), and \(\kappa\) and \(\tau\) a pair of integers satisfying \(0\leq \kappa \leq |H|-1\), \(1\leq \tau \leq |H|\) and \(\gcd (2,|H|-1)\mid \kappa\). It is proved that (i) if \(\tau\) is even, then \(H\) is a \((\kappa ,\tau)\)-regular set of \(G\); (ii) if \(\tau\) is odd, then \(H\) is a \((\kappa ,\tau)\)-regular set of \(G\) if and only if it is a \((0,1)\)-regular set of \(G\).Graph-codeshttps://zbmath.org/1532.050862024-05-13T19:39:47.825584Z"Alon, Noga"https://zbmath.org/authors/?q=ai:alon.nogaSummary: The symmetric difference of two graphs \(G_1\), \(G_2\) on the same set of vertices \([ n ] = \{ 1 , 2 , \ldots , n \}\) is the graph on \([ n ]\) whose set of edges are all edges that belong to exactly one of the two graphs \(G_1\), \(G_2\). Let \(H\) be a fixed graph with an even (positive) number of edges, and let \(D_H ( n )\) denote the maximum possible cardinality of a family of graphs on \([ n ]\) containing no two members whose symmetric difference is a copy of \(H\). Is it true that \(D_H ( n ) = o ( 2^{\binom{n}{2}} )\) for any such \(H\)? We discuss this problem, compute the value of \(D_H ( n )\) up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.Weighted enumeration of nonbacktracking walks on weighted graphshttps://zbmath.org/1532.050872024-05-13T19:39:47.825584Z"Arrigo, Francesca"https://zbmath.org/authors/?q=ai:arrigo.francesca"Higham, Desmond J."https://zbmath.org/authors/?q=ai:higham.desmond-j"Noferini, Vanni"https://zbmath.org/authors/?q=ai:noferini.vanni"Wood, Ryan"https://zbmath.org/authors/?q=ai:wood.ryanSummary: We extend the notion of nonbacktracking walks from unweighted graphs to graphs whose edges have a nonnegative weight. Here the weight associated with a walk is taken to be the product over the weights along the individual edges. We give two ways to compute the associated generating function, and corresponding node centrality measures. One method works directly on the original graph and one uses a line graph construction followed by a projection. The first method is more efficient, but the second has the advantage of extending naturally to time-evolving graphs. Based on these generating functions, we define and study corresponding centrality measures. Illustrative computational results are also provided.Some exact results for non-degenerate generalized Turán problemshttps://zbmath.org/1532.050882024-05-13T19:39:47.825584Z"Gerbner, Dániel"https://zbmath.org/authors/?q=ai:gerbner.danielSummary: The generalized Turán number \(\text{ex}(n, H, F)\) is the maximum number of copies of \(H\) in \(n\)-vertex \(F\)-free graphs. We consider the case where \(\chi(H)<\chi(F)\). There are several exact results on \(\text{ex}(n, H, F)\) when the extremal graph is a complete \((\chi(F)-1)\)-partite graph. We obtain multiple exact results with other kinds of extremal graphs.Efficient enumeration of dominating sets for sparse graphshttps://zbmath.org/1532.050892024-05-13T19:39:47.825584Z"Kurita, Kazuhiro"https://zbmath.org/authors/?q=ai:kurita.kazuhiro"Wasa, Kunihiro"https://zbmath.org/authors/?q=ai:wasa.kunihiro"Arimura, Hiroki"https://zbmath.org/authors/?q=ai:arimura.hiroki"Uno, Takeaki"https://zbmath.org/authors/?q=ai:uno.takeakiSummary: A dominating set \(D\) of a graph \(G\) is a set of vertices such that any vertex in \(G\) is in \(D\) or its neighbor is in \(D\). Enumeration of minimal dominating sets in a graph is one of central problems in enumeration study since enumeration of minimal dominating sets corresponds to enumeration of minimal hypergraph transversal. However, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a \(k\)-degenerate graph in \(O(k)\) time per solution using \(O(n+m)\) space, where \(n\) and \(m\) are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, \(H\)-minor free graphs with some fixed \(H\). The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine.
For the entire collection see [Zbl 1407.68036].Generating functions and counting formulas for spanning trees and forests in hypergraphshttps://zbmath.org/1532.050902024-05-13T19:39:47.825584Z"Liu, Jiuqiang"https://zbmath.org/authors/?q=ai:liu.jiuqiang"Zhang, Shenggui"https://zbmath.org/authors/?q=ai:zhang.shenggui"Yu, Guihai"https://zbmath.org/authors/?q=ai:yu.guihaiSummary: In this paper, we provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs in two different ways: (1) We represent spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper-Hafnians (orders and signs are not considered); (2) We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by \textit{A. Abdesselam} [ibid. 33, No. 1, 51--70 (2004; Zbl 1052.05044)] and Pfaffian matrix tree theorem by \textit{G. Masbaum} and \textit{A. Vaintrob} [Int. Math. Res. Not. 2002, No. 27, 1397--1426 (2002; Zbl 1008.05100)].A novel count of the spanning trees of a cubehttps://zbmath.org/1532.050912024-05-13T19:39:47.825584Z"Mattman, Thomas W."https://zbmath.org/authors/?q=ai:mattman.thomas-wSummary: Using the special value at \(u=1\) of the Artin-Ihara \(L\)-function, we give a short proof of the count of the number of spanning trees in the \(n\)-cube.Enumeration of labeled series-parallel tricyclic graphshttps://zbmath.org/1532.050922024-05-13T19:39:47.825584Z"Voblyi, V. A."https://zbmath.org/authors/?q=ai:voblyi.vitalii-antonievichSummary: A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. An explicit formula for the number of labeled series-parallel tricyclic graphs with a given number of vertices is obtained, and the corresponding asymptotics for the number of such graphs with a large number of vertices is found. We prove that under a uniform probability distribution, the probability that the labeled tricyclic graph is a series-parallel graph is asymptotically equal to \(13/15\).Minimum number of maximal dissociation sets in treeshttps://zbmath.org/1532.050932024-05-13T19:39:47.825584Z"Zhang, Junxia"https://zbmath.org/authors/?q=ai:zhang.junxia"Qian, Jianguo"https://zbmath.org/authors/?q=ai:qian.jianguo"Huang, Sumin"https://zbmath.org/authors/?q=ai:huang.suminSummary: A subset of vertices \(S\) in a graph \(G\) is called a dissociation set if it induces a subgraph with vertex degree at most 1. A dissociation set of \(G\) is maximal if it is not a proper subset of any other dissociation sets. We show that every tree of order \(n \geq 3\) has at least \(\lceil n/2 \rceil + 1\) maximal dissociation sets and characterize the corresponding extremal graphs attaining this lower bound.From Abel's binomial theorem to Cayley's tree formulahttps://zbmath.org/1532.050942024-05-13T19:39:47.825584Z"Zucker, Marc"https://zbmath.org/authors/?q=ai:zucker.marcSummary: We derive Abel's generalization of the binomial theorem and use it to present a short proof of Cayley's theorem on the number of trees on \(n\) labeled vertices.Graphs without a rainbow path of length 3https://zbmath.org/1532.050952024-05-13T19:39:47.825584Z"Babiński, Sebastian"https://zbmath.org/authors/?q=ai:babinski.sebastian"Grzesik, Andrzej"https://zbmath.org/authors/?q=ai:grzesik.andrzejSummary: \textit{P. Erdős} and \textit{T. Gallai} [Acta Math. Acad. Sci. Hung. 10, 337--356 (1959; Zbl 0090.39401)] proved the asymptotically optimal bound for the maximum number of edges in graphs not containing a path of a fixed length. Here, we study a rainbow version of their theorem, in which one considers \(k\geq 1\) graphs on a common set of vertices not creating a path having edges from different graphs and asks for the maximum number of edges in each graph. We prove the asymptotically optimal bound in the case of a path on three edges and any \(k\geq 1\).On Rödl's theorem for cographshttps://zbmath.org/1532.050962024-05-13T19:39:47.825584Z"Gishboliner, Lior"https://zbmath.org/authors/?q=ai:gishboliner.lior"Shapira, Asaf"https://zbmath.org/authors/?q=ai:shapira.asafSummary: A theorem of Rödl states that for every fixed \(F\) and \(\varepsilon>0\) there is \(\delta=\delta_F(\varepsilon)\) so that every induced \(F\)-free graph contains a vertex set of size \(\delta n\) whose edge density is either at most \(\varepsilon\) or at least \(1-\varepsilon\). Rödl's proof relied on the regularity lemma, hence it supplied only a tower-type bound for \(\delta \). \textit{J. Fox} and \textit{B. Sudakov} [Adv. Math. 219, No. 6, 1771--1800 (2008; Zbl 1152.05054)] conjectured that \(\delta\) can be made polynomial in \(\varepsilon\), and a recent result of \textit{J. Fox} et al. [``Induced subgraph density. II. Sparse and dense sets in cographs'', Preprint, \url{arXiv:2307.00801}] shows that this conjecture holds when \(F=P_4\). In fact, they show that the same conclusion holds even if \(G\) contains few copies of \(P_4\). In this note we give a short proof of a more general statement.Disjoint cycles through prescribed vertices in multidimensional torihttps://zbmath.org/1532.050972024-05-13T19:39:47.825584Z"Shinde, Amruta"https://zbmath.org/authors/?q=ai:shinde.amruta-v"Borse, Y. M."https://zbmath.org/authors/?q=ai:borse.y-mSummary: For a positive integer \(r\), a graph \(G\) is spanning \(r\)-cyclable if for any given set \(F\) of \(r\) vertices, there exists \(r\) vertex-disjoint cycles that together span \(G\) and each cycle contains exactly one vertex from \(F\). It is known that the hypercube \(Q_{n}\) and its variation, the crossed cube, are spanning \(r\)-cyclable for \(1 \leq r \leq n-1\). We prove that every \(n\)-dimensional torus, different from \(C_{3} \square C_{3}\), is spanning \(r\)-cyclable for \(1 \leq r \leq 2n-1\).Corrigendum to: ``Curvature and entropy of a graph''https://zbmath.org/1532.050982024-05-13T19:39:47.825584Z"Paeng, Seong-Hun"https://zbmath.org/authors/?q=ai:paeng.seong-hunFrom the text: The author regrets that the curvature of a combinatorial graph defined in his paper [ibid. 603, Article ID 127783, 12 p. (2022; Zbl 1528.05038)] should be used for Theorem 2 instead of the curvature \(\kappa\).Parallel connectivity in edge-colored complete graphs: complexity resultshttps://zbmath.org/1532.050992024-05-13T19:39:47.825584Z"Saad, Rachid"https://zbmath.org/authors/?q=ai:saad.rachidSummary: Given an edge-colored graph \(G_c\), a set of \(p\) pairs of vertices \((a_i, b_i)\) together with \(p\) numbers \(k_1, k_2, \ldots, k_p\) associated with the pairs, can we find a set of alternating paths linking the pairs \((a_1, b_1), (a_2, b_2), \ldots\), in their respective numbers \(k_1, k_2, \ldots, k_p\)? Such is the question addressed in this paper. The problem being highly intractable, we consider a restricted version of it to edge-colored complete graphs. Even so restricted, the problem remains intractable if the paths/trails must be edge-disjoint, but it ceases to be so if the paths/trails are to be vertex-disjoint, as is proved in this paper. An approximation algorithm is presented in the end, with a performance ratio asymptotically close to 3/4 for a restricted version of the problem.Under which conditions is \(\lambda'' (G) = \kappa''(L(G))\)?https://zbmath.org/1532.051002024-05-13T19:39:47.825584Z"Soliemany, Farnaz"https://zbmath.org/authors/?q=ai:soliemany.farnaz"Ghasemi, Mohsen"https://zbmath.org/authors/?q=ai:ghasemi.mohsen"Varmazyar, Rezvan"https://zbmath.org/authors/?q=ai:varmazyar.rezvanSummary: In this paper we show that if \(G\) is a connected graph such that \(|G|\geq 2 (\delta (G) + 1)\), \(\delta (G) \geq 2\) and \(G \ncong G_{t, n}^{*}\) then \(\kappa'' (L(G))\) exists and \(\lambda'' (G)= \kappa'' (L(G))\) if and only if \(G\) is not super-\(\lambda''\). We also obtain some other results.Subquadratic-time algorithm for the diameter and all eccentricities on median graphshttps://zbmath.org/1532.051012024-05-13T19:39:47.825584Z"Bergé, Pierre"https://zbmath.org/authors/?q=ai:berge.pierre"Ducoffe, Guillaume"https://zbmath.org/authors/?q=ai:ducoffe.guillaume"Habib, Michel"https://zbmath.org/authors/?q=ai:habib.michelSummary: On sparse graphs, \textit{L. Roditty} and \textit{V. Vassilevska Williams} [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 515--524 (2013; Zbl 1293.05184)] proved that no \(O(n^{2-\varepsilon )} \)-time algorithm achieves an approximation factor smaller than \(\frac{3}{2}\) for the diameter problem unless SETH fails. In this article, we solve an open question formulated in the literature: can we use the structural properties of median graphs to break this global quadratic barrier? We propose the first combinatorial algorithm computing exactly all eccentricities of a median graph in truly subquadratic time. Median graphs constitute the family of graphs which is the most studied in metric graph theory because their structure represents many other discrete and geometric concepts, such as \(\mathrm{CAT(0)}\) cube complexes. Our result generalizes a recent one, stating that there is a linear-time algorithm for all eccentricities in median graphs with bounded dimension \(d \), i.e. the dimension of the largest induced hypercube. This prerequisite on \(d \) is not necessary anymore to determine all eccentricities in subquadratic time. The execution time of our algorithm is \(O(n^{1.6456}\log^{O(1)} n) \). We provide also some satellite outcomes related to this general result. In particular, restricted to simplex graphs, this algorithm enumerates all eccentricities with a quasilinear running time. Moreover, an algorithm is proposed to compute exactly all reach centralities in time \(O(2^{3d}n\log^{O(1)}n) \).The strong spectral property of graphs: graph operations and barbell partitionshttps://zbmath.org/1532.051022024-05-13T19:39:47.825584Z"Allred, Sarah"https://zbmath.org/authors/?q=ai:allred.sarah-r"Curl, Emelie"https://zbmath.org/authors/?q=ai:curl.emelie"Fallat, Shaun"https://zbmath.org/authors/?q=ai:fallat.shaun-m"Nasserasr, Shahla"https://zbmath.org/authors/?q=ai:nasserasr.shahla"Schuerger, Houston"https://zbmath.org/authors/?q=ai:schuerger.houston"Villagrán, Ralihe R."https://zbmath.org/authors/?q=ai:villagran.ralihe-r"Vishwakarma, Prateek K."https://zbmath.org/authors/?q=ai:vishwakarma.prateek-kumarSummary: The utility of a matrix satisfying the Strong Spectral Property has been well established particularly in connection with the inverse eigenvalue problem for graphs. More recently the class of graphs in which all associated symmetric matrices possess the Strong Spectral Property (denoted \(\mathcal{G}^{\mathrm{SSP}})\) were studied, and along these lines we aim to study properties of graphs that exhibit a so-called barbell partition. Such a partition is a known impediment to membership in the class \(\mathcal{G}^{\mathrm{SSP}}\). In particular we consider the existence of barbell partitions under various standard and useful graph operations. We do so by considering both the preservation of an already present barbell partition after performing said graph operations as well as barbell partitions which are introduced under certain graph operations. The specific graph operations we consider are the addition and removal of vertices and edges, the duplication of vertices, as well as the Cartesian products, tensor products, strong products, corona products, joins, and vertex sums of two graphs. We also identify a correspondence between barbell partitions and graph substructures called forts, using this correspondence to further connect the study of zero forcing and the Strong Spectral Property.On unimodular graphs with a unique perfect matchinghttps://zbmath.org/1532.051032024-05-13T19:39:47.825584Z"Basumatary, Parameswar"https://zbmath.org/authors/?q=ai:basumatary.parameswar"Sarma, Kuldeep"https://zbmath.org/authors/?q=ai:sarma.kuldeepSummary: A graph is called unimodular if its adjacency matrix has determinant \(\pm 1\). This article provides a necessary and sufficient condition for a simple connected graph with a unique perfect matching to be unimodular. In particular, we give a complete characterization of bicyclic unimodular graphs with a unique perfect matching. Moreover, the possible values of the determinant of the adjacency matrix of unicyclic, bicyclic, and tricyclic graphs with a unique perfect matching are also provided in this article. For non-bipartite unicyclic graphs with a unique perfect matching, we address the problem of when the inverse of the corresponding adjacency matrix is diagonally similar to a non-negative matrix. A pseudo-unimodular graph is a singular graph whose product of non-zero eigenvalues of the corresponding adjacency matrix is \(\pm 1\). We supply a necessary and sufficient condition for a singular graph to be pseudo-unimodular.Spectral sufficient conditions of the existence of the longest path in the graph and its traceabilityhttps://zbmath.org/1532.051042024-05-13T19:39:47.825584Z"Benediktovich, Vladimir Ivanovich"https://zbmath.org/authors/?q=ai:benediktovich.vladimir-ivanovichSummary: It is known that the existence of many classical combinatorial structures in a graph, such as perfect matchings, Hamiltonian cycles, effective dominating sets, etc., can be characterized using \(( \kappa,\tau )\)-regular sets, whose determination is equivalent to the determination of these classical combinatorial structures. On the other hand, the determination of \(( \kappa,\tau )\) regular sets is closely related to the properties of the main spectrum of a graph. We use the previously obtained generalized properties of \(( \kappa,\tau )\)-regular sets of graphs to develop a recognition algorithm of the traceability of a graph. We also obtained new sufficient conditions for the existence of a longest simple path in a graph in terms of the spectral radius of the adjacency matrix and the signless Laplacian of the graph.The skew spectral radius and skew Randić spectral radius of general random oriented graphshttps://zbmath.org/1532.051052024-05-13T19:39:47.825584Z"Hu, Dan"https://zbmath.org/authors/?q=ai:hu.dan"Broersma, Hajo"https://zbmath.org/authors/?q=ai:broersma.hajo-j"Hou, Jiangyou"https://zbmath.org/authors/?q=ai:hou.jiangyou"Zhang, Shenggui"https://zbmath.org/authors/?q=ai:zhang.shengguiSummary: Let \(G\) be a simple connected graph on \(n\) vertices, and let \(G^\sigma\) be an orientation of \(G\) with skew adjacency matrix \(S(G^\sigma)\). Let \(d_i\) be the degree of the vertex \(v_i\) in \(G\). The skew Randić matrix of \(G^\sigma\) is the \(n \times n\) real skew symmetric matrix \(\mathcal{R}_S (G^\sigma) = [(\mathcal{R}_S)_{ij}]\), where \((\mathcal{R}_S)_{ij} = -(\mathcal{R}_S)_{ji} = (d_i d_j)^{- \frac{1}{2}}\) if \((v_i, v_j)\) is an arc of \(G^\sigma\), and \((\mathcal{R}_S)_{ij} = (\mathcal{R}_S)_{ji} = 0\) otherwise. The skew spectral radius \(\rho_S (G^\sigma)\) and the skew Randić spectral radius \(\rho_{\mathcal{R}_S}(G^\sigma)\) of \(G^\sigma\) are defined as the spectral radius of \(S(G^\sigma)\) and \(\mathcal{R}_S (G^\sigma)\) respectively. In this paper, we give upper bounds for the skew spectral radius and skew Randić spectral radius of general random oriented graphs.The \(Q\)-minimizer graph with given independence numberhttps://zbmath.org/1532.051062024-05-13T19:39:47.825584Z"Hu, Yarong"https://zbmath.org/authors/?q=ai:hu.yarong"Lou, Zhenzhen"https://zbmath.org/authors/?q=ai:lou.zhenzhen"Ning, Wenjie"https://zbmath.org/authors/?q=ai:ning.wenjieSummary: Let \(\mathcal{G}_{n, \alpha}\) be the set of all connected graphs of order \(n\) with independence number \(\alpha\). A graph is called the \(Q\)-minimizer graph (\(A\)-minimizer graph) if it attains the minimum signless Laplacian spectral radius (adjacency spectral radius) over all graphs in \(\mathcal{G}_{n, \alpha}\). In this paper, we first show that the \(Q\)-minimizer graph must be a tree for \(\alpha \geq \lceil \frac{n}{2} \rceil\), and then we derive seven propositions about the \(Q\)-minimizer graph. Moreover, when \(n - \alpha\) is a constant, the structure of the \(Q\)-minimizer graph is characterized. The method of getting \(Q\)-minimizer graph in this paper is different from that of getting \(A\)-minimizer graph. As applications, we determine the \(Q\)-minimizer graphs for \(\alpha = n - 1\), \(n - 2\), \(n - 3\) and \(n - 4\), respectively. The results of \(\alpha = n - 1\), \(n - 2\), \(n - 3\) are consistent with that in [\textit{R. Li} and \textit{J. Shi}, ibid. 433, No. 8--10, 1614--1622 (2010; Zbl 1211.05075)] and the result of \(\alpha = n - 4\) is new. Interestingly, the \(Q\)-minimizer graph in \(\mathcal{G}_{n, n - 4}\) is unique, which is exactly one of the \(A\)-minimizer graphs in \(\mathcal{G}_{n, n - 4}\).Graph limits and spectral extremal problems for graphshttps://zbmath.org/1532.051072024-05-13T19:39:47.825584Z"Liu, Lele"https://zbmath.org/authors/?q=ai:liu.leleSummary: We prove two conjectures in spectral extremal graph theory involving the linear combinations of graph eigenvalues. Let \(\lambda_1(G)\) be the largest eigenvalue of the adjacency matrix of a graph \(G\) and \(\overline{G}\) be the complement of \(G\). A nice conjecture states that the graph on \(n\) vertices maximizing \(\lambda_1(G)+\lambda_1(\overline{G})\) is the join of a clique and an independent set with \(\lfloor n/3\rfloor\) and \(\lceil 2n/3\rceil\) (also \(\lceil n/3\rceil\) and \(\lfloor 2n/3\rfloor\) if \(n\equiv 2\pmod{3})\) vertices, respectively. We resolve this conjecture for sufficiently large \(n\) using analytic methods. Our second result concerns the \(Q\)-spread of a graph \(G\), which is defined as the difference between the largest eigenvalue and least eigenvalue of the signless Laplacian of \(G\). It was conjectured by \textit{D. Cvetković} et al. [Publ. Inst. Math., Nouv. Sér. 81(95), 11--27 (2007; Zbl 1164.05038)] that the unique \(n\)-vertex connected graph of maximum \(Q\)-spread is the graph formed by adding a pendant edge to \(K_{n-1}\). We confirm this conjecture for sufficiently large \(n\).Extremal problems for the eccentricity matrices of complements of treeshttps://zbmath.org/1532.051082024-05-13T19:39:47.825584Z"Mahato, Iswar"https://zbmath.org/authors/?q=ai:mahato.iswar"Kannan, M. Rajesh"https://zbmath.org/authors/?q=ai:rajesh-kannan.mSummary: The eccentricity matrix of a connected graph \(G\), denoted by \(\mathcal{E}(G)\), is obtained from the distance matrix of \(G\) by keeping the largest nonzero entries in each row and each column and leaving zeros in the remaining ones. The \(\mathcal{E}\)-eigenvalues of \(G\) are the eigenvalues of \(\mathcal{E}(G)\). The largest modulus of an eigenvalue is the \(\mathcal{E}\)-spectral radius of \(G\). The \(\mathcal{E}\)-energy of \(G\) is the sum of the absolute values of all \(\mathcal{E}\)-eigenvalues of \(G\). In this article, we study some of the extremal problems for eccentricity matrices of complements of trees and characterize the extremal graphs. First, we determine the unique tree whose complement has minimum (respectively, maximum) \(\mathcal{E}\)-spectral radius among the complements of trees. Then, we prove that the \(\mathcal{E}\)-eigenvalues of the complement of a tree are symmetric about the origin. As a consequence of these results, we characterize the trees whose complement has minimum (respectively, maximum) least \(\mathcal{E}\)-eigenvalues among the complements of trees. Finally, we discuss the extremal problems for the second largest \(\mathcal{E}\)-eigenvalue and the \(\mathcal{E}\)-energy of complements of trees and characterize the extremal graphs. As an application, we obtain a Nordhaus-Gaddum-type lower bounds for the second largest \(\mathcal{E}\)-eigenvalue and \(\mathcal{E}\)-energy of a tree and its complement.On the spectra and spectral radii of token graphshttps://zbmath.org/1532.051092024-05-13T19:39:47.825584Z"Reyes, M. A."https://zbmath.org/authors/?q=ai:reyes.marco-a-h"Dalfó, C."https://zbmath.org/authors/?q=ai:dalfo.cristina"Fiol, M. A."https://zbmath.org/authors/?q=ai:fiol.miquel-angelSummary: Let \(G\) be a graph on \(n\) vertices. The \(k\)-token graph (or symmetric \(k\)-th power) of \(G\), denoted by \(F_k (G)\), has as vertices the \(\left(\begin{smallmatrix} n\\ k\end{smallmatrix}\right) k\)-subsets of vertices from \(G\), and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in \(G\). In particular, \(F_k (K_n)\) is the Johnson graph \(J(n, k)\), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of \(F_k (G)\) in terms of the spectrum of \(G\). For instance, when \(G\) is walk-regular, an exact value for the spectral radius \(\rho\) (or maximum eigenvalue) of \(F_k (G)\) is obtained. When \(G\) is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous' spectral gap conjecture (which is now a theorem) is proposed.Maximum degree and spectral radius of graphs in terms of sizehttps://zbmath.org/1532.051102024-05-13T19:39:47.825584Z"Wang, Zhiwen"https://zbmath.org/authors/?q=ai:wang.zhiwen"Guo, Ji-Ming"https://zbmath.org/authors/?q=ai:guo.jimingSummary: Denote by \(\rho (G)\) and \(\kappa (G)\) the spectral radius and the signless Laplacian spectral radius of a graph \(G\), respectively. Let \(k\geq 0\) be a fixed integer and \(G\) be a graph of size \(m\) which is large enough. We show that if \(\rho (G)\geq \sqrt{m-k}\), then \(C_4 \subseteq G\) or \(K_{1,m-k}\subseteq G\). Moreover, we prove that if \(\kappa (G)\geq m-k+1\), then \(K_{1,m-k}\subseteq G\). Both these results extend some known results.On the first two eigenvalues of regular graphshttps://zbmath.org/1532.051112024-05-13T19:39:47.825584Z"Zhang, Shengtong"https://zbmath.org/authors/?q=ai:zhang.shengtongSummary: Let \(G\) be a regular graph with \(m\) edges, and let \(\mu_1, \mu_2\) denote the two largest eigenvalues of \(A_G\), the adjacency matrix of \(G\). We show that, if \(G\) is not complete, then
\[
\mu_1^2 +\mu_2^2 \leq \frac{2(\omega -1)}{\omega} m
\]
where \(\omega\) is the clique number of \(G\). This confirms a conjecture of \textit{B. Bollobás} and \textit{V. Nikiforov} [J. Comb. Theory, Ser. B 97, No. 5, 859--865 (2007; Zbl 1124.05058)] for regular graphs. We also show that equality holds if and only if \(G\) is either a balanced Turán graph or the disjoint union of two balanced Turán graphs of the same size.Some bounds for the incidence \(Q\)-spectral radius of uniform hypergraphshttps://zbmath.org/1532.051122024-05-13T19:39:47.825584Z"Zhou, Junpeng"https://zbmath.org/authors/?q=ai:zhou.junpeng"Zhu, Zhongxun"https://zbmath.org/authors/?q=ai:zhu.zhongxun"Yang, Yu"https://zbmath.org/authors/?q=ai:yang.yu.3Summary: For a hypergraph \(H\), let \(B(H)\) be its incidence matrix. The signless Laplacian matrix \(Q(H)=B(H)B(H)^T\), whose \((i, j)\)-element is exactly the number of edges containing vertices \(v_i\) and \(v_j\) for \(i\ne j\) and \((i, i)\)-element is exactly the degree of vertex \(v_i\). The incidence \(Q\)-tensor \({\mathcal{Q}}^\ast=B(H){\mathcal{I}}B(H)^T\), whose \((i_1,i_2,\ldots ,i_k)\)-entry of \({\mathcal{Q}}^\ast\) is exactly equal to the number of edges \(e\) of \(H\) satisfying \(i_t\in e\) for all \(t\in [k]\). Obviously, we can see more complete structural properties of \(H\) from \({\mathcal{Q}}^\ast\) than \(Q(H)\). Up to now, few tensors whose entries are directly related to structural properties of the corresponding hypergraphs. In this regard, we believe that it deserve to study the structural properties of hypergraphs though this tensor. In this paper, we will study some upper bounds on the spectral radius of \({\mathcal{Q}}^\ast\) by some parameters on hypergraphs.Infinite Ramsey-minimal graphs for star forestshttps://zbmath.org/1532.051132024-05-13T19:39:47.825584Z"Hadiputra, Fawwaz Fakhrurrozi"https://zbmath.org/authors/?q=ai:hadiputra.fawwaz-fakhrurrozi"Vito, Valentino"https://zbmath.org/authors/?q=ai:vito.valentinoSummary: For graphs \(F\), \(G\), and \(H\), we write \(F \rightarrow (G,H)\) if every red-blue coloring of the edges of \(F\) produces a red copy of \(G\) or a blue copy of \(H\). The graph \(F\) is said to be \((G, H)\)-minimal if it is subgraph-minimal with respect to this property. The characterization problem for Ramsey-minimal graphs is classically done for finite graphs. \textit{J. M. Barrett} and \textit{V. Vito} [Electron. J. Comb. 28, No. 1, Research Paper P1.46, 14 p. (2021; Zbl 1464.05261)] generalized this problem to infinite graphs. They asked which pairs \((G, H)\) admit a Ramsey-minimal graph and which ones do not. We show that any pair of star forests such that at least one of them involves an infinite-star component admits no Ramsey-minimal graph. Also, we construct a Ramsey-minimal graph for a finite star forest versus a subdivision graph. This paper builds upon the results of \textit{S. A. Burr} et al. [Discrete Math. 33, 227--237 (1981; Zbl 0456.05046)] on Ramsey-minimal graphs for finite star forests.Complete bipartite graphs without small rainbow subgraphshttps://zbmath.org/1532.051142024-05-13T19:39:47.825584Z"Ma, Zhiqiang"https://zbmath.org/authors/?q=ai:ma.zhiqiang"Mao, Yaping"https://zbmath.org/authors/?q=ai:mao.yaping"Schiermeyer, Ingo"https://zbmath.org/authors/?q=ai:schiermeyer.ingo"Wei, Meiqin"https://zbmath.org/authors/?q=ai:wei.meiqinSummary: Motivated by bipartite Gallai-Ramsey type problems, we consider edge-colorings of complete bipartite graphs without rainbow tree and matching. Given two graphs \(G\) and \(H\), and a positive integer \(k\), define the bipartite Gallai-Ramsey number \(\operatorname{bgr}_k (G : H)\) as the minimum number of vertices \(n\) such that \(n^2 \geq k\) and for every \(N \geq n\), any coloring (using all \(k\) colors) of the complete bipartite graph \(K_{N, N}\) contains a rainbow copy of \(G\) or a monochromatic copy of \(H\). In this paper, we first describe the structures of a complete bipartite graph \(K_{n, n}\) without rainbow \(P_4^+\) and \(3 K_2\), respectively, where \(P_4^+\) is the graph consisting of a \(P_4\) with one extra edge incident with an interior vertex. Furthermore, we determine the exact values or upper and lower bounds on \(\operatorname{bgr}_k (G : H)\) when \(G\) is a 3-matching or a 4-path or \(P_4^+\), and \(H\) is a bipartite graph.Paired-domination game played on cycleshttps://zbmath.org/1532.051152024-05-13T19:39:47.825584Z"Gray, Aaron D."https://zbmath.org/authors/?q=ai:gray.aaron-d"Henning, Michael A."https://zbmath.org/authors/?q=ai:henning.michael-anthonyThis text further develops the graph domination game introduced in [\textit{B. Brešar} et al. SIAM J. Discrete Math. 24, No. 3, 979--991 (2010; Zbl 1223.05189)]. The version of the game studied involves two players, the Dominator and the Staller, who take turns choosing pairs of adjacent, unchosen vertices that dominate at least one vertex not dominated by a previously chosen pair of vertices. The game ends when there are no moves left, and the resulting set of vertices becomes a paired-dominating set -- a dominating set such that the subgraph induced by it contains a perfect matching. The Staller aims to maximize the cardinality of this set while the Dominator wishes to minimize it. The paper begins with both previous and new bounds for the game paired-domination number, then introduces the Paired-Domination Continuation principle and uses it to prove that for every graph \(G\), \(|\gamma_{gpr}(G)-\gamma_{gpr}^\prime (G)|\in\{0, 2\}\) where \(\gamma_{gpr}(G)\) is the cardinality of the dominating set when the Dominator moves first and \(\gamma_{gpr}^\prime (G)\) is the same quantity when the Staller moves first. The paper then introduces exact values for \(\gamma_{gpr}(G)\) and \(\gamma_{gpr}^\prime (G)\) where \(G\) is a cycle \(C_n\) on \(n\) vertices.
Reviewer: Solden Stoll (Seattle)Formulations for the maximum common edge subgraph problemhttps://zbmath.org/1532.051162024-05-13T19:39:47.825584Z"de Gastines, Etienne"https://zbmath.org/authors/?q=ai:de-gastines.etienne"Knippel, Arnaud"https://zbmath.org/authors/?q=ai:knippel.arnaudSummary: The Maximum Common Edge Subgraph Problem (MCES), given two graphs \(G\) and \(H\), asks about finding a maximum common subgraph between those two graphs with a maximal number of edges. We present new integer programming formulations for MCES and compare the performances of those formulations with earlier formulations from the literature.Graph sequences sampled from Robinson graphonshttps://zbmath.org/1532.051172024-05-13T19:39:47.825584Z"Ghandehari, Mahya"https://zbmath.org/authors/?q=ai:ghandehari.mahya"Janssen, Jeannette"https://zbmath.org/authors/?q=ai:janssen.jeannette-c-mSummary: The function \(\Gamma\) on the space of graphons, introduced in \textit{H. Chuangpishit} et al. [J. Comb. Theory, Ser. B 113, 162--184 (2015; Zbl 1315.05091)], aims to measure the extent to which a graphon \(w\) exhibits the Robinson property: for all \(x < y < z\), \(w ( x , z ) \leq \min \{ w ( x , y ) , w ( y , z ) \} \). Robinson graphons form a model for graphs with a natural line embedding so that most edges are local. The function \(\Gamma\) is compatible with the cut-norm \(\| \cdot \|_\square \), in the sense that graphons close in cut-norm have similar \(\Gamma \)-values. In particular, any graphon close in cut-norm to the set of all Robinson graphons has small \(\Gamma \)-values. Here we show the converse, by proving that every graphon \(w\) can be approximated by a Robinson graphon \(R_w\) so that \(\| w - R_w \|_\square\) is bounded in terms of \(\Gamma ( w )\). We then use classical techniques from functional analysis to show that a converging graph sequence \(\{ G_n \}\) converges to a Robinson graphon if and only if \(\Gamma ( G_n ) \to 0\). Finally, using probabilistic techniques we show that the rate of convergence of \(\Gamma\) for graph sequences sampled from a Robinson graphon can differ substantially depending on how strongly \(w\) exhibits the Robinson property.Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphshttps://zbmath.org/1532.051182024-05-13T19:39:47.825584Z"John O'Shea, Robert"https://zbmath.org/authors/?q=ai:john-oshea.robert"Wilkins, Louis"https://zbmath.org/authors/?q=ai:wilkins.louisSummary: Background: The Kelly-Ulam reconstruction conjecture proposes that a graph's isomorphism class is determined by the classes of its multiset of vertex-deleted subgraphs. Although the conjecture has been verified for many families of undirected graphs, several cases remain unresolved. This analysis proposes a unified proof of the reconstruction conjecture for all finite undirected graphs.
Methodology: A vertex-substitution framework is introduced, in which vertex-deleted subgraphs are augmented by a substitute vertex connected universally with characteristic edge weight (an arbitrary constant outside the deck alphabet). Vertex-substituted subgraphs have as many vertices as the parent graph, permitting tensor representation of the deck reconstruction.
Results: Hypomorphism under vertex-deletion is shown to imply hypomorphism under vertex-substitution and vice-versa. In the vertex-substitution framework, bijections mapping cards between hypomorphic decks are shown to map vertices between the parent graphs, demonstrating that an isomorphic mapping always exists.
Conclusions: The Kelly-Ulam reconstruction conjecture is verified for finite, undirected graphs on at least three vertices. The vertex-substitution framework provides a unified analytical approach to the reconstruction conjecture for all undirected graphs.On the hardness of the balanced connected subgraph problem for families of regular graphshttps://zbmath.org/1532.051192024-05-13T19:39:47.825584Z"Pathak, Harsharaj"https://zbmath.org/authors/?q=ai:pathak.harsharajSummary: The Balanced Connected Subgraph problem (BCS) was introduced by \textit{S. Bhore} et al. [Theor. Comput. Sci. 929, 69--80 (2022; Zbl 07575080)]. In the BCS problem, we are given a vertex-colored graph \(G=(V,E)\) where each vertex is colored ``red'' or ``blue''. The goal is to find a maximum cardinality induced connected subgraph \(H\) of \(G\) such that \(H\) contains an equal number of red and blue vertices. This problem is known to be NP-hard for general graphs as well as for many special classes of graphs. In this work, we explore the time complexity of the BCS problem in the case of regular graphs. We prove that the BCS problem is NP-hard for \(d\)-regular graphs \(\forall d\in\mathbb{N}\), \(d>3\). We further propose a parameterized variant of the BCS problem and explore its time complexity.An embedding technique in the study of word-representability of graphshttps://zbmath.org/1532.051202024-05-13T19:39:47.825584Z"Huang, Sumin"https://zbmath.org/authors/?q=ai:huang.sumin"Kitaev, Sergey"https://zbmath.org/authors/?q=ai:kitaev.sergey"Pyatkin, Artem"https://zbmath.org/authors/?q=ai:pyatkin.artem-valerevichSummary: Word-representable graphs, which are the same as semi-transitively orientable graphs, generalize several fundamental classes of graphs. In this paper we propose a novel approach to study word-representability of graphs using a technique of homomorphisms. As a proof of concept, we apply our method to show word-representability of the simplified graph of overlapping permutations that we introduce in this paper. For another application, we obtain results on word-representability of certain subgraphs of simplified de Bruijn graphs that were introduced recently by \textit{A. V. Petyuk} [``On word-representability of simplified de Bruijn graphs'', Preprint, \url{arXiv:2210.14762}] and studied in the context of word-representability.On the maximum \(F_5\)-free subhypergraphs of a random hypergraphhttps://zbmath.org/1532.051212024-05-13T19:39:47.825584Z"Araujo, Igor"https://zbmath.org/authors/?q=ai:araujo.igor"Balogh, József"https://zbmath.org/authors/?q=ai:balogh.jozsef"Luo, Haoran"https://zbmath.org/authors/?q=ai:luo.haoranSummary: Denote by \(F_5\) the \(3\)-uniform hypergraph on vertex set \(\{1, 2, 3, 4, 5\}\) with hyperedges \(\{123,124, 345\}\). \textit{J. Balogh} et al. [Random Struct. Algorithms 48, No. 4, 641--654 (2016; Zbl 1341.05176)] proved that if \(p > K \log n /n\) for some large constant \(K\), then every maximum \(F_5\)-free subhypergraph of \(G^3(n,p)\) is tripartite with high probability, and showed that if \(p_0 = 0.1\sqrt{\log n} /n\), then with high probability there exists a maximum \(F_5\)-free subhypergraph of \(G^3(n, p_0)\) that is not tripartite. In this paper, we sharpen the upper bound to be best possible up to a constant factor. We prove that if \(p > C \sqrt{\log n} /n\) for some large constant \(C\), then every maximum \(F_5\)-free subhypergraph of \(G^3(n, p)\) is tripartite with high probability.Edge balanced star-hypergraph designs and vertex colorings of path designshttps://zbmath.org/1532.051222024-05-13T19:39:47.825584Z"Bonacini, Paola"https://zbmath.org/authors/?q=ai:bonacini.paola"Marino, Lucia"https://zbmath.org/authors/?q=ai:marino.luciaSummary: Let \({K}_\nu^{(3)}=(X,\mathcal{E})\) be the complete hypergraph, uniform of rank 3, defined on a vertex set \(X=\{x_1,\ldots,x_\nu\}\), so that \(\mathcal{E}\) is the set of all triples of \(X\). Let \(H^{(3)}=(V,\mathcal{D})\) be a subhypergraph of \(K_\nu^{(3)}\), which means that \(V\subseteq X\) and \(\mathcal{D}\subseteq\mathcal{E}\). We call 3-edges the triples of \(V\) contained in the family \(\mathcal{D}\) and edges the pairs of \(V\) contained in the 3-edges of \(\mathcal{D}\), that we denote by \([x,y]\). A \(H^{(3)}\)-design \(\Sigma\) is called edge balanced if for any \(x,y\in X\), \(x\ne y\), the number of blocks of \(\Sigma\) containing the edge \([x,y]\) is constant. In this paper, we consider the star hypergraph \(S^{(3)}(2,m+2)\), which is a hypergraph with \(m\) 3-edges such that all of them have an edge in common. We completely determine the spectrum of edge balanced \(S^{(3)}(2,m+2)\)-designs for any \(m\ge 2\), that is, the set of the orders \(\nu\) for which such a design exists. Then we consider the case \(m=2\) and we denote the hypergraph \(S^{(3)}(2,4)\) by \(P^{(3)}(2,4)\). Starting from any edge-balanced \(S^{(3)}\left(2,\frac{\nu+4}{3}\right)\), with \(\nu\equiv 2\mod 3\) sufficiently big, for any \(p\in{\mathbb{N}}\), \(\lceil\frac{\nu}{2}\rceil\le p\le \nu\), we construct a \(P^{(3)}(2,4)\)-design of order \(2\nu\) with feasible set \(\{2,3\}\cup [p,\nu]\), in the context of proper vertex colorings such that no block is either monochromatic or polychromatic.On \(3\)-uniform hypergraphs avoiding a cycle of length fourhttps://zbmath.org/1532.051232024-05-13T19:39:47.825584Z"Ergemlidze, Beka"https://zbmath.org/authors/?q=ai:ergemlidze.beka"Győri, Ervin"https://zbmath.org/authors/?q=ai:gyori.ervin"Methuku, Abhishek"https://zbmath.org/authors/?q=ai:methuku.abhishek"Salia, Nika"https://zbmath.org/authors/?q=ai:salia.nika"Tompkins, Casey"https://zbmath.org/authors/?q=ai:tompkins.caseySummary: We show that the maximum number of edges in a \(3\)-uniform hypergraph without a Berge cycle of length four is at most \((1+o(1))\frac{n^{3/2}}{\sqrt{10}}\). This improves earlier estimates by \textit{E. Győri} and \textit{N. Lemons} [Comb. Probab. Comput. 21, No. 1--2, 193--201 (2012; Zbl 1241.05101)] and by \textit{Z. Füredi} and \textit{L. Özkahya} [Discrete Appl. Math. 216, Part 3, 582--588 (2017; Zbl 1358.05203)].Corrigendum to: ``Online purchasing under uncertainty''https://zbmath.org/1532.051242024-05-13T19:39:47.825584Z"Frieze, Alan"https://zbmath.org/authors/?q=ai:frieze.alan-m"Pegden, Wesley"https://zbmath.org/authors/?q=ai:pegden.wesleyCorrigendum to the authors' paper [ibid. 53, No. 2, 327--351 (2018; Zbl 1401.05204)].
%{{\copyright} 2021 Wiley Periodicals LLC.}Rigidity properties of the hypercube via Bakry-Émery curvaturehttps://zbmath.org/1532.051252024-05-13T19:39:47.825584Z"Liu, Shiping"https://zbmath.org/authors/?q=ai:liu.shiping"Münch, Florentin"https://zbmath.org/authors/?q=ai:munch.florentin"Peyerimhoff, Norbert"https://zbmath.org/authors/?q=ai:peyerimhoff.norbertSummary: We give rigidity results for the discrete Bonnet-Myers diameter bound and the Lichnerowicz eigenvalue estimate. Both inequalities are sharp if and only if the underlying graph is a hypercube. The proofs use well-known semigroup methods as well as new direct methods which translate curvature to combinatorial properties. Our results can be seen as first known discrete analogues of \textit{S.-Y. Cheng}'s [Math. Z. 143, 289--297 (1975; Zbl 0329.53035)] and \textit{M. Obata}'s [ J. Math. Soc. Japan 14, 333--340 (1962; Zbl 0115.39302)] rigidity theorems.An improved upper bound on the domination number of a treehttps://zbmath.org/1532.051262024-05-13T19:39:47.825584Z"Cabrera-Martínez, Abel"https://zbmath.org/authors/?q=ai:cabrera-martinez.abelA dominating set in a graph is a subset of vertices such that every vertex in the graph is either in the dominating set or adjacent to a vertex in the dominating set. The domination number of a graph is the minimum cardinality among all dominating sets of the graph. The author improves the previously known upper bound on the domination number of trees by giving the tight bound in terms of the order of a graph, its number of support vertices, strong support vertices, support link vertices, and strong leaves.
Reviewer: Aleksandra Tepeh (Duplek)Perfect double Italian domination of a graphhttps://zbmath.org/1532.051272024-05-13T19:39:47.825584Z"Hao, Guoliang"https://zbmath.org/authors/?q=ai:hao.guoliang"Jalilolghadr, Parvin"https://zbmath.org/authors/?q=ai:jalilolghadr.parvin"Mojdeh, Doost Ali"https://zbmath.org/authors/?q=ai:mojdeh.doost-aliSummary: For a graph \(G = (V, E)\) with \(V = V(G)\) and \(E = E(G)\), a perfect double Italian dominating function is a function \(f : V \to \{0, 1, 2, 3\}\) having the property that \(3 \leq \sum_{u \in N_{G} [v]} f(u) \leq 4\), for every vertex \(v \in G\) with \(f(v) \in \{0, 1\}\). The weight of a perfect double Italian dominating function \(f\) is the sum \(f(V) = \sum_{v \in V (G)} f(v)\) and the minimum weight of a perfect double Italian dominating function on \(G\) is the perfect double Italian domination number \(\gamma_{dl}^{p} (G)\) of \(G\). We initiate the study of perfect double Italian dominating functions. We check the \(\gamma_{dI}^{p}\) of some standard graphs and evaluate with \(\gamma_{dI}\) of such graphs. The perfect double Italian dominating functions versus perfect double Roman dominating functions are perused. The NP-completeness of this parameter is verified even when it is restricted to bipartite graphs. Finally, we characterize the graphs \(G\) of order \(n\) with \(\gamma_{dI}^{p} (G) \in \{3, 4, 5, n, 2n - 3, 2n - 4, 2n - 5, 2n - 6\}\).Counterexamples to the characterisation of graphs with equal independence and annihilation numberhttps://zbmath.org/1532.051282024-05-13T19:39:47.825584Z"Hiller, Michaela"https://zbmath.org/authors/?q=ai:hiller.michaelaSummary: In this paper, we disprove the claimed characterisation of graphs with equal independence and annihilation number as proposed by \textit{C. E. Larson} and \textit{R. Pepper} [ibid. 18, No. 1, Research Paper P180, 9 p. (2011; Zbl 1238.05198)]. The annihilation number of a graph is defined as the largest integer \(p\) such that the sum of its smallest \(p\) degrees is greater than or equal to its size, i.e., its number of edges. Larson and Pepper [loc. cit.] claimed that for a given graph \(G=(V, E)\), its independence number \(\alpha(G)\) equals its annihilation number \(a(G)\) if and only if
\begin{align*}
a (G) &\geqslant \frac {n}{2}: \quad && \alpha^\prime (G)=a(G) \tag{1} \\
a (G) &= \frac{n-1}{2}: \quad && \alpha'(G-v)=a(G) \,\, \text{for some} \,\, v \in V. \tag{2}
\end{align*}
This paper provides series of counterexamples with an arbitrarily large number of vertices, an arbitrarily large number of components, an arbitrarily large independence number, and an arbitrarily large difference between the critical and the regular independence number. Furthermore, we identify the error in the proof of Larson and Pepper's [loc. cit.] theorem. Yet, we show that the theorem still holds for bipartite graphs and connected claw-free graphs.On \([k]\)-Roman domination in graphshttps://zbmath.org/1532.051292024-05-13T19:39:47.825584Z"Khalili, N."https://zbmath.org/authors/?q=ai:khalili.nasser"Amjadi, J."https://zbmath.org/authors/?q=ai:amjadi.jafar"Chellali, M."https://zbmath.org/authors/?q=ai:chellali.mustapha.1"Sheikholeslami, S. M."https://zbmath.org/authors/?q=ai:sheikholeslami.seyed-mahmoudSummary: For an integer \(k \geq 1\), let \(f\) be a function that assigns labels from the set \(\{0, 1, \dots, k + 1\}\) to the vertices of a simple graph \(G = (V, E)\). The active neighborhood \(AN (v)\) of a vertex \(v \in V(G)\) with respect to \(f\) is the set of all neighbors of \(v\) that are assigned non-zero values under \(f\). A [\(k\)]-Roman dominating function (\([k]\)-RDF) is a function \(f : V(G) \to \{0, 1, 2, \dots, k +1 \}\) such that for every vertex \(v \in V(G)\) with \(f(v) < k\), we have \(\sum_{u \in N [v]} f(u) \geq |AN(v)| + k\). The weight of a [\(k\)]-RDF is the sum of its function values over the whole set of vertices, and the [\(k\)]-Roman domination number \(\gamma_{[kR]} (G)\) is the minimum weight of a [\(k\)]-RDF on \(G\). In this paper we determine various bounds on the [\(k\)]-Roman domination number. In particular, we show that for any integer \(k \geq 2\) every connected graph \(G\) of order \(n \geq 3\), satisfies \(\gamma_{[kR]} (G) \leq \frac{ (2k + 1)}{4} n\), and we characterize the graphs \(G\) attaining this bound. Moreover, we show that if \(T\) is a nontrivial tree, then \(\gamma_{[kR]} (T) \geq k \gamma (T) + 1\) for every integer \(k \geq 2\) and we characterize the trees attaining the lower bound. Finally, we prove the NP-completeness of the [\(k\)]-Roman domination problem in bipartite and chordal graphs.Towards the conjecture on domination versus edge domination in graphshttps://zbmath.org/1532.051302024-05-13T19:39:47.825584Z"Maniya, Paras"https://zbmath.org/authors/?q=ai:maniya.paras"Pradhan, Dinabandhu"https://zbmath.org/authors/?q=ai:pradhan.dinabandhuThe graphs considered are finite, simple, and undirected graphs. Let the vertex set and edge set of the graph be denoted by \(V(G)\) and \(E(G)\) respectively.
A dominating set of \(G\) is a subset \(D \subseteq V\) such that every vertex of \(V(G)\setminus D\) is adjacent to at least one vertex of \(D\). The minimum cardinality of a dominating set of a graph \(G\) is called the domination number of graph \(G\) and is denoted by \(\gamma(G)\). An edge dominating set of \(G\) is a subset \(F \subseteq E\) such that every edge in \(E(G)\setminus F\) is adjacent to at least one edge of \(F\). The minimum cardinality of an edge dominating set of a graph \(G\) is called the edge domination number of \(G\) and is denoted by \(\gamma_e(G)\).
\textit{J. Baste} et al. [Discrete Appl. Math. 285, 343--349 (2020; Zbl 1466.05155)] conjectured that if \(G\) is a \(\Delta\)-regular graph with \(\Delta \geq 1\), then \(\gamma(G) \leq \gamma_e(G)\). \textit{Y. Civan} et al. [ibid. 337, 171--172 (2023; Zbl 1520.05072)] proved the result to be true for a claw-free graph with minimum degree of at least two.
A fork is a graph that is obtained by attaching a pendant vertex to one of the vertex of a path \(P_4\) having degree two. A graph is fork-free if the graph does not contain any induced subgraph that is isomorphic to fork.
In the paper under review, the authors prove the conjecture to be true for fork-free graphs with minimum degree of at least two. Moreover, they also prove the conjecture to be valid for \(P_4\)-free graph with minimum degree at least one.
Reviewer: Venkatakrishnan Yanamandram (Tiruchirappalli)2-power domination number for Knödel graphs and its application in communication networkshttps://zbmath.org/1532.051312024-05-13T19:39:47.825584Z"Rajan, R. Sundara"https://zbmath.org/authors/?q=ai:rajan.r-sundara"Arulanand, S."https://zbmath.org/authors/?q=ai:arulanand.s"Prabhu, S."https://zbmath.org/authors/?q=ai:prabhu.swathy|prabhu.sumanth|prabhu.sharad-s|prabhu.s-v|prabhu.s-s|prabhu.s-r-boselin|prabhu.shanker-g-r|prabhu.sahana-m|prabhu.sachin|prabhu.siddharth-g|prabhu.sowbhagya-s|prabhu.savari"Rajasingh, Indra"https://zbmath.org/authors/?q=ai:rajasingh.indra\(2\)-power domination number \(\gamma_{p,2}\) of Knödel graphs \(W_{\Delta,n}\) is investigated. It is proved that if \(n\ge 18\), then \(\gamma_{p,2}(W_{4,n}) = 2\) and that if \(n\ge 46\), then \(\gamma_{p,2}(W_{5,n}) \ge 3\). Applications of the \(2\)-power domination number are also discussed.
Reviewer: Sandi Klavžar (Ljubljana)Envy-free matchings in bipartite graphs and their applications to fair divisionhttps://zbmath.org/1532.051322024-05-13T19:39:47.825584Z"Aigner-Horev, Elad"https://zbmath.org/authors/?q=ai:aigner-horev.elad"Segal-Halevi, Erel"https://zbmath.org/authors/?q=ai:segal-halevi.erelSummary: A matching in a bipartite graph with parts \(X\) and \(Y\) is called envy-free, if no unmatched vertex in \(X\) is a adjacent to a matched vertex in \(Y\). Every perfect matching is envy-free, but envy-free matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources (``cakes'') or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1-out-of-\((2n - 2)\) maximin-share allocation of discrete goods, and an algorithm for 1-out-of-\(\lfloor 2n/3 \rfloor\) maximin-share allocation of discrete bads among \(n\) agents.FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphshttps://zbmath.org/1532.051332024-05-13T19:39:47.825584Z"Bessy, Stéphane"https://zbmath.org/authors/?q=ai:bessy.stephane"Hörsch, Florian"https://zbmath.org/authors/?q=ai:horsch.florian"Maia, Ana Karolinna"https://zbmath.org/authors/?q=ai:maia.ana-karolinna"Rautenbach, Dieter"https://zbmath.org/authors/?q=ai:rautenbach.dieter"Sau, Ignasi"https://zbmath.org/authors/?q=ai:sau.ignasiSummary: We study three problems introduced by \textit{J. Bang-Jensen} and \textit{A. Yeo} [Theor. Comput. Sci. 595, 107--119 (2015; Zbl 1328.68082)] and by \textit{J. Bang-Jensen} et al. [Discrete Appl. Math. 209, 16--26 (2016; Zbl 1339.05371)] about finding disjoint ``balanced'' spanning rooted substructures in graphs and digraphs, which generalize classic packing problems such as detecting the existence of multiple arc-disjoint spanning arborescences. Namely, given a positive integer \(k\), a digraph \(D = (V, A)\), and a root \(r \in V\), we first consider the problem of finding two arc-disjoint \(k\)-safe spanning \(r\)-arborescences, meaning arborescences rooted at a vertex \(r\) such that deleting any arc \(rv\) and every vertex in the sub-arborescence rooted at \(v\) leaves at least \(k\) vertices. Then, we consider the problem of finding two arc-disjoint \((r, k)\)-flow branchings meaning arc sets admitting a flow that distributes one unit from \(r\) to every other vertex while respecting a capacity limit of \(n - k\) on every arc. We show that both these problems are \textsf{FPT} with parameter \(k\), improving on existing \textsf{XP} algorithms. The latter of these results answers a question of Bang-Jensen et al. [loc. cit.]. Further, given a positive integer \(k\), a graph \(G = (V, E)\), and \(r \in V\), we consider the problem of finding two edge-disjoint \((r, k)\)-safe spanning trees meaning spanning trees such that the component containing \(r\) has size at least \(k\) when deleting any vertex different from \(r\). We show that this problem is also \textsf{FPT} with parameter \(k\), again improving on a previous \textsf{XP} algorithm. Our main technical contribution is to prove that the existence of such spanning substructures is equivalent to the existence of substructures with size and maximum (out-)degree both bounded by a (linear or quadratic) function of \(k\), which may be of independent interest.Decomposing a triangle-free planar graph into a forest and a subcubic foresthttps://zbmath.org/1532.051342024-05-13T19:39:47.825584Z"Feghali, Carl"https://zbmath.org/authors/?q=ai:feghali.carl"Šámal, Robert"https://zbmath.org/authors/?q=ai:samal.robertSummary: We strengthen a result of \textit{F. Dross} et al. [ibid. 66, 81--94 (2017; Zbl 1369.05169)] that the vertex set of every triangle-free planar graph can be decomposed into a set that induces a forest and a set that induces a forest with maximum degree at most 5, showing that 5 can be replaced by 3.\((\alpha,\beta)\)-modules in graphshttps://zbmath.org/1532.051352024-05-13T19:39:47.825584Z"Habib, Michel"https://zbmath.org/authors/?q=ai:habib.michel"Mouatadid, Lalla"https://zbmath.org/authors/?q=ai:mouatadid.lalla"Sopena, Éric"https://zbmath.org/authors/?q=ai:sopena.eric"Zou, Mengchuan"https://zbmath.org/authors/?q=ai:zou.mengchuanSummary: Modular decomposition focuses on repeatedly identifying a module \(M\) (a collection of vertices that shares exactly the same neighborhood outside of \(M)\) and collapsing it into a single vertex. This notion of exactitude of neighborhood is very strict, especially when dealing with real-world graphs. We study new ways to relax this exactitude condition. However, generalizing modular decomposition is far from obvious. Most of the previous proposals lose algebraic properties of modules and thus most of the nice algorithmic consequences. We introduce the notion of an \((\alpha,\beta)\)-module, a relaxation that maintains some of the algebraic structure. It leads to a new combinatorial decomposition with interesting properties. Among the main results in this work, we show that minimal \((\alpha,\beta)\)-modules can be computed in polynomial time, and we generalize series and parallel operation between graphs. This leads to \((\alpha,\beta)\)-cographs which have interesting properties. We study how to generalize Gallai's theorem corresponding to the case for \(\alpha=\beta=0\), but unfortunately we give evidence that computing such a decomposition tree can be difficult.Deranged matchings: proofs and conjectureshttps://zbmath.org/1532.051362024-05-13T19:39:47.825584Z"Johnston, Daniel"https://zbmath.org/authors/?q=ai:johnston.daniel-r|johnston.daniel-b"Kayll, P. Mark"https://zbmath.org/authors/?q=ai:kayll.peter-mark"Palmer, Cory"https://zbmath.org/authors/?q=ai:palmer.cory-tSummary: We introduce, and partially resolve, a conjecture that brings a three-centuries-old derangements phenomenon and its much younger two-decades-old analogue under the same umbrella. Our tools blend combinatorics and analysis in a medley incorporating Inclusion-Exclusion and Tannery's theorem.Completing the solution of the directed Oberwolfach problem with cycles of equal lengthhttps://zbmath.org/1532.051372024-05-13T19:39:47.825584Z"Lacaze-Masmonteil, Alice"https://zbmath.org/authors/?q=ai:lacaze-masmonteil.aliceOne interesting version of the Oberwolfach problem is concerned with the task of finding a solution to whether $t$ conference attendees can be seated at $k$ round tables seating $k$ consecutive guests over the course of $t-1$ nights, with the condition that each guest is to be seated to the right of every other guest exactly once. The authors show that to completely resolve the directed Oberwolfach problem with cycles of uniform length it is enough to find $\alpha$ and \(m\) for which $K^\ast_\alpha m$ admits a resolvable decomposition into directed cycles of length $m$. The main result of this paper is that for an odd integer $m$ with $m\geqslant 5$, the digraph $K^\ast_2m$ admits a resolvable decomposition into directed cycles of length $m$. This implies a complete resolution of the directed Oberwolfach problem with tables of uniform length $m$ if and only if $(\alpha,m)=\{(1,6),(1,4), (2,3)\}$. Note that here a complete symmetric digraph of order $m$ is denoted by $K^\ast_m$. The proof is very lengthy and is established with the help of several interesting results.
Reviewer: V. Yegnanarayanan (Chennai)Partition line graphs of multigraphs into two subgraphs with large chromatic numbershttps://zbmath.org/1532.051382024-05-13T19:39:47.825584Z"Lv, Jian-Bo"https://zbmath.org/authors/?q=ai:lv.jianbo"Li, Jianxi"https://zbmath.org/authors/?q=ai:li.jianxiSummary: \textit{Y. Wang} and \textit{G. Yu} [J. Graph Theory 101, No. 1, 134--141 (2022; Zbl 1522.05144)] prove an enhanced version of the Erdős-Lovász Tihany conjecture for line graphs of multigraphs. That is, let \(s\), \(t\) and \(\ell\) be arbitrary integers with \(t \geq s \geq 3.5 \ell + 2\), \(\ell \geq 0\). If the line graph \(L(G)\) of some multigraph \(G\) has chromatic number \(s + t - 1 > \omega (L(G))\), then there is a partition \((S, T)\) of the vertex set \(V (L(G))\) such that \(\chi (L(G) [S]) \geq s\) and \(\chi (L(G) [T]) \geq t + \ell\). In this paper, for integers \(s\) and \(t\) with \(t \geq s \geq 7\), we prove that for each line graph \(L(G)\) with \(\chi (L(G)) = s + t - 1 \geq \omega (L(G))\), there is a partition \((S, T)\) of the vertex set \(V (L(G))\) such that \(\chi (L(G) [S]) \geq s\) and \(\chi (L(G) [T]) \geq t + 2\), which slightly improves the recent result of Wang and Yu [loc. cit.] for \(\ell = 2\).The degree and codegree threshold for linear triangle covering in 3-graphshttps://zbmath.org/1532.051392024-05-13T19:39:47.825584Z"Tang, Yuxuan"https://zbmath.org/authors/?q=ai:tang.yuxuan"Ma, Yue"https://zbmath.org/authors/?q=ai:ma.yue.2"Hou, Xinmin"https://zbmath.org/authors/?q=ai:hou.xinminSummary: Given two \(k\)-uniform hypergraphs \(F\) and \(G\), we say that \(G\) has an \(F\)-covering if every vertex in \(G\) is contained in a copy of \(F\). For \(1\leqslant i \leqslant k-1\), let \(c_i (n, F)\) be the least integer such that every \(n\)-vertex \(k\)-uniform hypergraph \(G\) with \(\delta_i(G)> c_i (n, F)\) has an \(F\)-covering. The covering problem has been systematically studied by \textit{V. Falgas-Ravry} and \textit{Y. Zhao} [SIAM J. Discrete Math. 30, No. 4, 1899--1917 (2016; Zbl 1346.05199)]. Last year, \textit{V. Falgas-Ravry} et al. [Comb. Probab. Comput. 30, No. 2, 175--199 (2020; Zbl 1466.05180)] asymptotically determined \(c_1(n, F)\) when \(F\) is the generalized triangle. In this note, we give the exact value of \(c_2 (n, F)\) and asymptotically determine \(c_1(n, F)\) when \(F\) is the linear triangle \(C_6^3\), where \(C_6^3\) is the 3-uniform hypergraph with vertex set \(\{v_1, v_2, v_3, v_4, v_5, v_6\}\) and edge set \(\{v_1v_2v_3, v_3v_4v_5, v_5v_6v_1\}\).Retraction notice to: ``New concepts in the vague graph structure with an application in transportation''https://zbmath.org/1532.051402024-05-13T19:39:47.825584ZRetraction notice to the article [\textit{X. Shi} and \textit{S. Kosari}, J. Funct. Spaces 2022, Article ID 1504397, 11~p. (2022; Zbl 1484.05174)].
From the text: This article has been retracted by Hindawi following an
investigation undertaken by the publisher. This investigation has uncovered evidence of one or more of the following indicators of systematic manipulation of the publication
process.Fuzzy chordal graphs and its propertieshttps://zbmath.org/1532.051412024-05-13T19:39:47.825584Z"Das, Kousik"https://zbmath.org/authors/?q=ai:das.kousik"Samanta, Sovan"https://zbmath.org/authors/?q=ai:samanta.sovan"De, Kajal"https://zbmath.org/authors/?q=ai:de.kajalSummary: Chordal graphs are those graphs which have chords for each cycle of the length \(> 3\). For large graphs/ networks, generally, the number of chords is less in number than the required number of chords to for a chordal graph. By definition, those graphs are not chordal. The algorithms and properties of chordal graphs do not apply to such cases. Also, the strength of the chords is not measured there. This study introduces a relaxation on such number of chords for the definition of chordal graphs. The notion of a fuzzy strong chord is introduced. After that, fuzzy chordal graphs and related properties are developed. The measure of fuzzy strong chords is proposed. Also, as a generation, fuzzy \(k\)-chordal graphs are developed, and isomorphism on a fuzzy chordal graph is defined. At last, area of applications of fuzzy chordal graphs and conclusions with future directions are illustrated.Extension of threshold graphs under complex fuzzy environmenthttps://zbmath.org/1532.051422024-05-13T19:39:47.825584Z"Hameed, Saira"https://zbmath.org/authors/?q=ai:hameed.saira"Akram, Muhammad"https://zbmath.org/authors/?q=ai:akram.muhammad"Mustafa, Noreen"https://zbmath.org/authors/?q=ai:mustafa.noreen"Samanta, Sovan"https://zbmath.org/authors/?q=ai:samanta.sovanSummary: The prime objective of this paper is to introduce a new model of threshold graphs in the complex fuzzy environment that has the capability of handling two-dimensional vague data. The proposed model is called as complex fuzzy threshold graph (CFTG). We introduce certain concepts related to CFTGs including, complex fuzzy alternating 4-cycle, complex fuzzy threshold dimension and complex fuzzy partition number of complex fuzzy graphs. We illustrate these concepts with examples. Further, we investigate some of their properties and discuss proficiency of the presented approach by investigating potential applications related to water source controlling system and internet service providers.Stability, vertex stability, and unfrozenness for special graph classeshttps://zbmath.org/1532.051432024-05-13T19:39:47.825584Z"Gurski, Frank"https://zbmath.org/authors/?q=ai:gurski.frank"Rothe, Jörg"https://zbmath.org/authors/?q=ai:rothe.jorg-matthias"Weishaupt, Robin"https://zbmath.org/authors/?q=ai:weishaupt.robinSummary: \textit{F. Frei} et al. [J. Comput. Syst. Sci. 123, 103--121 (2022; Zbl 1472.68113)] show that the stability, vertex stability, and unfrozenness problems with respect to certain graph parameters are complete for \(\Theta_2^\mathcal{P} \), the class of problems solvable in polynomial time by parallel access to an NP oracle. They studied the common graph parameters \(\alpha \) (the independence number), \(\beta \) (the vertex cover number), \(\omega \) (the clique number), and \(\chi \) (the chromatic number). We complement their approach by providing polynomial-time algorithms solving these problems for special graph classes, namely for graphs with bounded tree-width or bounded clique-width. In order to improve these general time bounds even further, we then focus on trees, forests, bipartite graphs, and co-graphs.A notion of vertex equitability for proper labellingshttps://zbmath.org/1532.051442024-05-13T19:39:47.825584Z"Bensmail, Julien"https://zbmath.org/authors/?q=ai:bensmail.julienSummary: We introduce an equitable version of proper labellings of graphs, where the notion of equitability is with respect to the resulting vertex sums. That is, we are interested in \(k\)-labellings where, when computing the sums of labels incident to the vertices, we get a vertex-colouring that is not proper only, but also equitable. For a given graph \(G\), we are interested in the parameter \(\overline{\chi}_\varSigma (G)\), which is the smallest \(k \geq 1\) (if any) such that \(G\) admits such \(k\)-labellings.
Through examples of particular graph classes, we observe that this new parameter \(\overline{\chi}_\varSigma\) behaves sort of similarly to the parameters \(\chi_\varSigma\) and \(s\), whose parameters lie behind the 1-2-3 Conjecture and the irregularity strength of graphs, in a more or less strong way, depending on the graphs considered. We then prove general bounds on \(\overline{\chi}_\varSigma\), showing that, in some contexts (trees and connected graphs with large minimum degree), this parameter is bounded above by roughly \(\frac{3n}{4}\) for an \(n\)-graph. We also prove that determining \(\overline{\chi}_\varSigma\) is NP-hard in general, and finish off with directions for further work on the topic.On inducing degenerate sums through 2-labellingshttps://zbmath.org/1532.051452024-05-13T19:39:47.825584Z"Bensmail, Julien"https://zbmath.org/authors/?q=ai:bensmail.julien"Hocquard, Hervé"https://zbmath.org/authors/?q=ai:hocquard.herve"Marcille, Pierre-Marie"https://zbmath.org/authors/?q=ai:marcille.pierre-marieSummary: We deal with a variant of the 1-2-3 Conjecture introduced by \textit{Y. Gao} et al. [ibid. 32, No. 4, 1415--1421 (2016; Zbl 1342.05038)]. This variant asks whether all graphs can have their edges labelled with 1 and 2 so that when computing the sums of labels incident to the vertices, no monochromatic cycle appears. In the aforementioned seminal work, the authors mainly verified their conjecture for a few classes of graphs, namely graphs with maximum average degree at most 3 and series-parallel graphs, and observed that it also holds for simple classes of graphs (cycles, complete graphs, and complete bipartite graphs). In this work, we provide a deeper study of this conjecture, establishing strong connections with other, more or less distant notions of graph theory. While this conjecture connects quite naturally to other notions and problems surrounding the 1-2-3 Conjecture, it can also be expressed so that it relates to notions such as the vertex-arboricity of graphs. Exploiting such connections, we provide easy proofs that the conjecture holds for bipartite graphs and 2-degenerate graphs, thus generalising some of the results of Gao et al. [loc. cit.]. We also prove that the conjecture holds for graphs with maximum average degree less than \(\frac{10}{3}\), thereby strengthening another of their results. Notably, this also implies the conjecture holds for planar graphs with girth at least 5. All along the way, we also raise observations and results highlighting why the conjecture might be of greater interest.\(C_4\)-face-magic labelings on odd order projective grid graphshttps://zbmath.org/1532.051462024-05-13T19:39:47.825584Z"Curran, Stephen J."https://zbmath.org/authors/?q=ai:curran.stephen-jamesAn \(F\)-face-magic projective labeling of a graph \(G=(V(G),E(G))\) embedded in the projective plane with the set of faces \(\mathcal{F}(G)\) is a bijective function \(f:V(G)\rightarrow\{1,2,\dots,|V(G)|\}\) with the property that for any \(F\in\mathcal{F}(G)\), the sum of labels of vertices around the face \(F\) is equal to an \(F\)-face-magic value \(S\). An \(F\)-face-magic projective graph is a graph that admits an \(F\)-face-magic projective labeling.
This paper deals with a \(C_4\)-face-magic projective labeling of an \(m\times n\) grid graph, \(\mathcal{P}_{m,n}\), embedded in the projective plane in a natural way. It is shown that for \(m,n\geqslant 2\), \(\mathcal{P}_{m,n}\) admits a \(C_4\)-face-magic projective labeling if and only if \(m\) and \(n\) have the same parity. Furthermore, they show that if \(m\geqslant 3\) and \(n\geqslant 3\) are odd integers, then the \(C_4\)-face-magic value of a \(C_4\)-face-magic projective labeling of \(\mathcal{P}_{m,n}\) belongs to the set \(\{2mn+1,2mn+2,2mn+3\}\). Then, the \(C_4\)-face-magic projective labelings of \(\mathcal{P}_{m,n}\) with \(C_4\)-face-magic value \(2mn + 2\) are characterized.
Reviewer: Faisal Susanto (Bandung)Semi-labeled unrooted binary tree optimization subject to nonnegativityhttps://zbmath.org/1532.051472024-05-13T19:39:47.825584Z"Hosseini, Seyed Soheil"https://zbmath.org/authors/?q=ai:hosseini.seyed-soheil"Wormald, Nick"https://zbmath.org/authors/?q=ai:wormald.nicholas-cSummary: Let \(D_{n \times n}\) denote the distance matrix of \(n\) objects, and let \(T\) be an unrooted binary tree in which the leaves denote those \(n\) objects. We want to find such a tree with the constraint that the edge weights are nonnegative where the distances between the leaves best estimate their corresponding values in \(D\). Accordingly, we have adopted the residual sum of squares (RSS) criterion to minimize the discrepancy between the distance between leaves in the tree and their corresponding distance in \(D\). For this optimization problem, we have designed an iterated local search (ILS) scheme based on the nearest neighbor interchange (NNI) operation to search the neighborhood.
{{\copyright} 2022 The Authors. \textit{Networks} published by Wiley Periodicals LLC.}Weisfeiler-Leman indistinguishability of graphonshttps://zbmath.org/1532.051482024-05-13T19:39:47.825584Z"Böker, Jan"https://zbmath.org/authors/?q=ai:boker.janSummary: The color refinement algorithm is mainly known as a heuristic method for graph isomorphism testing. It has surprising but natural characterizations in terms of, for example, homomorphism counts from trees and solutions to a system of linear equations. \textit{J. Grebik} and \textit{I. Rocha} [Combinatorica 42, No. 3, 365--404 (2022; Zbl 07614042)] have recently shown how color refinement and notions that characterize it generalize to graphons, which emerged as limit objects in the theory of dense graph limits. In particular, they show that these characterizations are still equivalent in the graphon case. The \(k\)-dimensional Weisfeiler-Leman algorithm \((k\)-WL) is a more powerful variant of color refinement that colors \(k\)-tuples instead of single vertices, where the terms \(1\)-WL and color refinement are often used interchangeably since they compute equivalent colorings. We show how to adapt the result of Grebík and Rocha [loc. cit.] to \(k\)-WL or, in other words, how \(k\)-WL and its characterizations generalize to graphons. In particular, we obtain characterizations in terms of homomorphism densities from multigraphs of bounded treewidth and linear equations. We give a simple example that parallel edges make a difference in the more general case of graphons, which means that, there, the equivalence between \(1\)-WL and color refinement does not hold anymore. We also show how this equivalence can be recovered by defining a variant of \(k\)-WL that corresponds to homomorphism densities from simple graphs of bounded treewidth.Connectivity of old and new models of friends-and-strangers graphshttps://zbmath.org/1532.051492024-05-13T19:39:47.825584Z"Milojević, Aleksa"https://zbmath.org/authors/?q=ai:milojevic.aleksaSummary: In this paper, we investigate the connectivity of friends-and-strangers graphs, which were introduced by \textit{C. Defant} and \textit{N. Kravitz} [Comb. Theory 1, Paper No. 6, 34 p. (2021; Zbl 1498.05148)]. We begin by considering friends-and-strangers graphs arising from two random graphs and consider the threshold probability at which such graphs attain maximal connectivity. We slightly improve the lower bounds on the threshold probabilities, thus disproving two conjectures of \textit{N. Alon} et al. [J. Comb. Theory, Ser. B 158, Part 1, 3--42 (2023; Zbl 1504.05146)]. We also improve the upper bound on the threshold probability in the case of random bipartite graphs, and obtain a tight bound up to a factor of \(n^{o(1)}\). Further, we introduce a generalization of the notion of friends-and-strangers graphs in which vertices of the starting graphs are allowed to have multiplicities and obtain generalizations of previous results of \textit{R. M. Wilson} [ibid. 16, 86--96 (1974; Zbl 0285.05110)] and of Defant and Kravitz [loc. cit.] in this new setting.On the tree-depth and tree-width in heterogeneous random graphshttps://zbmath.org/1532.051502024-05-13T19:39:47.825584Z"Shang, Yilun"https://zbmath.org/authors/?q=ai:shang.yilunSummary: In this note, we investigate the tree-depth and tree-width in a heterogeneous random graph obtained by including each edge \(e_{ij}\) (\(i\neq j\)) of a complete graph \(K_n\) over \(n\) vertices independently with probability \(p_n(e_{ij})\). When the sequence of edge probabilities satisfies some density assumptions, we show both tree-depth and tree-width are of linear size with high probability. Moreover, we extend the method to random weighted graphs with non-identical edge weights and capture the conditions under which with high probability the weighted tree-depth is bounded by a constant.First-passage percolation on random simple triangulationshttps://zbmath.org/1532.051512024-05-13T19:39:47.825584Z"Stufler, Benedikt"https://zbmath.org/authors/?q=ai:stufler.benediktSummary: We study first-passage percolation on random simple triangulations and their dual maps with independent identically distributed link weights. Our main result shows that the first-passage percolation distance concentrates in an \(o_p(n^{1/4})\) window around a constant multiple of the graph distance. Our approach follows the proof strategy by \textit{N. Curien} and \textit{J.-F. Le Gall} [Ann. Sci. Éc. Norm. Supér. (4) 52, No. 3, 631--701 (2019; Zbl 1429.05188)], but we have to overcome several obstacles specific to simple triangulations.Opinion forming in Erdős-Rényi random graph and expandershttps://zbmath.org/1532.051522024-05-13T19:39:47.825584Z"Zehmakan Ahad, N."https://zbmath.org/authors/?q=ai:zehmakan-ahad.nSummary: Assume for a graph \(G=(V,E)\) and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the Erdős-Rényi random graph \(\mathcal{G}_{n,p}\) and regular expanders. First we consider the behavior of the majority model on \(\mathcal{G}_{n,p}\) with an initial random configuration, where each node is blue independently with probability \(p_b\) and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely \(\frac{\log n}{n}\). Furthermore, we say a graph \(G\) is \(\lambda\)-expander if the second-largest absolute eigenvalue of its adjacency matrix is \(\lambda\). We prove that for a \(\Delta\)-regular \(\lambda\)-expander graph if \(\lambda/\Delta\) is sufficiently small, then the majority model by starting from \((\frac{1}{2}-\delta)n\) blue nodes (for an arbitrarily small constant \(\delta>0\)) results in fully red configuration in sub-logarithmically many rounds. Roughly speaking, this means the majority model is an ``efficient'' and ``fast'' density classifier on regular expanders. As a by-product of our results, we show regular Ramanujan graphs are asymptotically optimally immune, that is for an \(n\)-node \(\Delta\)-regular Ramanujan graph if the initial number of blue nodes is \(s\le\beta n\), the number of blue nodes in the next round is at most \(\frac{cs}{\Delta}\) for some constants \(c,\beta>0\). This settles an open problem by \textit{D. Peleg} [Lect. Notes Comput. Sci. 8001, 168--179 (2014; Zbl 1486.68137)].
For the entire collection see [Zbl 1407.68036].Fractal networks on Dürer-type polygonhttps://zbmath.org/1532.051532024-05-13T19:39:47.825584Z"Huang, Yuke"https://zbmath.org/authors/?q=ai:huang.yuke"Zhang, Hanxiong"https://zbmath.org/authors/?q=ai:zhang.hanxiong"Xue, Yumei"https://zbmath.org/authors/?q=ai:xue.yumeiSummary: Dürer's pentagon is known to the artist Albrecht Dürer. In this paper, we consider directed networks generated by Dürer-type polygons. We aim to present a study on some properties of these networks, such as degree distribution, clustering coefficient and average path length. We show that such networks have the scale-free effect, but do not have the small-world effect.Edge separators for graphs excluding a minorhttps://zbmath.org/1532.051542024-05-13T19:39:47.825584Z"Joret, Gwenaël"https://zbmath.org/authors/?q=ai:joret.gwenael"Lochet, William"https://zbmath.org/authors/?q=ai:lochet.william"Seweryn, Michał T."https://zbmath.org/authors/?q=ai:seweryn.michal-tSummary: We prove that every \(n\)-vertex \(K_t\)-minor-free graph \(G\) of maximum degree \(\Delta\) has a set \(F\) of \(O(t^2(\log t)^{1/4}\sqrt{\Delta n})\) edges such that every component of \(G - F\) has at most \(n/2\) vertices. This is best possible up to the dependency on \(t\) and extends earlier results of \textit{K. Diks} et al. [J. Algorithms 14, No. 2, 258--279 (1993; Zbl 0764.68112)] for planar graphs, and of \textit{O. Sýkora} and \textit{I. Vrťo} [Theor. Comput. Sci. 112, No. 2, 419--429 (1993; Zbl 0772.05057)] for bounded-genus graphs. Our result is a consequence of the following more general result: The line graph of \(G\) is isomorphic to a subgraph of the strong product \(H \boxtimes K_{\lfloor p \rfloor}\) for some graph \(H\) with treewidth at most \(t-2\) and \(p = \sqrt{(t-3)\Delta |E(G)|} + \Delta\).A graph minor condition for graphs to be \(k\)-linkedhttps://zbmath.org/1532.051552024-05-13T19:39:47.825584Z"Maezawa, Shun-ichi"https://zbmath.org/authors/?q=ai:maezawa.shunichiSummary: A graph is called \(k\)-linked, if for any \(2 k\) distinct vertices \(x_1 , x_2 , \ldots , x_k\) , \(y_1 , y_2 , \ldots , y_k\), there exist \(k\) vertex disjoint paths \(P_1 , P_2 , \ldots , P_k\) such that \(P_i\) connects \(x_i\) and \(y_i\) for each \(1 \leq i \leq k\). \textit{N. Robertson} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 63, No. 1, 65--110 (1995; Zbl 0823.05038)] showed that every \(2 k\)-connected graph having \(K_{3 k}\) as a minor is \(k\)-linked. \textit{G. Chen} et al. [J. Graph Theory 49, No. 1, 75--91 (2005; Zbl 1067.05072)] proved that every 6-connected graph having \(K_9^-\) as a minor is 3-linked, where \(K_k^{- i}\) is the graph obtained from the complete graph with \(k\) vertices by deleting exactly \(i\) edges. We improve these two results by showing that every \(2 k\)-connected graph having the graph obtained from \(K_{3 k}\) by deleting independent \(k\) edges as a minor is \(k\)-linked.Improved pyrotechnics: closer to the burning number conjecturehttps://zbmath.org/1532.051562024-05-13T19:39:47.825584Z"Bastide, Paul"https://zbmath.org/authors/?q=ai:bastide.paul"Bonamy, Marthe"https://zbmath.org/authors/?q=ai:bonamy.marthe"Bonato, Anthony"https://zbmath.org/authors/?q=ai:bonato.anthony"Charbit, Pierre"https://zbmath.org/authors/?q=ai:charbit.pierre"Kamali, Shahin"https://zbmath.org/authors/?q=ai:kamali.shahin"Pierron, Théo"https://zbmath.org/authors/?q=ai:pierron.theo"Rabie, Mikaël"https://zbmath.org/authors/?q=ai:rabie.mikaelSummary: The Burning Number Conjecture claims that for every connected graph \(G\) of order \(n\), its burning number satisfies \(b(G) \le \lceil \sqrt{n}\, \rceil\). While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its growth, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph \(G\) of order \(n\), given by \(b(G) \le \sqrt{4n/3} + 1\), improving on the previously known \(\sqrt{3n/2}+O(1)\) bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least \(3\) and holds for all large enough graphs with minimum degree at least \(4\). The previous best-known result was for graphs with minimum degree \(23\).On the first Zagreb index of graphs with self-loopshttps://zbmath.org/1532.051572024-05-13T19:39:47.825584Z"Shetty, Shashwath S."https://zbmath.org/authors/?q=ai:shetty.shashwath-s"Bhat K., Arathi"https://zbmath.org/authors/?q=ai:bhat-k.arathiSummary: Some of the most comprehensively studied degree-based topological indices are the Zagreb indices. The first Zagreb index \(M_{1}(G)\) of a graph \(G\) is defined as the sum of squares of the degrees of the vertices. Let \(X \subseteq V(G)\) and let \(G_{X}\) be the graph obtained from the simple graph \(G\), by attaching a self-loop to each of its vertices belonging to \(X\). In this article, some sharp bounds for the first Zagreb index of graphs with self-loops using various parameters has been put forward.The sequence of prime gaps is graphichttps://zbmath.org/1532.051582024-05-13T19:39:47.825584Z"Erdős, Péter L."https://zbmath.org/authors/?q=ai:erdos.peter-l"Harcos, Gergely"https://zbmath.org/authors/?q=ai:harcos.gergely"Kharel, Shubha R."https://zbmath.org/authors/?q=ai:kharel.shubha-r"Maga, Péter"https://zbmath.org/authors/?q=ai:maga.peter"Mezei, Tamás Róbert"https://zbmath.org/authors/?q=ai:mezei.tamas-robert"Toroczkai, Zoltán"https://zbmath.org/authors/?q=ai:toroczkai.zoltanSummary: Let us call a simple graph on \(n\geqslant 2\) vertices a prime gap graph if its vertex degrees are 1 and the first \(n-1\) prime gaps. We show that such a graph exists for every large \(n\), and in fact for every \(n\geqslant 2\) if we assume the Riemann hypothesis. Moreover, an infinite sequence of prime gap graphs can be generated by the so-called degree preserving growth process. This is the first time a naturally occurring infinite sequence of positive integers is identified as graphic. That is, we show the existence of an interesting, and so far unique, infinite combinatorial object.Lower bounds for the Turán densities of daisieshttps://zbmath.org/1532.051612024-05-13T19:39:47.825584Z"Ellis, David"https://zbmath.org/authors/?q=ai:ellis.david-b.1|ellis.david-c-p|ellis.david-b|ellis.david-m|ellis.david-christopher"King, Dylan"https://zbmath.org/authors/?q=ai:king.dylan-aSummary: For integers \(r \geqslant 3\) and \(t \geqslant 2\), an \(r\)-uniform \(t\)-daisy \(\mathcal{D}^t_r\) is a family of \(\binom{2t}{t} r\)-element sets of the form \[\{S \cup T : T\subset U, |T|=t \}\] for some sets \(S, U\) with \(|S|=r-t, |U|=2t\) and \(S \cap U = \emptyset\). It was conjectured by \textit{B. Bollobás} et al. [Comb. Probab. Comput. 20, No. 5, 743--747 (2011; Zbl 1293.05381)] (and independently by Bukh) that the Turán densities of \(t\)-daisies satisfy \(\lim\limits_{r \to \infty} \pi(\mathcal{D}_r^t) = 0\) for all \(t \geqslant 2\); this has become a well-known problem, and it is still open for all values of \(t\). In this paper, we give lower bounds for the Turán densities of \(r\)-uniform \(t\)-daisies. To do so, we introduce (and make some progress on) the following natural problem in additive combinatorics: for integers \(m \geqslant 2t \geqslant 4\), what is the maximum cardinality \(g(m, t)\) of a subset \(R\) of \(\mathbb{Z}/m\mathbb{Z}\) such that for any \(x \in \mathbb{Z}/m\mathbb{Z}\) and any \(2t\)-element subset \(X\) of \(\mathbb{Z}/m\mathbb{Z}\), there are \(t\) distinct elements of \(X\) whose sum is not in the translate \(x+R\)? This is a slice-analogue of an extremal Hilbert cube problem considered by \textit{D. S. Gunderson} and \textit{V. Rödl} [Comb. Probab. Comput. 7, No. 1, 65--79 (1998; Zbl 0892.05050)] as well as \textit{J. Cilleruelo} and \textit{R. Tesoro} [Combinatorica 38, No. 3, 511--546 (2018; Zbl 1438.11019)].\(r\)-cross \(t\)-intersecting families via necessary intersection pointshttps://zbmath.org/1532.051632024-05-13T19:39:47.825584Z"Gupta, Pranshu"https://zbmath.org/authors/?q=ai:gupta.pranshu"Mogge, Yannick"https://zbmath.org/authors/?q=ai:mogge.yannick"Piga, Simón"https://zbmath.org/authors/?q=ai:piga.simon"Schülke, Bjarne"https://zbmath.org/authors/?q=ai:schulke.bjarneThe paper generalizes the classical theorem of \textit{A. J. W. Hilton} and \textit{E. C. Milner} [Q. J. Math., Oxf. II. Ser. 18, 369--384 (1967; Zbl 0168.26205)] for cross-intersecting families in various directions. Let \(n\), \(r\) and \(t\) be positive integers, where \(r \geq 2\). If \(\mathcal{F}_1, \dots, \mathcal{F}_r\) are families of sets such that \(|\bigcap_{i=1}^r F_i| \geq t\) for every \((F_1, \dots, F_r) \in \mathcal{F}_1 \times \dots \times \mathcal{F}_r\), then they are said to be \(r\)-cross \(t\)-intersecting. The authors determine the maximum sum of sizes of \(r\) non-empty \(r\)-cross \(t\)-intersecting families \(\mathcal{F}_1, \dots, \mathcal{F}_r\) of subsets of \([n] = \{1, \dots, n\}\). They also address the more general setting where \(\mathcal{F}_1, \dots, \mathcal{F}_r\) are equipped with certain natural and important measures, such as the product measure and the uniform measure. For each \(i \in [r]\), let \(\mu_i \colon \{0, 1, \dots, n\} \rightarrow \mathbb{R}_{\geq 0}\), and let \(\mu_i(\mathcal{F}_i)\) denote the measure \(\sum_{F \in \mathcal{F}_i} \mu_i(|F|)\) of \(\mathcal{F}_i\). The authors determine the largest possible value of \(\sum_{i=1}^r \mu_i(\mathcal{F}_i)\) for the case where \(\mu_1, \dots, \mu_r\) are non-increasing. For \(1 \leq k_1 \leq \cdots \leq k_r \leq n\), they determine the largest possible value of \(\sum_{i=1}^r \mu_i(\mathcal{F}_i)\) for the case where \(n \geq 2k_r + k_2 - t\) and \(\emptyset \neq \mathcal{F}_i \subseteq \{A \subseteq [n] \colon |A| \leq k_i\}\) for each \(i \in [r]\). By taking \(k_1 = \cdots = k_r = k\), \(\mu_1(k) = \dots = \mu_r(k) = 1\) and \(\mu_1(j) = \dots = \mu_r(j) = 0\) for each \(j \in \{0, 1, \dots, n\} \backslash \{k\}\), the maximum sum of sizes of \(r\) non-empty \(r\)-cross \(t\)-intersecting families of \(k\)-element subsets of \([n]\) is obtained.
Reviewer: Peter Borg (Msida)Transversals and colorings of simplicial sphereshttps://zbmath.org/1532.051662024-05-13T19:39:47.825584Z"Briggs, Joseph"https://zbmath.org/authors/?q=ai:briggs.joseph"Dobbins, Michael Gene"https://zbmath.org/authors/?q=ai:dobbins.michael-gene"Lee, Seunghun"https://zbmath.org/authors/?q=ai:lee.seunghunSummary: Motivated from the surrounding property of a point set in \(\mathbb{R}^d\) introduced by \textit{A. F. Holmsen} et al. [Combinatorica 28, No. 6, 633--644 (2008; Zbl 1199.52013)], we consider the transversal number and chromatic number of a simplicial sphere. As an attempt to give a lower bound for the maximum transversal ratio of simplicial \(d\)-spheres, we provide two infinite constructions. The first construction gives infinitely many \((d+1)\)-dimensional simplicial polytopes with the transversal ratio exactly \(2/(d+2)\) for every \(d \geq 2\). In the case of \(d=2\), this meets the previously well-known upper bound 1/2 tightly. The second gives infinitely many simplicial 3-spheres with the transversal ratio greater than 1/2. This was unexpected from what was previously known about the surrounding property. Moreover, we show that, for \(d \geq 3\), the facet hypergraph \({\mathcal{F}}(\mathsf{K})\) of a \(d\)-dimensional simplicial sphere \(\mathsf{K}\) has the chromatic number \(\chi ({\mathcal{F}}(\mathsf{K})) \in O \big(n^{(\lceil d/2 \rceil -1)/d}\big)\), where \(n\) is the number of vertices of \(\mathsf{K}\). This slightly improves the upper bound previously obtained by \textit{C. G. Heise} et al. [Discrete Comput. Geom. 52, No. 4, 663--679 (2014; Zbl 1306.05060)].Pure pairs. IX: Transversal treeshttps://zbmath.org/1532.051672024-05-13T19:39:47.825584Z"Scott, Alex"https://zbmath.org/authors/?q=ai:scott.alexander-d"Seymour, Paul"https://zbmath.org/authors/?q=ai:seymour.paul-d"Spirkl, Sophie T."https://zbmath.org/authors/?q=ai:spirkl.sophie-theresaLet \(k > 0\), and \(G\) be a graph, with vertex set partitioned into \(k\) subsets (or blocks) of approximately equal size. An induced subgraph of \(G\) is said to be transversal (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly \(k\) vertices). In \(G\) a pair \((X,Y)\) of disjoint subsets of \(V(G)\) such that either all edges between \(X\), \(Y\) are present or none are called a pure pair. In the present context, the authors are interested in pure pairs \((X,Y)\) where each of \(X\), \(Y\) is a subset of one of the blocks and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.
For Part VIII see [the authors, ``Pure pairs. VIII. Excluding a sparse graph'', Preprint, \url{arXiv:2201.04062}].
Reviewer: Ioan Tomescu (Bucureşti)Improved lower bounds for multiplicative square-free sequenceshttps://zbmath.org/1532.051682024-05-13T19:39:47.825584Z"Pach, Péter Pál"https://zbmath.org/authors/?q=ai:pach.peter-pal"Vizer, Máté"https://zbmath.org/authors/?q=ai:vizer.mateSummary: In this short paper we improve an almost 30 years old result of \textit{P. Erdős} et al. [Eur. J. Comb. 16, No. 6, 567--588 (1995; Zbl 0840.11010)] on lower bounds for the size of multiplicative square-free sequences. Our construction uses Berge-cycle free hypergraphs that is interesting in its own right.Equidistribution of set-valued statistics on standard Young tableaux and transversalshttps://zbmath.org/1532.051762024-05-13T19:39:47.825584Z"Zhou, Robin D. P."https://zbmath.org/authors/?q=ai:zhou.robin-d-p"Yan, Sherry H. F."https://zbmath.org/authors/?q=ai:yan.sherry-h-fSummary: As a natural generalization of permutations, transversals of Young diagrams play an important role in the study of pattern avoiding permutations. Let \(\mathcal{T}_{\lambda}(\tau)\) and \(\mathcal{ST}_{\lambda}(\tau)\) denote the set of \(\tau\)-avoiding transversals and \(\tau\)-avoiding symmetric transversals of a Young diagram \(\lambda\), respectively. In this paper, we are mainly concerned with the distribution of the peak set and the valley set on standard Young tableaux and pattern avoiding transversals. In particular, we prove that the peak set and the valley set are equidistributed on the standard Young tableaux of shape \(\lambda /\mu\) for any skew diagram \(\lambda /\mu\). The equidistribution enables us to show that the peak set is equidistributed over \(\mathcal{T}_{\lambda}(12 \cdots k\tau)\) (resp. \(\mathcal{ST}_{\lambda}(12 \cdots k\tau))\) and \(\mathcal{T}_{\lambda}(k\cdots 21\tau)\) (resp. \(\mathcal{ST}_{\lambda}(k\cdots 21\tau))\) for any Young diagram \(\lambda\) and any permutation \(\tau\) of \(\{k+1, k+2, \ldots, k+m\}\) with \(k, m\geq 1\). Our results are refinements of the result of \textit{J. Backelin} et al. [Adv. Appl. Math. 38, No. 2, 133--148 (2007; Zbl 1127.05002)] which states that \(|\mathcal{T}_{\lambda}(12\cdots k\tau) |=|\mathcal{T}_{\lambda}(k\cdots 21\tau)|\) and the result of \textit{M. Bousquet-Mélou} and \textit{E. Steingrímsson} [J. Algebr. Comb. 22, No. 4, 383--409 (2005; Zbl 1085.05002)] which states that \(|\mathcal{ST}_{\lambda}(12\cdots k \tau) |=| \mathcal{ST}_{\lambda}(k\cdots 21 \tau)|\). As applications, we are able to
\begin{itemize}
\item confirm a recent conjecture posed by \textit{S. H. F. Yan} et al. [ibid. 58, No. 1, 69--94 (2023; Zbl 1518.05003)] which asserts that the peak set is equidistributed over \(12 \cdots k\tau\)-avoiding involutions and \(k \cdots 21\tau\)-avoiding involutions;
\item prove that alternating involutions avoiding the pattern \(12 \cdots k\tau\) are equinumerous with alternating involutions avoiding the pattern \(k \cdots 21\tau\), paralleling the result of \textit{J. Backelin} et al. [loc. cit.] for permutations, the result of Bousquet-Mélou and Steingrímsson [loc. cit.] for involutions, and the result of \textit{S. H. F. Yan} [Electron. J. Comb. 20, No. 3, Research Paper P58, 19 p. (2013; Zbl 1298.05013)] for alternating permutations.
\end{itemize}Riemann-Hurwitz theorem and Riemann-Roch theorem for hypermapshttps://zbmath.org/1532.051772024-05-13T19:39:47.825584Z"Cheng, Mengnan"https://zbmath.org/authors/?q=ai:cheng.mengnan"Cao, Tingbin"https://zbmath.org/authors/?q=ai:cao.tingbinSummary: In this paper, we try to answer some questions raised by \textit{L. Cangelmi} [Eur. J. Comb. 33, No. 7, 1444--1448 (2012; Zbl 1244.05110)]. We reinterpret the Riemann-Hurwitz theorem of orientable algebraic hypermaps by introducing tripartite graph morphisms and obtain Riemann-Roch theorems for orientable hypermaps by defining the divisor of a function \(f\) on darts. In addition, we extend Riemann-Roch theorem to non-orientable hypermaps by suitably replacing the orientable genus with the non-orientable genus. Finally, as an application of the Riemann-Hurwitz theorem, we establish the second main theorem from the viewpoint of Nevanlinna theory.Tropical moduli spaces of rational graphically stable curveshttps://zbmath.org/1532.051782024-05-13T19:39:47.825584Z"Fry, Andy"https://zbmath.org/authors/?q=ai:fry.andySummary: The tropical moduli space \(\mathcal{M}_{0,n}^{\text{trop}}\) is a cone complex which parameterizes leaf-labeled metric trees called tropical curves. We introduce graphic stability and describe a refinement of the cone complex given by radial alignment. We prove that given a complete multipartite graph \(\Gamma\), the moduli space of radially aligned \(\Gamma\)-stable tropical curves can be given the structure of a balanced fan. This fan structure coincides with the Bergman fan of the cycle matroid of \(\Gamma\).On graphs in which the neighborhoods of vertices are edge-regular graphs without 3-clawshttps://zbmath.org/1532.051792024-05-13T19:39:47.825584Z"Chen, M."https://zbmath.org/authors/?q=ai:chen.mingzhu"Makhnev, A. A."https://zbmath.org/authors/?q=ai:makhnev.a-a-jun|makhnev.aleksandr-a"Nirova, M. S."https://zbmath.org/authors/?q=ai:nirova.marina-sefovnaSummary: The triangle-free Krein graph \(\operatorname{Kre}(r)\) is strongly regular with parameters \(((r^2+3r)^2,r^3+3r^2+r,0,r^2+r)\). The existence of such graphs is known only for \(r=1\) (the complement of the Clebsch graph) and \(r=2\) (the Higman-Sims graph). \textit{A. L. Gavrilyuk} and \textit{A. A. Makhnev} [Dokl. Math. 72, No. 1, 591--594 (2005; Zbl 1126.05102); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 403, No. 6, 727--730 (2005)] proved that the graph \(\operatorname{Kre}(3)\) does not exist. Later \textit{A. A. Makhnev} [ibid. 96, No. 1, 348--350 (2017; Zbl 1373.05221); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 475, No. 3, 251--253 (2016)] proved that the graph \(\operatorname{Kre}(4)\) does not exist. The graph \(\operatorname{Kre}(r)\) is the only strongly regular triangle-free graph in which the antineighborhood of a vertex \(\operatorname{Kre}(r)^{\prime}\) is strongly regular. The graph \(\operatorname{Kre}(r)^{\prime}\) has parameters \(((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)\). This work clarifies Makhnev's result on graphs [loc. cit.] in which the neighborhoods of vertices are strongly regular graphs without 3-cocliques. As a consequence, it is proved that the graph \(\operatorname{Kre}(r)\) exists if and only if the graph \(\operatorname{Kre}(r)^{\prime}\) exists and is the complement of the block graph of a quasi-symmetric 2-design.Mixing is hard for triangle-free reflexive graphshttps://zbmath.org/1532.051812024-05-13T19:39:47.825584Z"Kim, Hyobeen"https://zbmath.org/authors/?q=ai:kim.hyobeen"Lee, Jae-baek"https://zbmath.org/authors/?q=ai:lee.jae-baek"Siggers, Mark"https://zbmath.org/authors/?q=ai:siggers.mark-hSummary: In the problem \(\operatorname{Mix} ( H )\) one is given a graph \(G\) and must decide if the Hom-graph \(\mathcal{Hom} ( G , H )\) is connected. We show that if \(H\) is a triangle-free reflexive graph with at least one cycle, \( \operatorname{Mix} ( H )\) is coNP-complete. The main part of this is a reduction to the problem \(\operatorname{NonFlat} ( \mathcal{H} )\) for a simplicial complex \(\mathcal{H} \), in which one is given a simplicial complex \(\mathcal{G}\) and must decide if there are any simplicial maps \(\phi\) from \(\mathcal{G}\) to \(\mathcal{H}\) under which some 1-cycles of \(\mathcal {G}\) maps to homologically nontrivial cycle of \(\mathcal{H} \). We show that for any reflexive graph \(H\), if the clique complex \(\mathcal{H}\) of \(H\) has a free, nontrivial homology group \(H_1 ( \mathcal{H} )\), then \(\operatorname{NonFlat} ( \mathcal{H} )\) is NP-complete.The typical approximate structure of sets with bounded sumsethttps://zbmath.org/1532.111372024-05-13T19:39:47.825584Z"Campos, Marcelo"https://zbmath.org/authors/?q=ai:campos.marcelo"Coulson, Matthew"https://zbmath.org/authors/?q=ai:coulson.matthew"Serra, Oriol"https://zbmath.org/authors/?q=ai:serra.oriol"Wötzel, Maximilian"https://zbmath.org/authors/?q=ai:wotzel.maximilianAn important problem in additive combinatorics is to understand the structure of a set \(A\) subject to some additive constraint in an additive group. A theorem of \textit{G. A. Freiman} [Foundations of a structural theory of set addition. Translation from Russian. Providence, RI: American Mathematical Society (AMS) (1973; Zbl 0271.10044)] provides such a structural result in terms of arithmetic progressions when \(A+A\) is small. Classical results like the Kneser theorem in abelian groups or the Brunn-Minkowski inequality in Euclidean spaces naturally address a similar problem for the addition of distinct sets \(A+B\). When \(A+A\) is very small, then another theorem of Freiman shows that the set is dense in one arithmetic progression, and this result has been also extended to \(A+B\) by \textit{V. F. Lev} and \textit{P. Y. Smeliansky} [Acta Arith. 70, No. 1, 85--91 (1995; Zbl 0817.11005)]. Discrete versions of the Brunn-Minkowski inequality have also been addressed for distinct sets by \textit{I. Z. Ruzsa} [Combinatorica 14, No. 4, 485--490 (1994; Zbl 0815.11012)] and \textit{R. J. Gardner} and \textit{P. Gronchi} [Trans. Am. Math. Soc. 353, No. 10, 3995--4024 (2001; Zbl 0977.52019)].
Motivated by the Cameron-Erdős conjecture on the number of sum-free sets in \(\{1,2,\dots,n\}\), there has been a quest to analyze the typical structure of sets satisfying some additive constraint. One of the most efficient techniques to address this problem is the method of hypergraph containers first introduced by \textit{J. Balogh} et al. [J. Am. Math. Soc. 28, No. 3, 669--709 (2015; Zbl 1310.05154)] and independently by \textit{D. Saxton} and \textit{A. Thomason} [Invent. Math. 201, No. 3, 925--992 (2015; Zbl 1320.05085)]. The usual structure of this method is to essentially have two separate ingredients, the first being a result about independent sets in hypergraphs following certain degree conditions and the second being supersaturation and stability results. \textit{N. Alon} et al. [Proc. Lond. Math. Soc. (3) 108, No. 1, 44--72 (2014; Zbl 1284.05024)] posed a conjecture on the number of sets \(A\) of size \(s \ge C\log n\) contained in \(\{1,2,\dots,n\}\) which have sumset \(|A+A| \le K|A|\), \(K \le s/C\). This was proved by \textit{B. Green} and \textit{R. Morris} [Combinatorica 36, No. 2, 129--159 (2016; Zbl 1399.11168)] for \(K\) constant and extended by \textit{M. Campos} [Isr. J. Math. 236, No. 2, 711--726 (2020; Zbl 1439.05019)] to \(K = o(s/(\log n)^3)\). These counting results are naturally connected to the typical structure of these sets, showing that they are almost contained in an arithmetic progression of length \((1+o(1))Ks/2\). The authors build on the later work by Campos to adapt the result to distinct sets. The main result of the paper is the following.
Theorem 1.1. Let \(n \ge s_2 \ge s_1 = \Omega(s_2)\) be integers, and let \(m\) be an integer satisfying \(s_1+s_2 \le m = o(s_2^2/(\log n)^3)\). Then, for almost all sets \(X_1, X_2 \subset \{1,2,\dots,n\}\) such that \(|X_i| = s_i\) and \(|X_1+X_2| \le m\), there exist arithmetic progressions \(P_1\) and \(P_2\) with the same common difference of size \(|P_i| = (1+o(1))s_im/(s_1+s_2)\) and \(|X_i \backslash P_i| = o(s_i)\).
This theorem is derived from Theorem 4.1. The proof requires that the cardinalities of the two sets \(X_1, X_2\) are not arbitrarily far apart. But this seems natural: Even if the condition \(|X_1| = \Omega(|X_2|)\) can be weakened, it is not clear that a nontrivial structural result should hold when one set is much smaller than the other.
For an abelian group \(G\) an any positive real number \(t\), let \(\beta(t) = \max\{|H|; H \le G, |H| \le t\}\). The authors also prove the following counting analogue to Theorem 1.1.
Theorem 1.2. Let \(G\) be an abelian group. Let \(n \ge s_2 \ge s_1 = \Omega(s_2)\) be integers, and let \(m\) be an integer satisfying \(s_1+s_2 \le m = o(s_2^2/[(\log s_2)^4 (\log n)^3])\). Then, for any \(F_1, F_2 \subset G\) with \(|F_i| = n\), the number of pairs of sets \((X_1,X_2) \in 2^{F_1} \times 2^{F_2}\) such that \(|X_i| = s_i\) and \(|X_1+X_2| \le m\) is at most \(2^{o(s_2)} \binom{\frac{s_1}{s_1+s_2}(m+\beta)}{s_1} \binom{\frac{s_2}{s_1+s_2}(m+\beta)}{s_2}\), where \(\beta = \beta((1+o(1))m)\).
For some groups, it is possible to get rid of the \(\log s_2\) term in the upper bound of \(m\) in Theorem 1.2. An example discussed in [\textit{M. Campos}, Isr. J. Math. 236, No. 2, 711--726 (2020; Zbl 1439.05019)] that can be adapted to the asymmetric case shows that the range of \(m\) for which Theorem 1.2 holds cannot be improved to \(m = \Omega(s_2^2/\log n)\). It is not clear whether the same holds true for Theorem 1.1, and an interesting question would be to investigate whether it might be true for any \(m = o(s_2^2)\).
Reviewer: Sávio Ribas (Belo Horizonte)Counting square-free monomial Cremona mapshttps://zbmath.org/1532.130062024-05-13T19:39:47.825584Z"Costa, Bárbara"https://zbmath.org/authors/?q=ai:costa.barbara"Dias, Thiago"https://zbmath.org/authors/?q=ai:dias.thiago"Gondim, Rodrigo"https://zbmath.org/authors/?q=ai:gondim.rodrigo"Machado, Ricardo"https://zbmath.org/authors/?q=ai:machado.ricardo-j|machado.ricardo-nThe paper under review is focused on the investigation of special Cremona transformations of \( \mathbb{P}^{n-1} \) called square-free Cremona maps. The important new result proved in the paper discusses the equivalence classes of square-free monomial Cremona transformations of \( \mathbb{P}^5\). The particular case of such cubic Cremona transformations is considered in detail. The same classification task is solved for quadratic square-free Cremona maps of \( \mathbb{P}^{n-1}\) when the number \(n=7,8,9.10,11\), and for cubic square-free Cremona maps of \( \mathbb{P}^6 \).
Reviewer: Georgi Hristov Georgiev (Shumen)A combinatorial description of the dormant Miura transformationhttps://zbmath.org/1532.140672024-05-13T19:39:47.825584Z"Wakabayashi, Yasuhiro"https://zbmath.org/authors/?q=ai:wakabayashi.yasuhiroThe purpose of this paper is to give combinatorial descriptions of dormant generic Miura \(sl_2\)-opers. The combinatorial objects that used are certain branch numberings of \(3\)-regular i.e., trivalent graphs. The author describes Miura \(sl_2\)-opers and Miura transformations in terms of graph-theoretic objects, and constructs a bijective correspondence between dormant generic Miura \(sl_2\)-opers on a totally degenerate curve in positive characteristic and certain branch numberings on a \(3\)-regular graph. This correspondence allows him to completely identify dormant generic Miura \(sl_2\)-opers on totally degenerate curves. Also, he investigates how this result can be related to the combinatorial description of dormant \(sl_2\)-opers given by \textit{S. Mochizuki} [Foundations of \(p\)-adic Teichmüller theory. Providence, RI: American Mathematical Society (1999; Zbl 0969.14013)] and \textit{F. Liu} and \textit{B. Osserman} [J. Algebr. Comb. 23, No. 2, 125--136 (2006; Zbl 1090.14009)].
The paper is organized as follows. Section 1 is an introduction to the subject and statement of results. Here, the author introduces also some notation and conventions used in this paper. Sections 2 is devoted to dormant generic Miura \(sl_2\)-Opers and deals with some background material. In Section 3, the author studies a combinatorial description of dormant Miura \(sl_2\)-opers (equivalently, pre-Tango structures) on a totally degenerate curve. In Section 4, the author considers the complete determination of strict \(p\)-branch numberings, which gives a classification of dormant generic Miura \(sl_2\)-opers on totally degenerate curves.
Reviewer: Ahmed Lesfari (El Jadida)\(L\)-functions of Carlitz modules, resultantal varieties and rooted binary trees. IIhttps://zbmath.org/1532.140832024-05-13T19:39:47.825584Z"Grishkov, A."https://zbmath.org/authors/?q=ai:grishkov.alexander-n"Logachev, D."https://zbmath.org/authors/?q=ai:logachev.dmitry"Zobnin, A."https://zbmath.org/authors/?q=ai:zobnin.alexey-iSummary: We continue study of some algebraic varieties (called resultantal varieties) started in a paper of authors ``L-functions of Carlitz modules, resultantal varieties and rooted binary trees, I'', cited as [the authors, J. Number Theory 238, 269--312 (2022; Zbl 1502.14113)]. These varieties are related with the Sylvester matrix for the resultant of two polynomials, from one side, and with the L-functions of twisted Carlitz modules, from another side. They are described in terms of weighted rooted binary trees. We give some proofs that lack in [the authors, J. Number Theory 238, 269--312 (2022; Zbl 1502.14113)], some examples and tables that confirm conjectures from [the authors, J. Number Theory 238, 269--312 (2022; Zbl 1502.14113)], and some ideas of development of this theory.Contractive symmetric matrix completion problems related to graphshttps://zbmath.org/1532.150222024-05-13T19:39:47.825584Z"Chun, Sangmin"https://zbmath.org/authors/?q=ai:chun.sangmin"Kim, In Hyoun"https://zbmath.org/authors/?q=ai:kim.in-hyoun"Kim, Jaewoong"https://zbmath.org/authors/?q=ai:kim.jaewoong"Yoon, Jasang"https://zbmath.org/authors/?q=ai:yoon.jasangSummary: In this paper, we consider the contractive real symmetric matrix completion problems motivated in part by studies on sparse (or dense) matrices for weighted sparse recovery problems and rating matrices with rating density in recommender systems. We completely characterize symmetric patterns \(P\) with the property (C) that every partially contractive real symmetric matrix with pattern \(P\) has a contractive real symmetric completion using graphs.Tracelet Hopf algebras and decomposition spaces (extended abstract)https://zbmath.org/1532.160302024-05-13T19:39:47.825584Z"Behr, Nicolas"https://zbmath.org/authors/?q=ai:behr.nicolas"Kock, Joachim"https://zbmath.org/authors/?q=ai:kock.joachimSummary: Tracelets are the intrinsic carriers of causal information in categorical rewriting systems. In this work, we assemble tracelets into a symmetric monoidal decomposition space, inducing a cocommutative Hopf algebra of tracelets. This Hopf algebra captures important combinatorial and algebraic aspects of rewriting theory, and is motivated by applications of its representation theory to stochastic rewriting systems such as chemical reaction networks.
For the entire collection see [Zbl 1522.68034].On cut vertices and eigenvalues of character graphs of solvable groupshttps://zbmath.org/1532.200112024-05-13T19:39:47.825584Z"Hafezieh, Roghayeh"https://zbmath.org/authors/?q=ai:hafezieh.roghayeh"Hosseinzadeh, Mohammad Ali"https://zbmath.org/authors/?q=ai:hosseinzadeh.mohammad-ali"Hossein-Zadeh, Samaneh"https://zbmath.org/authors/?q=ai:hossein-zadeh.samaneh"Iranmanesh, Ali"https://zbmath.org/authors/?q=ai:iranmanesh.aliSummary: Given a finite group \(G\), the \textit{character graph}, denoted by \(\Delta ( G )\), for its irreducible character degrees is a graph with vertex set \(\rho ( G )\) which is the set of prime numbers that divide the irreducible character degrees of \(G\), and with \(\{ p , q \}\) being an edge if there exists a non-linear \(\chi \in \operatorname{Irr} ( G )\) whose degree is divisible by \(p q\). In this paper, on one hand, we proceed by discussing the graphical shape of \(\Delta ( G )\) when it has cut vertices or small number of eigenvalues, and on the other hand we give some results on the group structure of \(G\) with such \(\Delta ( G )\). Recently, \textit{M. L. Lewis} and \textit{Q. Meng} [Monatsh. Math. 190, No. 3, 541--548 (2019; Zbl 1475.20015)] proved the character graph of each solvable group has at most one cut vertex. Now, we determine the structure of character graphs of solvable groups with a cut vertex and diameter 3. Furthermore, we study solvable groups whose character graphs have at most two distinct eigenvalues. Moreover, we investigate the solvable groups whose character graphs are regular with three distinct eigenvalues. In addition, we give some lower bounds for the number of edges of \(\Delta ( G )\).The Ramsey number \(R_4 (3)\) is not solvable by group partition meanshttps://zbmath.org/1532.200292024-05-13T19:39:47.825584Z"Anabanti, C. S."https://zbmath.org/authors/?q=ai:anabanti.chimere-stanleyLet \(G\) be a finite group. A nonempty subset \(S\) of \(G\) is said to be product-free if \(S \cap SS =\emptyset\); \(S\) is called symmetric if \(S=S^{-1}\).
The Ramsey number \(R_{n}(3)\) is the smallest positive integer such that colouring the edges of a complete graph on \(R_{n}(3)\) vertices in \(n\) colours forces the appearance of a monochromatic triangle. In [\textit{R. E. Greenwood} and \textit{A. M. Gleason}, Can. J. Math. 7, 1--7 (1955; Zbl 0064.17901)] it has been proven that \(R_{3}(3)=17\) and it is known that \(51 \leq R_{4}(3) \leq 62\) (for the lower limit see [\textit{F. R. K. Chung}, Discrete Math. 5, 317--321 (1973; Zbl 0258.05111)], for the upper limit see [\textit{S. E. Fettes}, \textit{R. L. Kramer} and \textit{S. P. Radziszowski}, Ars Comb. 72, 41--63 (2004; Zbl 1075.05057)]).
For a finite group \(G\), it is proved in this paper that if \(G^{\ast}=G\setminus \{ 1 \}\) can be partitioned into disjoint union of \(m\) symmetric product-free sets, then \(R_{m}(3) \geq |G|+1\) (Theorem 1.1).
The Ramsey number \(R_{n}(3)\) is called solvable by group partition means if there is a finite group \(G\) such that \(|G|+1 = R_{n}(3)\) and \(G^{\ast}\) can be partitioned as a union of \(n\) symmetric product-free sets. For \(n \leq 3\), \(R_{n}(3)\) is solvable by group partition means. The main result of the paper under review is that \(R_{4}(3)\) can not be solvable by a group partition approach (Theorem 2.2).
Reviewer: Egle Bettio (Venezia)The commuting conjugacy class graphs of finite groups with a given propertyhttps://zbmath.org/1532.200372024-05-13T19:39:47.825584Z"Rezaei, Mehdi"https://zbmath.org/authors/?q=ai:rezaei.mehdi"Foruzanfar, Zeinab"https://zbmath.org/authors/?q=ai:foruzanfar.zeinabLet \(G\) be a finite non-abelian group. The commuting conjugacy class graph \(\Gamma(G)\) of \(G\), defined in [\textit{M. Herzog} et al., Commun. Algebra 37, No. 10, 3369--3387 (2009; Zbl 1187.20027)], is the simple graph whose vertex set is the set of non-central conjugacy classes of \(G\) and two distinct vertices \(X\) and \(Y\) are connected by an edge if there are two elements \(x \in X\) and \(y\in Y\) such that \(xy=yx\).
In the paper under review, the authors determine the structure of \(\Gamma(G)\) when the central factor \(G/Z(G)\) is isomorphic to a Frobenius group of order \(pq\) or \(p^{2}q\) (\(p\) and \(q\) primes).
Reviewer: Egle Bettio (Venezia)Quivers and path semigroups characterized by locality conditionshttps://zbmath.org/1532.200602024-05-13T19:39:47.825584Z"Zheng, Shanghua"https://zbmath.org/authors/?q=ai:zheng.shanghua"Guo, Li"https://zbmath.org/authors/?q=ai:guo.liSummary: Path algebras from quivers are a fundamental class of algebras with wide applications. Yet it is challenging to describe their universal properties since their underlying path semigroups are only partially defined. A new notion, called locality structures, was recently introduced to deal with partially defined operation, with motivation from locality in convex geometry and quantum field theory. We show that there is a natural correspondence between locality sets and quivers which leads to a concrete class of locality semigroups, called Brandt locality semigroups, which can be obtained by the paths of quivers. Further these path Brandt locality semigroups are precisely the free objects in the category of Brandt locality semigroups with a rigidity condition. This characterization gives a universal property of path algebras and at the same time a combinatorial realization of free rigid Brandt locality semigroups.On graphs and \(M\)-equivalencehttps://zbmath.org/1532.220012024-05-13T19:39:47.825584Z"Pyrch, N. M."https://zbmath.org/authors/?q=ai:pyrch.n-mSee the review of the Russian original in Zbl 1524.22005.
Reviewer: Mihail I. Ursul (Oradea)Hausdorff dimension of a family of networkshttps://zbmath.org/1532.280042024-05-13T19:39:47.825584Z"Zeng, Qingcheng"https://zbmath.org/authors/?q=ai:zeng.qingcheng"Xi, Lifeng"https://zbmath.org/authors/?q=ai:xi.lifeng(no abstract)Classification and stability of positive solutions to the NLS equation on the \(\mathcal{T}\)-metric graphhttps://zbmath.org/1532.340452024-05-13T19:39:47.825584Z"Agostinho, Francisco"https://zbmath.org/authors/?q=ai:agostinho.francisco"Correia, Simão"https://zbmath.org/authors/?q=ai:correia.simao"Tavares, Hugo"https://zbmath.org/authors/?q=ai:tavares.hugoSummary: Given \(\lambda>0\) and \(p>2\), we present a complete classification of the positive \(H^1\)-solutions of the equation \(-u''+\lambda u=|u|^{p-2}u\) on the \(\mathcal{T}\)-metric graph (consisting of two unbounded edges and a terminal edge of length \(\ell>0\), all joined together at a single vertex). This study implies, in particular, the uniqueness of action ground states. Moreover, for \(p\sim 6^-\), the notions of action and energy ground states do not coincide and energy ground states are not unique. In the \(L^2\)-supercritical case \(p>6\), we prove that, for \(\lambda\sim 0^+\) and \(\lambda\sim+\infty\), action ground states are orbitally unstable for the flow generated by the associated time-dependent NLS equation \(i\partial_tu+\partial^2_{xx}u+|u|^{p-2}u=0\). Finally, we provide numerical evidence of the uniqueness of energy ground states for \(p\sim 2^+\) and of the existence of both stable and unstable action ground states for \(p\sim 6\).
{{\copyright} 2024 IOP Publishing Ltd \& London Mathematical Society}Stochastic approximation of lamplighter metricshttps://zbmath.org/1532.460222024-05-13T19:39:47.825584Z"Baudier, Florent"https://zbmath.org/authors/?q=ai:baudier.florent-p"Motakis, Pavlos"https://zbmath.org/authors/?q=ai:motakis.pavlos"Schlumprecht, Thomas"https://zbmath.org/authors/?q=ai:schlumprecht.thomas"Zsák, András"https://zbmath.org/authors/?q=ai:zsak.andrasSummary: We observe that embeddings into random metrics can be fruitfully used to study the \(L_1\)-embeddability of lamplighter graphs or groups, and more generally lamplighter metric spaces. Once this connection has been established, several new upper bound estimates on the \(L_1\)-distortion of lamplighter metrics follow from known related estimates about stochastic embeddings into dominating tree-metrics. For instance, every lamplighter metric on an \(n\)-point metric space embeds bi-Lipschitzly into \(L_1\) with distortion \(O(\log n)\). In particular, for every finite group \(G\) the lamplighter group \(H=\mathbb{Z}_2\wr G\) bi-Lipschitzly embeds into \(L_1\) with distortion \(O(\log \log |H|)\). In the case where the ground space in the lamplighter construction is a graph with some topological restrictions, better distortion estimates can be achieved. Finally, we discuss how a coarse embedding into \(L_1\) of the lamplighter group over the \(d\)-dimensional infinite lattice \(\mathbb{Z}^d\) can be constructed from bi-Lipschitz embeddings of the lamplighter graphs over finite \(d\)-dimensional grids, and we include a remark on Lipschitz free spaces over finite metric spaces.
{{\copyright} 2022 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence.}Rigidity, graphs and Hausdorff dimensionhttps://zbmath.org/1532.520142024-05-13T19:39:47.825584Z"Chatzikonstantinou, Nikolaos"https://zbmath.org/authors/?q=ai:chatzikonstantinou.nikolaos"Iosevich, Alex"https://zbmath.org/authors/?q=ai:iosevich.alex"Mkrtchyan, Sevak"https://zbmath.org/authors/?q=ai:mkrtchyan.sevak"Pakianathan, Jonathan"https://zbmath.org/authors/?q=ai:pakianathan.jonathanThe famous Steinhaus Theorem says that if \(E\subset\mathbb{R}^d\), \(d\geq1\), has positive Lebesgue measure, then the difference \(E-E\) contains some neighborhood of zero [\textit{H. Steinhaus}, Fundam. Math. 1, 93--104 (1920; JFM 47.0179.02)]. In the words of one of the authors of the paper under review [\textit{A. Iosevich}, Notices Am. Math. Soc. 66, No. 4, 552--555 (2019; Zbl 1414.42001)] the Falconer distance conjecture can be viewed as a more delicate variant of the Steinhaus Theorem. \textit{K. J. Falconer} [Mathematika 32, 206--212 (1985; Zbl 0605.28005)] proved that if \(E\) is a compact subset of \(\mathbb{R}^d\) and the Hausdorff dimension of \(E\) is greater than \(d/2+1/2\), then the distance set
\[
D(E)=\{|x-y|\,:\,x,y\in E\}\subset\mathbb{R}
\]
has positive Lebesgue measure. He also gave examples of sets with Hausdorff dimension \(\leq d/2\) with zero Lebesgue measure. The Falconer Distance Conjecture says that if the Hausdorff dimension of \(E\subset\mathbb{R}^d\), \(d\geq2\), is \(>d/2\), then the Lebesgue measure of the distance set \(D(E)\) is positive still stands.
In the paper under review, the authors study a problem inspired by the Falconer distance conjecture. A tuple \(x=(x^1,\ldots,x^{k+1})\), \(x^i\in\mathbb{R}^d\), is called a \((k+1)\)-point configuration in \(\mathbb{R}^d\). Two such configurations \(x\) and \(y\) are equivalent (\(x\sim y\)) if there is an isometry \(T\) on \(\mathbb{R}^d\) such that \(Tx^i=y^i\) for all \(i=1,\ldots,k+1\). Further, let \(E^{k+1}/\sim\) be the equivalence classes of \((k + 1)\)-point configurations of points from the set \(E\). The authors then define in a special way the reduced moduli space of congruence classes. This space can be explicitly identified with a Euclidean space and thus a Lebesgue measure can be defined on this space. The main result of the paper is the following theorem:
Let \(d\geq2\) and \(k\geq1\) be arbitrary integers. The dimension of the reduced moduli space of \((k + 1)\)-point configurations in \(\mathbb{R}^d\) is
\[
m=d(k+1)-\binom{d+1}{2}
\]
and if \(E\subset\mathbb{R}^d\) is any compact set of Hausdorff dimension larger than \(d-\dfrac{1}{k+1}\), then the \(m\)-dimensional Lebesgue measure of the reduced set of congruence classes of \((k + 1)\)-point configurations of points from E is positive.
This result complements the results of \textit{A. Greenleaf} et al. [Rev. Mat. Iberoam. 31, No. 3, 799--810 (2015; Zbl 1329.52015)], where the case when \(k\leq d\) was considered.
For the entire collection see [Zbl 1479.11005].
Reviewer: Mikhail Kabenyuk (Kemerovo)Trilateration using unlabeled path or loop lengthshttps://zbmath.org/1532.520152024-05-13T19:39:47.825584Z"Gkioulekas, Ioannis"https://zbmath.org/authors/?q=ai:gkioulekas.ioannis"Gortler, Steven J."https://zbmath.org/authors/?q=ai:gortler.steven-j"Theran, Louis"https://zbmath.org/authors/?q=ai:theran.louis"Zickler, Todd"https://zbmath.org/authors/?q=ai:zickler.todd-eSummary: Let \(\mathbf{p}\) be a configuration of \(n\) points in \(\mathbb{R}^d\) for some \(n\) and some \(d \geq 2\). Each pair of points defines an edge, which has a Euclidean length in the configuration. A path is an ordered sequence of the points, and a loop is a path that begins and ends at the same point. A path or loop, as a sequence of edges, also has a Euclidean length, which is simply the sum of its Euclidean edge lengths. We are interested in reconstructing \(\mathbf{p}\) given a set of edge, path and loop lengths. In particular, we consider the unlabeled setting where the lengths are given simply as a set of real numbers, and are not labeled with the combinatorial data describing which paths or loops gave rise to these lengths. In this paper, we study the question of when \(\mathbf{p}\) will be uniquely determined (up to an unknowable Euclidean transform) from some given set of path or loop lengths through an exhaustive trilateration process. Such a process has already been used for the simpler problem of reconstruction using unlabeled edge lengths. This paper also provides a complete proof that this process must work in that edge-setting when given a sufficiently rich set of edge measurements and assuming that \(\mathbf{p}\) is generic.Girth, magnitude homology and phase transition of diagonalityhttps://zbmath.org/1532.550072024-05-13T19:39:47.825584Z"Asao, Yasuhiko"https://zbmath.org/authors/?q=ai:asao.yasuhiko"Hiraoka, Yasuaki"https://zbmath.org/authors/?q=ai:hiraoka.yasuaki"Kanazawa, Shu"https://zbmath.org/authors/?q=ai:kanazawa.shuThis paper studies the magnitude homology of graphs. Magnitude is a recently-introduced invariant of metric spaces, whose connection to homology calculations was shown by \textit{N. Otter} [Homology Homotopy Appl. 24, No. 2, 365--387 (2022; Zbl 07626030)]. These insights led to a new strand of research, extending magnitude to a wider variety of spaces. Asao et al. focus on studying to what extent magnitude homology can be used to reveal geometric properties of graphs. The paper particularly focuses on how the \textit{girth} of a graph influences and even partially \textit{determines} magnitude homology. The main contribution of this paper is thus a characterization of the magnitude homology groups of a graph, given in relation to its girth. In addition, the paper studies the \textit{diagonality} of a graph, referring to a specific phenomenon in magnitude homology: Being a bi-graded homology theory, the magnitude homology of a graph is indexed by two distinct grades \(k, l\); \textit{diagonality} now refers to the phenomenon of a graph having a concentration of non-trivial magnitude homology groups along the diagonal, i.e. its magnitude homology is trivial for \(k \neq l\). A preliminary characterization of this phenomenon was provided by \textit{R. Hepworth} and \textit{S. Willerton} [ibid. 19, No. 2, 31--60 (2017; Zbl 1377.05088)]; the current paper extends these results by showing how diagonality arises as a function of the edge density in random graphs, the main result being that Erdős-Rényi graphs exhibit a phase transition of diagonality as function of their edge insertion probability \(p\).
Reviewer: Bastian Rieck (München)Limiting spectral distribution of stochastic block modelhttps://zbmath.org/1532.600112024-05-13T19:39:47.825584Z"Su, Giap Van"https://zbmath.org/authors/?q=ai:su.giap-van"Chen, May-Ru"https://zbmath.org/authors/?q=ai:chen.mayru"Guo, Mei-Hui"https://zbmath.org/authors/?q=ai:guo.meihui"Huang, Hao-Wei"https://zbmath.org/authors/?q=ai:huang.haoweiSummary: The stochastic block model (SBM) is an extension of the Erdős-Rényi graph and has applications in numerous fields, such as data analysis, recovering community structure in graph data and social networks. In this paper, we consider the normal central SBM adjacency matrix with \(K\) communities of arbitrary sizes. We derive an explicit formula for the limiting empirical spectral density function when the size of the matrix tends to infinity. We also obtain an upper bound for the operator norm of such random matrices by means of the Stieltjes transform and random matrix theory.A modification of the random cutting modelhttps://zbmath.org/1532.600132024-05-13T19:39:47.825584Z"Burghart, Fabian"https://zbmath.org/authors/?q=ai:burghart.fabianSummary: We propose a modification to the random destruction of graphs: given a finite network with a distinguished set of sources and targets, remove (cut) vertices at random, discarding components that do not contain a source node. We investigate the number of cuts required until all targets are removed, and the size of the remaining graph. This model interpolates between the random cutting model going back to \textit{A. Meir} and \textit{J. W. Moon} [J. Aust. Math. Soc. 11, 313--324 (1970; Zbl 0196.27602)] and site percolation. We prove several general results, including that the size of the remaining graph is a tight family of random variables for compatible sequences of expander-type graphs, and determine limiting distributions for binary caterpillar trees and complete binary trees.On the second eigenvalue of random bipartite biregular graphshttps://zbmath.org/1532.600162024-05-13T19:39:47.825584Z"Zhu, Yizhe"https://zbmath.org/authors/?q=ai:zhu.yizheSummary: We consider the spectral gap of a uniformly chosen random \((d_1,d_2)\)-biregular bipartite graph \(G\) with \(|V_1|=n\), \(|V_2|=m\), where \(d_1,d_2\) could possibly grow with \(n\) and \(m\). Let \(A\) be the adjacency matrix of \(G\). Under the assumption that \(d_1\ge d_2\) and \(d_2=O(n^{2/3})\), we show that \(\lambda_2(A)=O(\sqrt{d_1})\) with high probability. As a corollary, combining the results from [\textit{K. Tikhomirov} and \textit{P. Youssef}, Ann. Probab. 47, No. 1, 362--419 (2019; Zbl 1407.05212)], we show that the second singular value of a uniform random \(d\)-regular digraph is \(O(\sqrt{d})\) for \(1\le d\le n/2\) with high probability. Assuming \(d_2\) is fixed and \(d_1=O(n^2)\), we further prove that for a random \((d_1,d_2)\)-biregular bipartite graph, \(|\lambda_i^2(A)-d_1|=O(\sqrt{d_1})\) for all \(2\le i\le n+m-1\) with high probability. The proofs of the two results are based on the size biased coupling method introduced in [\textit{N. Cook} et al., Ann. Probab. 46, No. 1, 72--125 (2018; Zbl 1386.05105)]) for random \(d\)-regular graphs and several new switching operations we define for random bipartite biregular graphs.Large deviations for mean field model in Erdős-Rényi graphhttps://zbmath.org/1532.600522024-05-13T19:39:47.825584Z"Gao, Yunshi"https://zbmath.org/authors/?q=ai:gao.yunshiSummary: In this paper, we study a particle systems (or interacting diffusions) on an Erdős-Rényi graph with the parameter \(p_N \in (0, 1]\) that behaves like a mean-field system up to large deviations. Our aim is to establish the large deviations for the empirical measure process of particle systems under the condition \(N p_N^4 \to \infty\) as \(N \to \infty\), where \(N\) is the number of particles. The result is obtained by proving the exponential equivalence between our systems and general interacting systems without random graphs. The multilinear extensions of Grothendieck inequality play a crucial role in our proof.Limiting shape for first-passage percolation models on random geometric graphshttps://zbmath.org/1532.602092024-05-13T19:39:47.825584Z"Coletti, Cristian F."https://zbmath.org/authors/?q=ai:coletti.cristian-f"de Lima, Lucas R."https://zbmath.org/authors/?q=ai:de-lima.lucas-r"Hinsen, Alexander"https://zbmath.org/authors/?q=ai:hinsen.alexander"Jahnel, Benedikt"https://zbmath.org/authors/?q=ai:jahnel.benedikt"Valesin, Daniel"https://zbmath.org/authors/?q=ai:valesin.danielSummary: Let a random geometric graph be defined in the supercritical regime for the existence of a unique infinite connected component in Euclidean space. Consider the first-passage percolation model with independent and identically distributed random variables on the random infinite connected component. We provide sufficient conditions for the existence of the asymptotic shape, and we show that the shape is a Euclidean ball. We give some examples exhibiting the result for Bernoulli percolation and the Richardson model. In the latter case we further show that it converges weakly to a nonstandard branching process in the joint limit of large intensities and slow passage times.The winner takes it all but onehttps://zbmath.org/1532.602112024-05-13T19:39:47.825584Z"Deijfen, Maria"https://zbmath.org/authors/?q=ai:deijfen.maria"Van Der Hofstad, Remco"https://zbmath.org/authors/?q=ai:van-der-hofstad.remco-w"Sfragara, Matteo"https://zbmath.org/authors/?q=ai:sfragara.matteoSummary: We study competing first passage percolation on graphs generated by the configuration model with infinite-mean degrees. Initially, two uniformly chosen vertices are infected with a type 1 and type 2 infection, respectively, and the infection then spreads via nearest neighbors in the graph. The time it takes for the type 1 (resp. 2) infection to traverse an edge \(e\) is given by a random variable \(X_1(e)\) (resp. \(X_2(e)\)) and, if the vertex at the other end of the edge is still uninfected, it then becomes type 1 (resp. 2) infected and immune to the other type. Assuming that the degrees follow a power-law distribution with exponent \(\tau \in (1,2)\), we show that with high probability as the number of vertices tends to infinity, one of the infection types occupies all vertices except for the starting point of the other type. Moreover, both infections have a positive probability of winning regardless of the passage-time distribution. The result is also shown to hold for the erased configuration model, where self-loops are erased and multiple edges are merged, and when the degrees are conditioned to be smaller than \(n^\alpha\) for some \(\alpha> 0\).High-dimensional near-critical percolation and the torus plateauhttps://zbmath.org/1532.602162024-05-13T19:39:47.825584Z"Hutchcroft, Tom"https://zbmath.org/authors/?q=ai:hutchcroft.tom"Michta, Emmanuel"https://zbmath.org/authors/?q=ai:michta.emmanuel"Slade, Gordon"https://zbmath.org/authors/?q=ai:slade.gordonSummary: We consider percolation on \({\mathbb{Z}^d}\) and on the \(d\)-dimensional discrete torus, in dimensions \(d\ge 11\) for the nearest-neighbour model and in dimensions \(d > 6\) for spread-out models. For \({\mathbb{Z}^d}\) we employ a wide range of techniques and previous results to prove that there exist positive constants \(c\) and \(C\) such that the slightly subcritical two-point function and one-arm probabilities satisfy
\[
\begin{aligned}
\mathbb{P}_{p_{c} -\varepsilon} (0\leftrightarrow x) &\le \frac{C}{\| x{\|^{d-2}}}{e^{-c{\varepsilon^{1/2}}\| x\|}},\\
\frac{c}{{r^2}}{e^{-C{\varepsilon^{1/2}}r}} &\le {\mathbb{P}_{{p_c}-\varepsilon}}(0\leftrightarrow \partial{[-r,r]^d})\le \frac{C}{{r^2}}{e^{-c{\varepsilon^{1/2}}r}}.
\end{aligned}
\]
Using this, we prove that throughout the critical window the torus two-point function has a ``plateau,'' meaning that it decays for small \(x\) as \(\| x{\|^{-(d-2)}}\) but for large \(x\) is essentially constant and of order \({V^{-2/3}}\) where \(V\) is the volume of the torus. The plateau for the two-point function leads immediately to a proof of the torus triangle condition, which is known to have many implications for the critical behaviour on the torus, and also leads to a proof that the critical values on the torus and on \({\mathbb{Z}^d}\) are separated by a multiple of \({V^{-1/3}}\). The torus triangle condition and the size of the separation of critical points have been proved previously, but our proofs are different and are direct consequences of the bound on the \({\mathbb{Z}^d}\) two-point function. In particular, we use results derived from the lace expansion on \({\mathbb{Z}^d}\), but in contrast to previous work on high-dimensional torus percolation, we do not need or use a separate torus lace expansion.Recurrence of horizontal-vertical walkshttps://zbmath.org/1532.602252024-05-13T19:39:47.825584Z"Chan, Swee Hong"https://zbmath.org/authors/?q=ai:chan.swee-hongSummary: Consider a nearest neighbor random walk on the two-dimensional integer lattice, where each vertex is initially labeled either `H' or `V', uniformly and independently. At each discrete time step, the walker resamples the label at its current location (changing `H' to `V' and `V' to `H' with probability \(q)\). Then, it takes a mean zero horizontal step if the new label is `H', and a mean zero vertical step if the new label is `V'. This model is a randomized version of the deterministic rotor walk, for which its recurrence (i.e., visiting every vertex infinitely often with probability 1) in two dimensions is still an open problem. We answer the analogous question for the horizontal-vertical walk, by showing that the horizontal-vertical walk is recurrent for \(q\in (\frac{1}{3},1]\).Numerical study for a class of time fractional diffusion equations using operational matrices based on Hosoya polynomialhttps://zbmath.org/1532.650972024-05-13T19:39:47.825584Z"Zhou, Ping"https://zbmath.org/authors/?q=ai:zhou.ping|zhou.ping.1"Jafari, Hossein"https://zbmath.org/authors/?q=ai:jafari.hossein"Ganji, Roghayeh M."https://zbmath.org/authors/?q=ai:ganji.roghayeh-moallem"Narsale, Sonali M."https://zbmath.org/authors/?q=ai:narsale.sonali-mandarSummary: In this paper, we develop a numerical method by using operational matrices based on Hosoya polynomials of simple paths to find the approximate solution of diffusion equations of fractional order with respect to time. This method is applied to certain diffusion equations like time fractional advection-diffusion equations and time fractional Kolmogorov equations. Here we use the Atangana-Baleanu fractional derivative. With the help of this approach we convert these equations to a set of algebraic equations, which is easier to be solved. Also, the error bound is provided. The obtained numerical solutions using the presented method are compared with the exact solutions. The numerical results show that the suggested method is convenient and accurate.Network capacity bound for personalized PageRank in multimodal networkshttps://zbmath.org/1532.680092024-05-13T19:39:47.825584Z"Kłopotek, Mieczysław A."https://zbmath.org/authors/?q=ai:klopotek.mieczyslaw-alojzy"Wierzchoń, Sławomir T."https://zbmath.org/authors/?q=ai:wierzchon.slawomir-tadeusz"Kłopotek, Robert A."https://zbmath.org/authors/?q=ai:klopotek.robert-albertSummary: In a former paper [the authors et al., in: Challenges in computational statistics and Data mining. Cham: Springer. 189--204 (2015; \url{doi:10.1007/978-3-319-18781-5_11})] the concept of Bipartite PageRank was introduced and a theorem on the limit of authority flowing between nodes for personalized PageRank has been generalized. In this paper we want to extend those results to multimodal networks. In particular we deal with a hypergraph type that may be used for describing multimodal network where a hyperlink connects nodes from each of the modalities. We introduce a generalisation of PageRank for such graphs and define the respective random walk model that can be used for computations. We state and prove theorems on the limit of outflow of authority for cases where individual modalities have identical and distinct damping factors.Disjoint paths and connected subgraphs for \(H\)-free graphshttps://zbmath.org/1532.680232024-05-13T19:39:47.825584Z"Kern, Walter"https://zbmath.org/authors/?q=ai:kern.walter"Martin, Barnaby"https://zbmath.org/authors/?q=ai:martin.barnaby-d"Paulusma, Daniël"https://zbmath.org/authors/?q=ai:paulusma.daniel"Smith, Siani"https://zbmath.org/authors/?q=ai:smith.siani"van Leeuwen, Erik Jan"https://zbmath.org/authors/?q=ai:van-leeuwen.erik-janSummary: The well-known \textsc{Disjoint Paths} problem is to decide if a graph contains \(k\) pairwise disjoint paths, each connecting a different terminal pair from a set of \(k\) distinct vertex pairs. We determine, with an exception of two cases, the complexity of the \textsc{Disjoint Paths} problem for \(H\)-free graphs. If \(k\) is fixed, we obtain the \(k\)\textsc{-Disjoint Paths} problem, which is known to be polynomial-time solvable on the class of all graphs for every \(k\geq 1\). The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of \(k\)\textsc{-Disjoint Connected Subgraphs} for \(H\)-free graphs, and give the same almost-complete classification for \textsc{Disjoint Connected Subgraphs} for \(H\)-free graphs as for \textsc{Disjoint Paths}. Moreover, we give exact algorithms for \textsc{Disjoint Paths} and \textsc{Disjoint Connected Subgraphs} on graphs with \(n\) vertices and \(m\) edges that have running times of \(O(2^nn^2k)\) and \(O(3^nkm)\), respectively.On the maximum cardinality cut problem in proper interval graphs and related graph classeshttps://zbmath.org/1532.680242024-05-13T19:39:47.825584Z"Boyacı, Arman"https://zbmath.org/authors/?q=ai:boyaci.arman"Ekim, Tınaz"https://zbmath.org/authors/?q=ai:ekim.tinaz"Shalom, Mordechai"https://zbmath.org/authors/?q=ai:shalom.mordechaiSummary: Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is \(\mathsf{FPT}\) when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter.
Specifically, we define an \((\alpha, \beta, \delta)\)-clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most \(\delta\) labels, a) every label consists of at most \(\beta\) sets of twin vertices, and b) all the labels together induce a graph with independence number at most \(\alpha\). We show that for every two constants \(\alpha,\delta > 0\) the problem is \(\mathsf{FPT}\) when parameterized by \(\beta\) plus the smallest width of an \((\alpha,\beta,\delta)\)-clique-width decomposition.The use of a pruned modular decomposition for maximum matching algorithms on some graph classeshttps://zbmath.org/1532.680642024-05-13T19:39:47.825584Z"Ducoffe, Guillaume"https://zbmath.org/authors/?q=ai:ducoffe.guillaume"Popa, Alexandru"https://zbmath.org/authors/?q=ai:popa.alexandruSummary: We address the following general question: given a graph class \(\mathcal{C}\) on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into \(\mathcal{C}\)? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a ``pruned modular decomposition'', that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in [\textit{D. Coudert} et al., SODA 2018, 2765--2784 (2018; Zbl 1403.68157)]. Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.
For the entire collection see [Zbl 1407.68036].Efficiently list-edge coloring multigraphs asymptotically optimallyhttps://zbmath.org/1532.680652024-05-13T19:39:47.825584Z"Iliopoulos, Fotis"https://zbmath.org/authors/?q=ai:iliopoulos.fotis"Sinclair, Alistair"https://zbmath.org/authors/?q=ai:sinclair.alistairSummary: We give polynomial time algorithms for the seminal results of Kahn, who showed that the Goldberg-Seymour and list-coloring conjectures for (list-)edge coloring multigraphs hold asymptotically. Kahn's arguments are based on the probabilistic method and are non-constructive. Our key insight is that we can combine sophisticated techniques due to Achlioptas, Iliopoulos, and Kolmogorov for the analysis of local search algorithms with correlation decay properties of the probability spaces on matchings used by Kahn in order to construct efficient edge-coloring algorithms.
{{\copyright} 2022 Wiley Periodicals LLC}On the complexity of stable fractional hypergraph matchinghttps://zbmath.org/1532.680662024-05-13T19:39:47.825584Z"Ishizuka, Takashi"https://zbmath.org/authors/?q=ai:ishizuka.takashi"Kamiyama, Naoyuki"https://zbmath.org/authors/?q=ai:kamiyama.naoyukiSummary: In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system. \textit{R. Aharoni} and \textit{T. Fleiner} [J. Comb. Theory, Ser. B 87, No. 1, 72--80 (2003; Zbl 1058.05031)] proved that there exists a stable fractional matching in every hypergraphic preference system. Furthermore, \textit{S. Kintali} et al. [SIAM J. Comput. 42, No. 6, 2063--2113 (2013; Zbl 1285.68048)] proved that the problem of finding a stable fractional matching in a hypergraphic preference system is PPAD-complete. In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is bounded by some constant. The proof by Kintali et al. [loc. cit.] implies the PPAD-completeness of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is 5. In this paper, we prove that (i) this problem is PPAD-complete even if the maximum degree is 3, and (ii) if the maximum degree is 2, then this problem can be solved in polynomial time. Furthermore, we prove that the problem of finding an approximate stable fractional matching in a hypergraphic preference system is PPAD-complete.
For the entire collection see [Zbl 1407.68036].On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphshttps://zbmath.org/1532.680672024-05-13T19:39:47.825584Z"Jena, Sangram K."https://zbmath.org/authors/?q=ai:jena.sangram-k"Jallu, Ramesh K."https://zbmath.org/authors/?q=ai:jallu.ramesh-k"Das, Gautam K."https://zbmath.org/authors/?q=ai:das.gautam-kumarSummary: In this article, we study the \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination problem. Given a simple undirected graph \(G=(V,E)\), and positive integers \(d,m,\ell\) and \(r\), a subset \(V'\subseteq V\) is said to be a \(d\)-distance \(m\)-tuple \((\ell, r)\)-dominating set if it satisfies the following conditions: (i) each vertex \(v \in V\) is \(d\)-distance dominated by at least \(m\) vertices in \(V'\), and (ii) each \(r\) size subset \(U\) of \(V\) is \(d\)-distance dominated by at least \(\ell\) vertices in \(V'\). Here, a vertex \(v\) is \(d\)-distance dominated by another vertex \(u\) means the shortest path distance between \(u\) and \(v\) is at most \(d\) in \(G\). A set \(U\) is \(d\)-distance dominated by a set of \(\ell\) vertices means size of the union of the \(d\)-distance neighborhood of all vertices of \(U\) in \(V'\) is at least \(\ell\). The objective of the \(d\)-distance \(m\)-tuple \((\ell, r)\)-domination problem is to find a minimum size subset \(V'\subseteq V\) satisfying the above two conditions.
We prove that the problem of deciding whether a graph \(G\) has (i) a 1-distance \(m\)-tuple \((\ell, r)\)-dominating set for each fixed value of \(m,\ell\), and \(r\), and (ii) a \(d\)-distance \(m\)-tuple \((\ell, 2)\)-dominating set for each fixed value of \(d(\geq 2), m\), and \(\ell\) of cardinality at most \(k\) (here \(k\) is a positive integer) are NP-complete. We also prove that for any \(\varepsilon > 0\), the 1-distance \(m\)-tuple \((\ell, r)\)-domination problem and the \(d\)-distance \(m\)-tuple \((\ell, 2)\)-domination problem cannot be approximated within a factor of \((\frac{1}{2}-\varepsilon)\ln |V|\) and \((\frac{1}{4}- \varepsilon)\ln |V|\), respectively, unless \(\mathrm{P}=\mathrm{NP}\).Colouring \((P_r+P_s)\)-free graphshttps://zbmath.org/1532.680682024-05-13T19:39:47.825584Z"Klimošová, Tereza"https://zbmath.org/authors/?q=ai:klimosova.tereza"Malík, Josef"https://zbmath.org/authors/?q=ai:malik.josef"Masařík, Tomáš"https://zbmath.org/authors/?q=ai:masarik.tomas"Novotná, Jana"https://zbmath.org/authors/?q=ai:novotna.jana"Paulusma, Daniël"https://zbmath.org/authors/?q=ai:paulusma.daniel"Slívová, Veronika"https://zbmath.org/authors/?q=ai:slivova.veronikaSummary: The \(k\)-Colouring problem is to decide if the vertices of a graph can be coloured with at most \(k\) colours for a fixed integer \(k\) such that no two adjacent vertices are coloured alike. If each vertex \(u\) must be assigned a colour from a prescribed list \(L(u)\subseteq\{1,\dots,k\}\), then we obtain the List \(k\)-Colouring problem. A graph \(G\) is \(H\)-free if \(G\) does not contain \(H\) as an induced subgraph. We continue an extensive study into the complexity of these two problems for \(H\)-free graphs. We prove that List 3-Colouring is polynomial-time solvable for \((P_2+P_5)\)-free graphs and for \((P_3+P_4)\)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on \(H\)-free graphs for all graphs \(H\) up to seven vertices. We also prove that 5-Colouring is NP-complete for \((P_3+P_5)\)-free graphs.
For the entire collection see [Zbl 1407.68036].A relaxation of the directed disjoint paths problem: a global congestion metric helpshttps://zbmath.org/1532.680692024-05-13T19:39:47.825584Z"Lopes, Raul"https://zbmath.org/authors/?q=ai:lopes.raul-h-c"Sau, Ignasi"https://zbmath.org/authors/?q=ai:sau.ignasiSummary: In the \textsc{Directed Disjoint Paths} problem, we are given a digraph \(D\) and a set of requests \(\{(s_1,t_1),\ldots,(s_k,t_k)\}\), and the task is to find a collection of pairwise vertex-disjoint paths \(\{P_1,\ldots,P_k\}\) such that each \(P_i\) is a path from \(s_i\) to \(t_i\) in \(D\). This problem is \textsf{NP}-complete for fixed \(k = 2\) and \textsf{W}[1]-hard with parameter \(k\) in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Positive results are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be ``disjoint enough'', in the sense that they must behave properly not in the whole graph, but in an unspecified part of size prescribed by a parameter. Namely, in the \textsc{Disjoint Enough Directed Paths} problem, given an \(n\)-vertex digraph \(D\), a set of \(k\) requests, and non-negative integers \(d\) and \(s\), the task is to find a collection of paths connecting the requests such that at least \(d\) vertices of \(D\) occur in at most \(s\) paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of \(D\). Among other results, we show that the problem is \textsf{W}[1]-hard in DAGs with parameter \(d\) and, on the positive side, we give an algorithm in time \(\mathcal{O}(n^{d+2}\cdot k^{d\cdot s})\) and a kernel of size \(d\cdot 2^{k-s}\cdot\begin{pmatrix} k \\ s \end{pmatrix}+2k\) in general digraphs. This latter result has consequences for the \textsc{Steiner Network} problem: we show that it is \textsf{FPT} parameterized by the number \(k\) of terminals and \(p\), where \(p=n-q\) and \(q\) is the size of the solution.Computing vertex-disjoint paths in large graphs using MAOshttps://zbmath.org/1532.680702024-05-13T19:39:47.825584Z"Preißer, Johanna E."https://zbmath.org/authors/?q=ai:preisser.johanna-e"Schmidt, Jens M."https://zbmath.org/authors/?q=ai:schmidt.jens-mSummary: We consider the problem of computing \(k\in\mathbb{N}\) internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, \(O(\min\{k,\sqrt{n}\}m)\) for each pair by using traditional flow-based methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). \textit{M. Rauch Henzinger} [J. Algorithms 24, No. 1, 194--220 (1997; Zbl 0879.68045)] showed for every MAO and every \(1\le k\le\delta\) (where \(\delta\) is the minimum degree of the graph) the existence of \(k\) internally vertex-disjoint paths between every pair of the last \(\delta-k+2\) vertices of this MAO. Later, \textit{H. Nagamochi} [Discrete Appl. Math. 154, No. 16, 2411--2417 (2006; Zbl 1129.05025)] generalized this result by using the machinery of mixed connectivity. Both results are however inherently non-constructive. We present the first algorithm that computes these \(k\) internally vertex-disjoint paths in linear time \(O(m)\), which improves the previously best time \(O(\min\{k,\sqrt{n}\}m)\). Due to the linear running time, this algorithm is suitable for large graphs. The algorithm is simple, works directly on the MAO structure, and completes a long history of purely existential proofs with a constructive method. We extend our algorithm to compute several other path systems and discuss its impact for certifying algorithms.
For the entire collection see [Zbl 1407.68036].A faster parameterized algorithm for temporal matchinghttps://zbmath.org/1532.680722024-05-13T19:39:47.825584Z"Zschoche, Philipp"https://zbmath.org/authors/?q=ai:zschoche.philippSummary: A temporal graph is a sequence of graphs (called layers) over the same vertex set -- describing a graph topology which is subject to discrete changes over time. A \(\Delta\)-temporal matching \(M\) is a set of time edges \((e, t)\) (an edge \(e\) paired up with a point in time \(t)\) such that for all distinct time edges \((e, t),(e',t')\in M\) we have that \(e\) and \(e'\) do not share an endpoint, or the time-labels \(t\) and \(t'\) are at least \(\Delta\) time units apart.
\textit{G. B. Mertzios} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 154, Article 27, 14 p. (2020; Zbl 07650912)] provided a \(2^{O(\Delta\nu)}\cdot|\mathcal{G}|^{O(1)}\)-time algorithm to compute the maximum size of a \(\Delta\)-temporal matching in a temporal graph \(\mathcal{G}\), where \(|\mathcal{G}|\) denotes the size of \(\mathcal{G}\), and \(\nu\) is the \(\Delta\)-vertex cover number of \(\mathcal{G}\). The \(\Delta\)-vertex cover number is the minimum number \(\nu\) such that the classical vertex cover number of the union of any \(\Delta\) consecutive layers of the temporal graph is upper-bounded by \(\nu\). We show an improved algorithm to compute a \(\Delta\)-temporal matching of maximum size with a running time of \(\Delta^{O(\nu)}\cdot |\mathcal{G}|\) and hence provide an exponential speedup in terms of \(\Delta\).Learning centrality by learning to routehttps://zbmath.org/1532.680912024-05-13T19:39:47.825584Z"Bachar, Liav"https://zbmath.org/authors/?q=ai:bachar.liav"Elyashar, Aviad"https://zbmath.org/authors/?q=ai:elyashar.aviad"Puzis, Rami"https://zbmath.org/authors/?q=ai:puzis.ramiSummary: Developing a tailor-made centrality measure for a given task requires domain and network analysis expertise, as well as time and effort. Automatically learning arbitrary centrality measures provided ground truth node scores is an important research direction. In this article, we propose a generic deep learning architecture for centrality learning that relies on the insight that arbitrary centrality measures can be computed using Routing Betweenness Centrality (RBC) and our new differentiable implementation of RBC. The proposed Learned Routing Centrality (LRC) architecture optimizes the routing function of RBC to fit the ground truth scores. Results show that LRC can learn multiple types of centrality indices more accurately than state-of-the-art.
For the entire collection see [Zbl 1492.94005].Clique-width of point configurationshttps://zbmath.org/1532.681162024-05-13T19:39:47.825584Z"Çağırıcı, Onur"https://zbmath.org/authors/?q=ai:cagirici.onur"Hliněný, Petr"https://zbmath.org/authors/?q=ai:hlineny.petr"Pokrývka, Filip"https://zbmath.org/authors/?q=ai:pokryvka.filip"Sankaran, Abhisekh"https://zbmath.org/authors/?q=ai:sankaran.abhisekhSummary: While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of \textit{clique-width} to geometric point configurations represented by their \textit{order type}. We study basic properties of this clique-width notion, and show that it is aligned with the general concept of clique-width of relational structures by Blumensath and Courcelle (2006). We also relate the new notion to monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given.Toward finiteness of central configurations for the planar six-body problem by symbolic computations. I: Determine diagrams and ordershttps://zbmath.org/1532.700012024-05-13T19:39:47.825584Z"Chang, Ke-Ming"https://zbmath.org/authors/?q=ai:chang.ke-ming"Chen, Kuo-Chang"https://zbmath.org/authors/?q=ai:chen.kuo-chang|chen.kuochangSummary: In a series of papers we develop symbolic computation algorithms to investigate finiteness of central configurations for the planar \(n\)-body problem. Our approach is based on \textit{A. Albouy} and \textit{V. Kaloshin}'s work on finiteness of central configurations for the 5-body problems [Ann. Math. (2) 176, No. 1, 535--588 (2012; Zbl 1362.70014)]. In their paper, bicolored graphs called \textit{zw}-diagrams were introduced for possible scenarios when the finiteness conjecture fails, and proving finiteness amounts to exclusions of central configurations associated to these diagrams. Following their method, the amount of computations becomes enormous when there are more than five bodies. In this paper we introduce matrix algebra for determination of possible diagrams and asymptotic orders, devise several criteria to reduce computational complexity, and determine possible \textit{zw}-diagrams by automated deductions. For the planar six-body problem, we show that there are at most 86 \textit{zw}-diagrams.From Hurwitz numbers to Feynman diagrams: counting rooted trees in log gravityhttps://zbmath.org/1532.810352024-05-13T19:39:47.825584Z"Mvondo-She, Yannick"https://zbmath.org/authors/?q=ai:mvondo-she.yannickSummary: We show that the partition function of the logarithmic sector of critical topologically massive gravity which represents a series expansion of composition of functions, can be expressed as a sum over rooted trees. Our work brings a connection between integrable hierarchies of mathematical physics, combinatorial Hopf algebras and rooted trees, by explaining how the \(\tau\)-functions of the (potential) Burgers and KP integrable hierarchies appearing in the partition function of log gravity conceal the Hopf algebra of composition of functions, known as the Faà di Bruno algebra, of the same type as the celebrated Connes-Kreimer Hopf algebra of rooted trees and Feynman diagrams. In particular, the Hurwitz numbers appearing in the partition function arise as coefficients of isomorphism classes of rooted trees. A parallel is drawn between our findings and established results in the statistical physics literature concerning certain systems with quenched disorder on trees, associated to nonlinear partial differential equations admitting traveling wave solutions. This should be of particular interest in view of a further description of the disorder observed in log gravity.System-size dependence of the charged-particle pseudorapidity density at \(\sqrt{ s_{\operatorname{NN}}} = 5.02 \text{TeV}\) for pp, Ppb, and pbpb collisionshttps://zbmath.org/1532.810642024-05-13T19:39:47.825584ZSummary: We present the first systematic comparison of the charged-particle pseudorapidity densities for three widely different collision systems, pp, pPb, and PbPb, at the top energy of the Large Hadron Collider \(( \sqrt{ s_{\operatorname{NN}}} = 5.02 \text{TeV} )\) measured over a wide pseudorapidity range \((- 3.5 < \eta < 5)\), the widest possible among the four experiments at that facility. The systematic uncertainties are minimised since the measurements are recorded by the same experimental apparatus (ALICE). The distributions for pPb and PbPb collisions are determined as a function of the centrality of the collisions, while results from pp collisions are reported for inelastic events with at least one charged particle at midrapidity. The charged-particle pseudorapidity densities are, under simple and robust assumptions, transformed to charged-particle rapidity densities. This allows for the calculation and the presentation of the evolution of the width of the rapidity distributions and of a lower bound on the Bjorken energy density, as a function of the number of participants in all three collision systems. We find a decreasing width of the particle production, and roughly a smooth ten fold increase in the energy density, as the system size grows, which is consistent with a gradually higher dense phase of matter.Transformation of transverse momentum distributions from parton branching to Collins-Soper-Sterman frameworkhttps://zbmath.org/1532.810832024-05-13T19:39:47.825584Z"Martinez, Armando Bermudez"https://zbmath.org/authors/?q=ai:martinez.armando-bermudezSummary: Two main frameworks for defining transverse momentum dependent (TMD) parton densities are the Collins-Soper-Sterman (CSS) formalism, and the Parton Branching (PB) approach. While PB-TMDs have an explicit dependence on a single scale which is used to evolve PB-TMDs in momentum space, TMDs defined in CSS formalism present a double-scale evolution in renormalization and rapidity scales, via a pair of coupled evolution equations. In this letter I leverage the Collins-Soper kernel determined from simulated Drell Yan transverse momentum spectra using PB-TMDs, and provide, for the first time, the transformation of TMD parton distributions from the PB framework to the CSS formalism. The evolved PB-TMDs in \(b\)-space are compared to the recently released, unpolarized TMD distribution ART23.Computing optimal shortcuts for networkshttps://zbmath.org/1532.900222024-05-13T19:39:47.825584Z"Garijo, Delia"https://zbmath.org/authors/?q=ai:garijo.delia"Márquez, Alberto"https://zbmath.org/authors/?q=ai:marquez.alberto"Rodríguez, Natalia"https://zbmath.org/authors/?q=ai:rodriguez.natalia.1"Silveira, Rodrigo I."https://zbmath.org/authors/?q=ai:silveira.rodrigo-iSummary: We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Questions of this type have received considerable attention recently, mostly for discrete variants of the problem. We study a fully continuous setting, where all points on the network and the inserted segment must be taken into account. We present the first results on the computation of optimal shortcuts for general networks in this model, together with several results for networks that are paths, restricted to two types of shortcuts: shortcuts with a fixed orientation and simple shortcuts.
For the entire collection see [Zbl 1407.68036].The power function hidden in the vulnerability of fractal complex networkshttps://zbmath.org/1532.900232024-05-13T19:39:47.825584Z"Li, Dong-Yan"https://zbmath.org/authors/?q=ai:li.dongyan"Huang, Peng-He"https://zbmath.org/authors/?q=ai:huang.penghe"Wang, Xing-Yuan"https://zbmath.org/authors/?q=ai:wang.xingyuan"Liu, Hao-Dong"https://zbmath.org/authors/?q=ai:liu.haodongSummary: As a special kind of complex network, fractal complex networks have their unique characteristics such as fractal dimension, scale invariance, percolation threshold, \textit{etc}. There have been some researches on the topology of fractal network, among which the calculation of fractal dimension, the construction of fractal model, the phase transition and the robustness of fractal network were the hotspots. But unlike the studies of the scale-free and small-world networks, there was little research on the relationship between the stability and the fractal feature, especially between the vulnerability and fractal dimension of the fractal networks. In this paper, the relationship between vulnerability and fractal dimension was discussed based on two kinds of fractal growth models and different vulnerability measurement methods. The same power functional relationships were obtained and a universal expression was proposed. Then, the effect of fractal feature on the vulnerability was exploring through the fitting error when fractal dimensions were calculated. Finally, the vulnerability of the real networks and their similarities to the fractal models in term of vulnerability showed the rationality of the fractal network models in establishing stable models. The results of this study have important reference for creating structurally stable artificial neural networks, transportation networks and information networks.Nabla fractional distributed optimization algorithms over undirected/directed graphshttps://zbmath.org/1532.900742024-05-13T19:39:47.825584Z"Hong, Xiaolin"https://zbmath.org/authors/?q=ai:hong.xiaolin"Wei, Yiheng"https://zbmath.org/authors/?q=ai:wei.yiheng"Zhou, Shuaiyu"https://zbmath.org/authors/?q=ai:zhou.shuaiyu"Yue, Dongdong"https://zbmath.org/authors/?q=ai:yue.dongdongSummary: The primary focus of this paper centers on investigating unconstrained distributed optimization problems over undirected or directed graphs. One noteworthy departure from current distributed optimization algorithms in the continuous-time domain is the integration of nabla fractional calculus, which augments algorithmic performance by reducing iterative complexity. Through rigorous analysis, this paper demonstrates that the two algorithms presented converge at the Mittag-Leffler rate to the precise solution of a distributed optimization problem over a connected undirected graph or a connected balanced directed graph with strongly convex and smooth objective functions. The research findings provide valuable insights into the potential utility of nabla fractional calculus in distributed optimization problems, highlighting the possibility of enhancing the efficiency and effectiveness of distributed optimization algorithms.On a class of PCA with size-3 neighborhood and their applications in percolation gameshttps://zbmath.org/1532.910212024-05-13T19:39:47.825584Z"Bhasin, Dhruv"https://zbmath.org/authors/?q=ai:bhasin.dhruv"Karmakar, Sayar"https://zbmath.org/authors/?q=ai:karmakar.sayar"Podder, Moumanti"https://zbmath.org/authors/?q=ai:podder.moumanti"Roy, Souvik"https://zbmath.org/authors/?q=ai:roy.souvik.1Summary: Different versions of percolation games on \(\mathbb{Z}^2\), with parameters \(p\) and \(q\) that indicate, respectively, the probability with which a site in \(\mathbb{Z}^2\) is labeled a trap and the probability with which it is labeled a target, are shown to have probability 0 of culminating in draws when \(p + q > 0\). We show that, for fixed \(p\) and \(q\), the probability of draw in each of these games is 0 if and only if a certain 1-dimensional probabilistic cellular automaton (PCA) \(F_{p, q}\) with a size-3 neighborhood is ergodic. This allows us to conclude that \(F_{p, q}\) is ergodic whenever \(p + q > 0\), thereby rigorously establishing ergodicity for a considerable class of PCAs that tie in closely with important topics such as the enumeration of directed animals, broadcasting of information on directed infinite lattices, examining reliability of computations against the presence of noise etc. The key to our proof is the technique of weight functions. We include extensive discussions on game theoretic PCAs to which this technique may be applicable to establish ergodicity, and on percolation games to which this technique may be applicable to explore the `regimes' (depending on the underlying parameter(s), such as \((p, q)\) in our case) in which the probabilities of draw are 0.Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game formshttps://zbmath.org/1532.910222024-05-13T19:39:47.825584Z"Gurvich, Vladimir"https://zbmath.org/authors/?q=ai:gurvich.vladimir-a"Naumova, Mariya"https://zbmath.org/authors/?q=ai:naumova.mariyaSummary: We prove a new property of dual hypergraphs and derive from it Nash-solvability of the corresponding (tight) game forms. This result is known since 1975, but its new proof is much simpler.An effective heuristic clustering algorithm for mining multiple critical nodes in complex networkshttps://zbmath.org/1532.910822024-05-13T19:39:47.825584Z"Wang, Ying"https://zbmath.org/authors/?q=ai:wang.ying.44"Zheng, Yunan"https://zbmath.org/authors/?q=ai:zheng.yunan"Shi, Xuelei"https://zbmath.org/authors/?q=ai:shi.xuelei"Liu, Yiguang"https://zbmath.org/authors/?q=ai:liu.yiguangSummary: Influence maximization is of great significance in complex networks, and many methods have been proposed to solve it. However, they are usually time-consuming or cannot deal with the overlap of spreading. To get over the flaws, an effective heuristic clustering algorithm is proposed in this paper: (1) nodes that have been assigned to clusters are excluded from the network structure to guarantee they do not participate in subsequent clustering. (2) the K-shell (\(k_s\)) and Neighborhood Coreness (\textit{NC}) value of nodes in the remaining network are recalculated, which ensures the node influence can be adjusted during the clustering process. (3) a hub node and a routing node are selected for each cluster to jointly determine the initial spreader, which balances the local and global influence. Due to the above contributions, the proposed method preferably guarantees the influence of initial spreaders and the dispersity between them. A series of experiments based on Susceptible-Infected-Recovered (SIR) stochastic model confirm that the proposed method has favorable performance under different initial constraints against known methods, including VoteRank, HC, GCC, HGD, and DLS-AHC.Simplex closing probabilities in directed graphshttps://zbmath.org/1532.920082024-05-13T19:39:47.825584Z"Unger, Florian"https://zbmath.org/authors/?q=ai:unger.florian"Krebs, Jonathan"https://zbmath.org/authors/?q=ai:krebs.jonathan"Müller, Michael G."https://zbmath.org/authors/?q=ai:muller.michael-gSummary: Recent work in mathematical neuroscience has calculated the directed graph homology of the directed simplicial complex given by the brain's sparse adjacency graph, the so called connectome. These biological connectomes show an abundance of both high-dimensional directed simplices and Betti-numbers in all viable dimensions -- in contrast to Erdős-Rényi-graphs of comparable size and density. An analysis of synthetically trained connectomes reveals similar findings, raising questions about the graphs comparability and the nature of origin of the simplices.
We present a new method capable of delivering insight into the emergence of simplices and thus simplicial abundance. Our approach allows to easily distinguish simplex-rich connectomes of different origin. The method relies on the novel concept of an almost-d-simplex, that is, a simplex missing exactly one edge, and consequently the almost-d-simplex closing probability by dimension. We also describe a fast algorithm to identify almost-d-simplices in a given graph. Applying this method to biological and artificial data allows us to identify a mechanism responsible for simplex emergence, and suggests this mechanism is responsible for the simplex signature of the excitatory subnetwork of a statistical reconstruction of the mouse primary visual cortex. Our highly optimized code for this new method is publicly available.Quantifying robustness of the gap gene networkhttps://zbmath.org/1532.920632024-05-13T19:39:47.825584Z"Andreas, Elizabeth"https://zbmath.org/authors/?q=ai:andreas.elizabeth"Cummins, Breschine"https://zbmath.org/authors/?q=ai:cummins.breschine"Gedeon, Tomáš"https://zbmath.org/authors/?q=ai:gedeon.tomasSummary: Early development of \textit{Drosophila melanogaster} (fruit fly) facilitated by the gap gene network has been shown to be incredibly robust, and the same patterns emerge even when the process is seriously disrupted. We investigate this robustness using a previously developed computational framework called DSGRN (dynamic signatures generated by regulatory networks). Our mathematical innovations include the conceptual extension of this established modeling technique to enable modeling of spatially monotone environmental effects, as well as the development of a collection of graph theoretic robustness scores for network models. This allows us to rank order the robustness of network models of cellular systems where each cell contains the same genetic network topology but operates under a parameter regime that changes continuously from cell to cell. We demonstrate the power of this method by comparing the robustness of two previously introduced network models of gap gene expression along the anterior-posterior axis of the fruit fly embryo, both to each other and to a random sample of networks with same number of nodes and edges. We observe that there is a substantial difference in robustness scores between the two models. Our biological insight is that random network topologies are in general capable of reproducing complex patterns of expression, but that using measures of robustness to rank order networks permits a large reduction in hypothesis space for highly conserved systems such as developmental networks.Efficient approaches for attaining epidemic-free networks with minimum edge removal sethttps://zbmath.org/1532.921022024-05-13T19:39:47.825584Z"Liu, Yang"https://zbmath.org/authors/?q=ai:liu.yang.256"Liang, Guangbo"https://zbmath.org/authors/?q=ai:liang.guangbo"Wang, Xi"https://zbmath.org/authors/?q=ai:wang.xi.1|wang.xi|wang.xi.2"Wang, Zhuoyu"https://zbmath.org/authors/?q=ai:wang.zhuoyu"Zhu, Peican"https://zbmath.org/authors/?q=ai:zhu.peican"Wang, Zhen"https://zbmath.org/authors/?q=ai:wang.zhen.13|wang.zhen.21|wang.zhen.3|wang.zhen.1|wang.zhen.10|wang.zhen.8|wang.zhen.14|wang.zhen.9|wang.zhen.2|wang.zhen.5|wang.zhen.7|wang.zhen|wang.zhen.12This paper studies efficient approaches for attaining epidemic-free networks with minimum edge removal set. It presents three edge removal strategies to cope with the epidemic containment problem. It obtain the removal edge set through simultaneously optimizing the epidemic threshold and the largest connected component of the remaining network. It shows superiority in the containment of epidemics of different spread efficiencies. A bound strategy is also introduced to scale up the proposed methods to make them effective to deal with large-scale networks. Some experiments are presented to evaluate the effectiveness of the methods on synthetic and empirical networks.
Reviewer: Yilun Shang (Newcastle upon Tyne)Contagion source detection in epidemic and infodemic outbreaks: mathematical analysis and network algorithmshttps://zbmath.org/1532.921112024-05-13T19:39:47.825584Z"Tan, Chee Wei"https://zbmath.org/authors/?q=ai:tan.chee-wei"Yu, Pei-Duo"https://zbmath.org/authors/?q=ai:yu.pei-duoSummary: The rapid spread of infectious diseases and online rumors share similarities in terms of their speed, scale, and patterns of contagion. Although these two phenomena have historically been studied separately, the COVID-19 pandemic has highlighted the devastating consequences that simultaneous crises of epidemics and misinformation can have on the world. Soon after the outbreak of COVID-19, the World Health Organization launched a campaign against the COVID-19 Infodemic, which refers to the dissemination of pandemic-related false information online that causes widespread panic and hinders recovery efforts. Undoubtedly, nothing spreads faster than fear.
Networks serve as a crucial platform for viral spreading, as the actions of highly influential users can quickly render others susceptible to the same. The potential for contagion in epidemics and rumors hinges on the initial source, underscoring the need for rapid and efficient digital contact tracing algorithms to identify superspreaders or Patient Zero. Similarly, detecting and removing rumor mongers is essential for preventing the proliferation of harmful information in online social networks. Identifying the source of large-scale contagions requires solving complex optimization problems on expansive graphs. Accurate source identification and understanding the dynamic spreading process requires a comprehensive understanding of surveillance in massive networks, including topological structures and spreading veracity. Ultimately, the efficacy of algorithms for digital contact tracing and rumor source detection relies on this understanding.
This monograph provides an overview of the mathematical theories and computational algorithm design for contagion source detection in large networks. By leveraging network centrality as a tool for statistical inference, we can accurately identify the source of contagions, trace their spread, and predict future trajectories. This approach provides fundamental insights into surveillance capability and asymptotic behavior of contagion spreading in networks. Mathematical theory and computational algorithms are vital to understanding contagion dynamics, improving surveillance capabilities, and developing effective strategies to prevent the spread of infectious diseases and misinformation.Degree distance in graphs with forbidden subgraphshttps://zbmath.org/1532.921252024-05-13T19:39:47.825584Z"Mafuta, Phillip"https://zbmath.org/authors/?q=ai:mafuta.phillipIn this paper, the author studied the degree distance of some graphs without pendant vertices and of given degree and diameter. For such graphs, two main results are presented in Theorems 2 and 3. In these results, the author obtained upper bounds for the degree distance of such graphs which do not have \(C_3\)'s and \(C_4\)'s. These results improve an upper bound given by \textit{S. Mukwembi} and \textit{S. Munyira} [Bull. Aust. Math. Soc. 87, No. 2, 255--271 (2013; Zbl 1262.05040)].
Reviewer: Ismail Naci Cangül (Bursa)Maximizing Graovac-Ghorbani index of trees with fixed maximum degreehttps://zbmath.org/1532.921262024-05-13T19:39:47.825584Z"Majstorović, Snježana"https://zbmath.org/authors/?q=ai:majstorovic.snjezanaThe paper explores topological descriptors, numerical measures utilized for delineating characteristics of molecular graphs. These graphs depict the carbon-atom framework found in organic hydrocarbon molecules. Topological descriptors offer a method for quantitatively depicting the structure and attributes of these molecules.
The Graovac-Ghorbani (\(ABC_{GG}\)) index was introduced in [\textit{A. Graovac} and \textit{M. Ghorbani}, ``A new version of atom-bond connectivity index'', Acta Chim. Slov. 57, 609--612 (2010)] as a derivative of the atom-bond connectivity (ABC) index, which is one of the well-described descriptors.
For a graph \(G=(V,E)\), \(ABC_{GG}\) index is given by the formula:
\[ABC_{GG}(G)= \sum_{uv \in E(G)} \sqrt{\frac{n_u + n_v - 2}{n_u n_v}},\]
where \(n_u\) is the number of vertices which are closer to vertex \(u\) than to vertex \(v\) and \(n_v\) is the number of vertices which are closer to \(v\) than to \(u\).
Let \(\Delta\) denote the maximum degree of a graph \(G\). For \(\Delta \ge 2\) , let \(T^1_{\Delta+1,\Delta}\) denote a star with \(\Delta +1 \) vertices rooted at the vertex of degree \(\Delta\). For \(\ell \ge 2\), let \(T^\ell_{n,\Delta}\) be a rooted tree with \(n\) vertices obtained by attaching \(\Delta-1\) pendant vertices to each pendant vertex of \(m\)-vertex tree \(T^{\ell-1}_{m,\Delta}\). The tree \(T^\ell_{n,\Delta}\) is called a dendrimer. An almost dendrimer is a tree obtained from a dendrimer by removing certain pendant vertices.
It is shown that almost dendrimers are trees which maximize \(ABC_{GG}\) index among all trees on \(n\) vertices with maximum degree at most \(\Delta\). This results confirms the conjecture proposed in [\textit{D. Dimitrov} et al., Appl. Math. Comput. 293, 370--376 (2017; Zbl 1411.05146)].
Reviewer: Aleksander Vesel (Maribor)Distance-targeted competitive follower-attraction containment control for multi-agent systems with weighted directed graphshttps://zbmath.org/1532.930142024-05-13T19:39:47.825584Z"Ao, Yichao"https://zbmath.org/authors/?q=ai:ao.yichao"Jia, Yingmin"https://zbmath.org/authors/?q=ai:jia.yingminSummary: This paper studies competitive containment control problems of the leader-follower multi-agent systems with weighted directed graphs. Two leaders compete to minimize the ultimate distances from the followers, by directly connecting with some of the followers and allocating weights on these connections. This competition is characterized by a nonzero-sum game due to the existence of singular strategies. With the help of matrix series and Geršgorin discs, we provide the gradients and the convexity of the payoff functions on the differentiable strategy sets. By constructing auxiliary strategy sets which elaborately exclude the singular strategies and deeply analyzing the Karush-Kuhn-Tucker conditions, existence and uniqueness of the Nash equilibrium are rigorously examined, and a sufficient and necessary algebraic condition for this Nash equilibrium is further obtained. For a special case where all followers can be connected with meanwhile a degree condition for the interaction graph is satisfied, we find each leader tends to build connections with all followers and destroy the distribution fashion of multi-agent systems. All above analysis indicates that some typical phenomena in game theory models such as pigs' payoff and prisoner's dilemma similarly exist in the multi-agent containment control systems. Lastly, two Nash equilibrium seeking algorithms are proposed for leaders to select their rational strategies.
{{\copyright} 2023 John Wiley \& Sons Ltd.}Resilient time-varying output formation tracking of heterogeneous linear multiagent systems under malicious false data injection attacks and denial-of-service attacks over digraphshttps://zbmath.org/1532.930482024-05-13T19:39:47.825584Z"Feng, Zhi"https://zbmath.org/authors/?q=ai:feng.zhi"Hu, Guoqiang"https://zbmath.org/authors/?q=ai:hu.guoqiangSummary: A distributed control fashion of cooperative formation tracking may be vulnerable to malicious attacks on sensors and communications that deteriorate the formation tracking performance or even destabilize the entire multiagent system. This article addresses a resilient time-varying output formation tracking problem of linear heterogeneous multiagent systems, where an attacker can adversely inject false data injection (FDI) attacks on sensors and denial-of-service (DoS) attacks on communications. Both characteristics will not only enhance the practical relevance of the studied issue, but also bring nontrivial design challenges of distributed control algorithms and convergence analysis. A novel resilient distributed control architecture is developed to guarantee a global exponential time-varying output formation tracking. In particular, the design includes features: (1) a resilient distributed leader estimator is developed to estimate the leader's state for each follower under DoS attacks over digraphs; (2) a distributed output feedback controller integrated with an observer-based resilient mechanism is developed to achieve the time-varying output formation tracking under attacks; (3) unlike existing related works to handle attacks as bounded disturbances or faults, the proposed design is resilient to enable exponential convergence, whereas many related works obtain uniformly ultimately boundedness (UUB) convergence. Simulation results are presented to validate the design's effectiveness.
{{\copyright} 2023 John Wiley \& Sons Ltd.}Fully distributed event-driven cooperation with unknown parameters under directed graphshttps://zbmath.org/1532.931782024-05-13T19:39:47.825584Z"Liu, Shu"https://zbmath.org/authors/?q=ai:liu.shu.1|liu.shu"Sun, Jiayue"https://zbmath.org/authors/?q=ai:sun.jiayue"Zhang, Huaguang"https://zbmath.org/authors/?q=ai:zhang.huaguangSummary: In this article, a novel fully distributed dynamic event-driven strategy is designed for linear multi-agent systems (MASs) containing unknown parameters under general directed graphs. Each agent can achieve consensus asymptotically by communicating with its neighbors and does not need to use global information, so the proposed dynamic event-driven algorithm can work in a fully distributed manner. Existing fully distributed event-based consensus works rely on two or more event monitoring conditions. Too much event monitoring logic will put an extra computational burden on the MASs; instead, for the first time, this article proposes a fully distributed event-driven strategy with a single event monitoring condition under directed graphs. In addition, the proposed strategy (adaptive control law and event monitoring condition) does not involve the dynamics parameters of MASs and provides better applicability. Finally, we rule out Zeno behavior by showing that any adjacent event interval for each agent is greater than zero. The simulations verify our results.
{{\copyright} 2022 John Wiley \& Sons Ltd.}Adaptive event-triggered bipartite consensus control for multi-agent systems under signed digraphshttps://zbmath.org/1532.931842024-05-13T19:39:47.825584Z"Mu, Rui"https://zbmath.org/authors/?q=ai:mu.rui"Wei, Airong"https://zbmath.org/authors/?q=ai:wei.airong"Li, Haitao"https://zbmath.org/authors/?q=ai:li.haitao"Zhang, Xianfu"https://zbmath.org/authors/?q=ai:zhang.xianfu"Duan, Zhiyu"https://zbmath.org/authors/?q=ai:duan.zhiyuSummary: In this paper, the bipartite consensus problem is addressed via adaptive event-triggered control for multi-agent systems in directed communication networks, where cooperative and competitive interactions are considered simultaneously. Under a strongly connected digraph, a novel fully distributed control protocol is first put forward, which consists of an adaptive controller and two event-triggered mechanisms. The protocol is flexible and capable of achieving bipartite consensus without employing global information. Meanwhile, the Zeno behavior cannot occur by embedding \(L_p\) functions in the event-triggered mechanisms. Furthermore, a general digraph with a spanning tree is investigated, and it is shown that the proposed protocol is still effective in bipartite consensus including the leader-follower one as a special case. It is worth noting that there is no need for the protocol to continuously update the controller, nor to maintain the uninterrupted communication with neighbors. Finally, the validity of the presented results is confirmed by simulations.
{{\copyright} 2022 John Wiley \& Sons Ltd.}Polynomial-time optimal liveness enforcement for guidepath-based transport systemshttps://zbmath.org/1532.932442024-05-13T19:39:47.825584Z"Reveliotis, Spyros"https://zbmath.org/authors/?q=ai:reveliotis.spyros-a"Masopust, Tomáš"https://zbmath.org/authors/?q=ai:masopust.tomas"Ibrahim, Michael"https://zbmath.org/authors/?q=ai:ibrahim.michael-nawarSummary: Zone-controlled guidepath-based transport systems is a modeling abstraction representing the traffic dynamics of a set of agents circulating in a constricted medium. An important problem for the traffic coordinator of these systems is to preserve liveness, that is, the ability of each agent to successfully complete its current trip and to be engaged in similar trips in the future. We present a polynomial-time algorithm for enforcing liveness in a class of these systems, in a maximally permissive manner. Our result is surprising and applicable in the traffic control of various unit-load material handling systems and other robotic applications.Performance-prescribed consensus for uncertain nonlinear multi-agent systems under directed graphhttps://zbmath.org/1532.933442024-05-13T19:39:47.825584Z"Yu, Linzhen"https://zbmath.org/authors/?q=ai:yu.linzhen"Liu, Yungang"https://zbmath.org/authors/?q=ai:liu.yungangSummary: Whether or not system performance can be prescribed by users is one core issue for almost all control problems, of course for multi-agent control systems. But it could pose stern constraints on or exceptions to systems and control methods. How can one guarantee the prescribed performance while covering much more systems? It deserves deep study and particularly entails the integration/reformation of the related techniques. In the paper, we are concerned with the leaderless consensus with a prescribed convergence rate, aiming at \(n\)-dimensional multi-agent systems typically with unknown heterogeneous nonlinearities under a directed graph. In view of the essence of the problem, we resort to a powerful time-varying high-gain method, that is, funnel control. Specifically, to suppress unknown system nonlinearities and guarantee the prescribed performance, funnel gains are devised by utilizing the relative states and a time-varying design function. Integrating them as well as a series of intermediate variables, a distributed consensus protocol is obtained without involving any global graph information. Remark that besides being used to construct funnel gains, the time-varying design function is also introduced as a part of the protocol, substantially enhancing the control effect and playing a key role in forcing the relative states to ultimately converge to zero. It is shown that under the proposed protocol, the desired consensus is achieved with a prescribed convergence rate. A simulation example is given to illustrate the effectiveness of the theoretical result.
{{\copyright} 2022 John Wiley \& Sons Ltd.}Linear convergence of distributed estimation with constraints and communication delayshttps://zbmath.org/1532.933592024-05-13T19:39:47.825584Z"Zhou, Yaoyao"https://zbmath.org/authors/?q=ai:zhou.yaoyao"Chen, Gang"https://zbmath.org/authors/?q=ai:chen.gang.7Summary: Motivated by the multi-sensor estimation problem, we consider a distributed constraint parameter estimation problem on a directed graph. Our goal is to design a fast distributed algorithm to handle constraint parameter estimation problems, especially considering the communication delays when sensors interact on a directed graph. Based on the gradient-tracking algorithm and indirect projection method, the projected distributed parameter estimation algorithm (PDPEA) is proposed, which can deal with the closed convex set constraint and use the historical information stored by the sensors to achieve fast and accurate mean gradient estimation. The analysis shows that the PDPEA converges to a global and consensual minimizer even under the influence of measurement noise, arbitrarily bounded communication delays, and directed information topologies. Under the assumption that the local cost function is strongly convex and smooth, we show that the algorithm converges at a linear rate for an appropriate choice of stepsize. Lastly, we demonstrate the effectiveness of the proposed algorithm by setting up a multi-sensor parameter estimation network.