Recent zbMATH articles in MSC 05Chttps://zbmath.org/atom/cc/05C2022-09-13T20:28:31.338867ZUnknown authorWerkzeugBook review of: L. Lovász, Graphs and geometryhttps://zbmath.org/1491.000162022-09-13T20:28:31.338867Z"Meunier, Frédéric"https://zbmath.org/authors/?q=ai:meunier.fredericReview of [Zbl 1425.05001].A unified approach to structural limits and limits of graphs with bounded tree-depthhttps://zbmath.org/1491.030042022-09-13T20:28:31.338867Z"Nešetřil, Jaroslav"https://zbmath.org/authors/?q=ai:nesetril.jaroslav"Ossona de Mendez, Patrice"https://zbmath.org/authors/?q=ai:ossona-de-mendez.patriceThis monograph sets up a framework for studying limits of infinite sequences of finite relational structures, such as graphs, by associating, when possible, a ``limit object'', called modeling, to such a sequence. This framework generalizes the frameworks considered by graph theorists when studying the notions of graphon and graphing. To say something about the main results we need to know something about three central concepts of this framework.
A sequence of finite structures \((A_n)_{n \in \mathbb{N}}\) (having the same finite relational signature) is FO-convergent if for every first-order formula \(\varphi(x_1, \ldots, x_k)\), the proportion of \(k\)-tuples in \(A_n\) which satisfy \(\varphi\) converges as \(n\) tends to infinity.
A modeling is a relational structure with the additional features that its domain is a Borel space equipped with a probability measure and every first-order definable relation is measurable in the corresponding product \(\sigma\)-algebra.
A modeling \(M\) is called a modeling FO-limit of an FO-convergent sequence of finite structures \((A_n)_{n \in \mathbb{N}}\) if for every first-order formula the proportion of tuples in \(A_n\) which satisfy it converges to the probability (according to \(M\)) of the relation defined by that formula in \(M\).
The main definitions and results are collected in the first section of the monograph. The first of these states that if \(\mathcal{C}\) is a monotone class of finite graphs such that every \(FO\)-convergent sequence of graphs from \(\mathcal{C}\) has a modeling FO-limit, then \(\mathcal{C}\) is nowhere dense. It follows that there are FO-convergent sequences of graphs without a modeling FO-limit. It is conjectured that the converse implication also holds and Section 5.2 in the appendix reports on recent progress towards verifying the conjecture.
The remaining main results are concerned with (colored) graphs: (a) Every FO-convergent sequence of finite graphs with a fixed maximum degree has a modeling FO-limit, and (b) every FO-convergent sequence of finite colored trees with a fixed maximum height has a modeling FO-limit. The statement (b) is generalized (see Theorem 4.3.6), via the use of interpretations, to say roughly that (c) every FO-convergent sequence of finite colored graphs with fixed maximum tree height has a modeling FO-limit. Conjecture 1.3 proposes conditions under which a modeling should be a modeling FO-limit of an FO-convergent sequence of finite graphs of with fixed maximum degree. In the case of the statements (b) and (c), this monograph proves converses of the implications. More precisely: If \(M\) is a modeling such that its underlying first-order structure is a rooted colored tree with finite height and if \(M\) satisfies the Finitary Mass Transport Principle (FMTP) (Definition 4.20), then \(M\) is a modeling FO-limit of a sequence of finite rooted colored trees. Via the use of interpretations this result, which is technically hard to prove, can be generalized (in Theorem 4.3.6) to roughly the following: If \(M\) is a modeling that can be interpreted in a modeling \(T\) with the FMTP such that the underlying first-order structure of \(T\) is a rooted colored tree, then \(M\) is the modeling FO-limit of a sequence of finite graphs with a fixed bound on the tree height.
Section 2 develops general methods (for possible future use) involving (Lindenbaum-Tarski) Boolean algebras, Stone spaces, Ehrenfeucht-Fraisse games, the Gaifmain locality theorem and the notion of an interpretation of one structure in another. Section 3 studies modelings and their relationship to the concepts of Vapnik-Chervonenkis dimension, nowhere denseness, and random freeness. Section 4 studies sequences and limits of (colored) graphs with bounded tree-height, in particular rooted colored trees with bounded height, and the results mentioned above about such structures are proved here. The final Section 5 discusses open problems related to the theory developed in the monograph.
Reviewer: Vera Koponen (Uppsala)A note on computable distinguishing coloringshttps://zbmath.org/1491.030262022-09-13T20:28:31.338867Z"Bazhenov, N."https://zbmath.org/authors/?q=ai:bazhenov.n-a"Greenberg, N."https://zbmath.org/authors/?q=ai:greenberg.noam"Melnikov, A."https://zbmath.org/authors/?q=ai:melnikov.alexander-g"Miller, R."https://zbmath.org/authors/?q=ai:miller.russell-g|miller.russel-g"Ng, K. M."https://zbmath.org/authors/?q=ai:ng.kengmengSummary: An \(\alpha \)-coloring \(\xi\) of a structure \(\mathcal{S}\) is \textit{distinguishing} if there are no nontrivial automorphisms of \(\mathcal{S}\) respecting \(\xi \). In this note we prove several results illustrating that computing the distinguishing number of a structure can be very hard in general. In contrast, we show that every computable Boolean algebra has a \(0^{\prime\prime}\)-computable distinguishing 2-coloring. We also define the notion of a computabile distinguishing 2-coloring of a separable space; we apply the new definition to separable Banach spaces.A first course in graph theory and combinatoricshttps://zbmath.org/1491.050012022-09-13T20:28:31.338867Z"Cioabă, Sebastian"https://zbmath.org/authors/?q=ai:cioaba.sebastian-m"Murty, M. Ram"https://zbmath.org/authors/?q=ai:murty.maruti-ramPublisher's description: This book discusses the origin of graph theory from its humble beginnings in recreational mathematics to its modern setting or modeling communication networks, as is evidenced by the World Wide Web graph used by many Internet search engines. The second edition of the book includes recent developments in the theory of signed adjacency matrices involving the proof of sensitivity conjecture and the theory of Ramanujan graphs. In addition, the book discusses topics such as Pick's theorem on areas of lattice polygons and Graham-Pollak's work on addressing of graphs. The concept of graph is fundamental in mathematics and engineering, as it conveniently encodes diverse relations and facilitates combinatorial analysis of many theoretical and practical problems. The text is ideal for a one-semester course at the advanced undergraduate level or beginning graduate level.
See the review of the first edition in [Zbl 1216.05001].Number theory and combinatorics. A collection in honor of the mathematics of Ronald Grahamhttps://zbmath.org/1491.050022022-09-13T20:28:31.338867ZPublisher's description: This volume is dedicated to the work and memory of Professor Ronald L. Graham known as the architect of discrete mathematics and combinatorics and will consist of up to 20 contributions from top mathematicians reflecting on his work in combinatorics and number theory.
\begin{itemize}
\item Original contributions by leading experts in combinatorics and number theory
\item Includes essays and memories of Professor Graham from those that knew him
\item Of interest to researchers and graduate students working in combinatorics and number theory.
\end{itemize}
The articles of this volume will be reviewed individually.
Indexed articles:
\textit{Adeniran, Ayomikun; Snider, Lauren; Yan, Catherine}, Multivariate difference Gončarov polynomials, 1-20 [Zbl 07571262]
\textit{Butler, Steve (ed.); Hurlbert, Glenn (ed.)}, Foreword, V-VI [Zbl 07571285]
\textit{Allouche, J.-P.}, On an inequality in a 1970 paper of R. L. Graham, 21-26 [Zbl 07571263]
\textit{Alon, Noga; Alweiss, Ryan; Liu, Yang P.; Martinsson, Anders; Narayanan, Shyam}, Arithmetic progressions in sumsets of sparse sets, 27-33 [Zbl 07571264]
\textit{Bennett, Michael A.; Martin, Greg; O'bryant, Kevin}, Multidimensional Padé approximation of binomial functions: equalities, 35-64 [Zbl 07571265]
\textit{Blomberg, Lars; Shannon, S. R.; Sloane, N. J. A.}, Graphical enumeration and stained glass windows. I: Rectangular grids, 65-97 [Zbl 07571266]
\textit{Brown, Tom C.; Mohsenipour, Shahram}, Two extensions of Hilbert's cube lemma, 99-107 [Zbl 07571267]
\textit{Budden, Mark}, The Gallai-Ramsey number for a tree versus complete graphs, 109-113 [Zbl 07571268]
\textit{Buhler, Joe; Freiling, Chris; Graham, Ron; Kariv, Jonathan; Roche, James R.; Tiefenbruck, Mark; van Alten, Clint; Yeroshkin, Dmytro}, On Levine's notorious hat puzzle, 115-165 [Zbl 07571269]
\textit{Cooper, Joshua; Fickes, Grant}, Recurrence ranks and moment sequences, 167-186 [Zbl 07571270]
\textit{Dudek, Andrzej; Grytczuk, Jarosław; Ruciński, Andrzej}, On weak twins and up-and-down subpermutations, 187-202 [Zbl 07571271]
\textit{Farhangi, Sohail; Grytczuk, Jarosław}, Distance graphs and arithmetic progressions, 203-208 [Zbl 07571272]
\textit{Filaseta, Michael; Juillerat, Jacob}, Consecutive primes which are widely digitally delicate, 209-247 [Zbl 07571273]
\textit{Griggs, Jerrold R.}, Spanning trees and domination in hypercubes, 249-258 [Zbl 07571274]
\textit{Harborth, Heiko; Nienborg, Hauke}, Rook domination on hexagonal hexagon boards, 259-265 [Zbl 07571275]
\textit{Hindman, Neil; Strauss, Dona}, Strongly image partition regular matrices, 267-284 [Zbl 07571276]
\textit{Hopkins, Brian}, Introducing shift-constrained Rado numbers, 285-296 [Zbl 07571277]
\textit{Lichtman, Jared Duker}, Mertens' prime product formula, dissected, 297-310 [Zbl 07571278]
\textit{Nathanson, Melvyn B.}, Curious convergent series of integers with missing digits, 311-327 [Zbl 07571279]
\textit{Pomerance, Carl}, A note on Carmichael numbers in residue classes, 321-327 [Zbl 07571280]
\textit{Shkredov, I. D.; Solymosi, J.}, Tilted corners in integer grids, 329-338 [Zbl 07571281]
\textit{Alon, Noga (ed.); Brown, Tom C (ed.); Butler, Steve (ed.); Griggs, Jerrold R. (ed.); Hindman, Neil (ed.); Jungic, Veselin (ed.); Landman, Bruce M. (ed.); Nešetřil, Jaroslav (ed.)}, Remembrances [of Ron Graham], 339-360 [Zbl 07571282]
\textit{Butler, Steve}, A selected bibliography of Ron Graham, 355-360 [Zbl 07571283]Enumerating graph embeddings and partial-duals by genus and Euler genushttps://zbmath.org/1491.050062022-09-13T20:28:31.338867Z"Gross, Jonathan L."https://zbmath.org/authors/?q=ai:gross.jonathan-l"Tucker, Thomas W."https://zbmath.org/authors/?q=ai:tucker.thomas-wSummary: We present an overview of an enumerative approach to topological graph theory, involving the
derivation of generating functions for a set of graph embeddings, according to the topological types of their
respective surfaces. We are mainly concerned with methods for calculating two kinds of polynomials:
\begin{itemize}
\item[1.] the genus polynomial \(\Gamma_G(z)\) for a given graph \(G\), which is taken over all orientable embeddings of \(G\), and
the Euler-genus polynomial \(\mathcal{E}_G(z)\), which is taken over all embeddings;
\item[2.] the partial-duality polynomials \(\partial\mathcal{E}^*_G(z)\), \(\partial\mathcal{E}^\times_G(z)\), and \(\partial\mathcal{E}^{*\times *}_G(z)\), which are taken over the partial-duals for
all subsets of edges, for Poincare duality (\(*\)), Petrie duality (\(\times\)), and Wilson duality (\(*\times *\)), respectively.
\end{itemize}
We describe the methods used for the computation of recursions and closed formulas for genus polynomials
and partial-dual polynomials. We also describe methods used to examine the polynomials pertaining to some
special families of graphs or graph embeddings, for the possible properties of interpolation and log-concavity.Lattice paths and \((n - 2)\)-stack sortable permutationshttps://zbmath.org/1491.050072022-09-13T20:28:31.338867Z"Gu, Cindy C. Y."https://zbmath.org/authors/?q=ai:gu.cindy-c-y"Wang, Larry X. W."https://zbmath.org/authors/?q=ai:wang.larry-x-wSummary: We establish a bijection between the \((n - 2)\)-stack sortable permutations and the labeled lattice paths. Using this bijection, we directly give combinatorial proof for the log-concavity of the numbers of \((n - 2)\)-stack sortable permutations with \(k\) descents. Furthermore, we prove the numbers of \((n - 2)\)-stack sortable permutations with \(k\) descents satisfy interlacing log-concavity. We also consider a conjecture proposed by \textit{M. Bóna} [ibid. 98, No. 1, 201--209 (2002; Zbl 1009.05003)] that the sequences of the descents of \(t\)-stack sortable permutations of \([n]\) are Hilbert functions for any \(t\) and \(n\). We prove this conjecture for \(t = n - 2\).Bijections between compositions over finite groupshttps://zbmath.org/1491.050162022-09-13T20:28:31.338867Z"Gao, Zhicheng"https://zbmath.org/authors/?q=ai:gao.zhicheng"Zhang, Tiancheng"https://zbmath.org/authors/?q=ai:zhang.tianchengSummary: One may generalize integer compositions by replacing positive integers with elements from an additive group, giving the broader concept of compositions over a group. In this note we give some simple bijections between compositions over a finite group. It follows from these bijections that the number of compositions of a nonzero group element \(g\) is independent of \(g\). As a result we derive a simple expression for the number of compositions of any given group element. This extends an earlier result for abelian groups which was obtained using generating functions and a multivariate multisection formula.Combinatorialization of Sury and McLaughlin identities and general linear recurrences by a unified approachhttps://zbmath.org/1491.050292022-09-13T20:28:31.338867Z"Bera, Sudip"https://zbmath.org/authors/?q=ai:bera.sudipSummary: In this article, we provide combinatorial proofs of some prior identities due to Sury and McLaughlin. We show that the solution of a general linear recurrence with constant coefficients can be interpreted as a determinant of a matrix. Moreover, we derive determinantal expressions for the Fibonacci and Lucas numbers. We prove Binet's formula for Fibonacci and Lucas numbers in a purely combinatorial way and, in the course of doing so, find a determinantal identity which we believe to be new.Ryser's theorem for \(\rho\)-Latin rectangleshttps://zbmath.org/1491.050402022-09-13T20:28:31.338867Z"Bahmanian, Amin"https://zbmath.org/authors/?q=ai:bahmanian.m-aminSummary: Let \(L\) be an \(n \times n\) array whose top left \(r \times s\) subarray is filled with \(k\) different symbols, each occurring at most once in each row and at most once in each column. We find necessary and sufficient conditions that ensure the remaining cells of \(L\) can be filled such that each symbol occurs at most once in each row and at most once in each column, and each symbol occurs a prescribed number of times in \(L\). The case where the prescribed number of times each symbol occurs is \(n\) was solved by \textit{H. J. Ryser} [Proc. Am. Math. Soc. 2, 550--552 (1951; Zbl 0043.01202)], and the case \(s = n\) was settled by \textit{J. L. Goldwasser} et al. [J. Comb. Theory, Ser. A 130, 26--41 (2015; Zbl 1303.05021]. Our technique leads to a very short proof of the latter.List coloring of two matroids through reduction to partition matroidshttps://zbmath.org/1491.050442022-09-13T20:28:31.338867Z"Bérczi, Kristóf"https://zbmath.org/authors/?q=ai:berczi.kristof"Schwarcz, Tamás"https://zbmath.org/authors/?q=ai:schwarcz.tamas"Yamaguchi, Yutaro"https://zbmath.org/authors/?q=ai:yamaguchi.yutaroAuthors' abstract: In the list coloring problem for two matroids, we are given matroids \(M_1=(S,\mathcal{I}_1)\) and \(M_2=(S,\mathcal{I}_2)\) on the same ground set \(S\), and the goal is to determine the smallest number \(k\) such that, given arbitrary lists \(L_s\) of \(k\) colors for \(s\in S\), it is possible to choose a color from each list so that every monochromatic set is independent in both \(M_1\) and \(M_2\). When both \(M_1\) and \(M_2\) are partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs [\textit{F. Galvin}, J. Comb. Theory, Ser. B 63, No. 1, 153--158 (1995; Zbl 0826.05026)] gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constant \(c\) such that if the coloring number is \(k\) (i.e., the ground set can be partitioned into \(k\) common independent sets), then the list coloring number is at most \(c\cdot k\). In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much and might be of independent combinatorial interest. In particular, we show that if \(M=(S,\mathcal{I})\) is a matroid in which \(S\) can be partitioned into \(k\) independent sets, then there exists a partition matroid \(N=(S,\mathcal{J})\) with \(\mathcal{J}\subseteq\mathcal{I}\) in which \(S\) can be partitioned into (A) \(k\) independent sets if \(M\) is a transversal matroid, (B) \(2k-1\) independent sets if \(M\) is a graphic matroid, (C) \(\lceil kr/(r-1)\rceil\) independent sets if \(M\) is a paving matroid of rank \(r\), and (D) \(2k-2\) independent sets if \(M\) is a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank of \(N\) is the same as that of \(M\). We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one.
Reviewer: Jack Koolen (Hefei)Matroids with different configurations and the same \(\mathcal{G} \)-invarianthttps://zbmath.org/1491.050452022-09-13T20:28:31.338867Z"Bonin, Joseph E."https://zbmath.org/authors/?q=ai:bonin.joseph-eSummary: From the configuration of a matroid (which records the size and rank of the cyclic flats and the containments among them, but not the sets), one can compute several much-studied matroid invariants, including the Tutte polynomial and a newer, stronger invariant, the \(\mathcal{G}\)-invariant. To gauge how much additional information the configuration contains compared to these invariants, it is of interest to have methods for constructing matroids with different configurations but the same \(\mathcal{G}\)-invariant. We offer several such constructions along with tools for developing more.The excluded minors for lattice path polymatroidshttps://zbmath.org/1491.050462022-09-13T20:28:31.338867Z"Bonin, Joseph E."https://zbmath.org/authors/?q=ai:bonin.joseph-e"Chun, Carolyn"https://zbmath.org/authors/?q=ai:chun.carolyn"Fife, Tara"https://zbmath.org/authors/?q=ai:fife.taraSummary: We find the excluded minors for the minor-closed class of lattice path polymatroids as a subclass of the minor-closed class of Boolean polymatroids. Like lattice path matroids and Boolean polymatroids, there are infinitely many excluded minors, but they fall into a small number of easily-described types.Twist polynomials of delta-matroidshttps://zbmath.org/1491.050492022-09-13T20:28:31.338867Z"Yan, Qi"https://zbmath.org/authors/?q=ai:yan.qi"Jin, Xian'an"https://zbmath.org/authors/?q=ai:jin.xiananSummary: Recently, \textit{J. L. Gross} et al. [Eur. J. Comb. 86, Article ID 103084, 20 p. (2020; Zbl 1437.05060] introduced the partial duality polynomial of a ribbon graph and posed a conjecture that there is no orientable ribbon graph whose partial duality polynomial has only one non-constant term. We found an infinite family of counterexamples for the conjecture and showed that essentially these are the only counterexamples. This is also obtained independently by \textit{S. Chmutov} and \textit{F. Vignes-Tourneret} [Eur. J. Comb. 97, Article ID 103368, 7 p. (2021; Zbl 1469.05083)] and they posed a problem: it would be interesting to know whether the partial duality polynomial and the related conjectures would make sense for general delta-matroids. In this paper, we show that partial duality polynomials have delta-matroid analogues. We introduce the twist polynomials of delta-matroids and discuss its basic properties for delta-matroids. We give a characterization of even normal binary delta-matroids whose twist polynomials have only one term and then prove that the twist polynomial of a normal binary delta-matroid contains non-zero constant term if and only if its intersection graph is bipartite.Spanning trees and spanning closed walks with small degreeshttps://zbmath.org/1491.050522022-09-13T20:28:31.338867Z"Hasanvand, Morteza"https://zbmath.org/authors/?q=ai:hasanvand.mortezaSummary: Let \(G\) be a graph and let \(f\) be a positive integer-valued function on \(V(G)\). In this paper, we show that if for all \(S \subseteq V(G)\), \(\omega(G \setminus S) < \sum_{v \in S}(f(v) - 2) + 2 + \omega(G [S])\), then \(G\) has a spanning tree \(T\) containing an arbitrary given matching such that for each vertex \(v\), \(d_T(v) \leq f(v)\), where \(\omega(G \setminus S)\) denotes the number of components of \(G \setminus S\) and \(\omega(G [S])\) denotes the number of components of the induced subgraph \(G [S]\) with the vertex set \(S\). This is an improvement of several results. Next, we prove that if for all \(S \subseteq V(G)\), \(\omega(G \setminus S) \leq \sum_{v \in S}(f(v) - 1) + 1\), then \(G\) admits a spanning closed walk passing through the edges of an arbitrary given matching meeting each vertex \(v\) at most \(f(v)\) times. This result solves a long-standing conjecture due to \textit{B. Jackson} and \textit{N. C. Wormald} [Australas. J. Comb. 2, 135--146 (1990; Zbl 0757.05074)].The component counts of random functionshttps://zbmath.org/1491.050532022-09-13T20:28:31.338867Z"Stark, Dudley"https://zbmath.org/authors/?q=ai:stark.dudleySummary: Consider functions \(f : A \to A \cup C\), where \(A\) and \(C\) are disjoint finite sets. The weakly connected components of the digraph of such a function are cycles of rooted trees, as in random mappings, and isolated rooted trees. Let \(n_1 = | A |\) and \(n_3 = | C |\). When a function is chosen from all \(( n_1 + n_3 )^{n_1}\) possibilities uniformly at random, then we find the following limiting behaviour as \(n_1 \to \infty \). If \(n_3 = o( n_1)\), then the size of the maximal mapping component goes to infinity almost surely; if \(n_3 \sim \gamma n_1\), \(\gamma > 0\) a constant, then process counting numbers of mapping components of different sizes converges; if \(n_1 = o( n_3)\), then the number of mapping components converges to 0 in probability. We get estimates on the size of the largest tree component which are of order \(\log n_3\) when \(n_3 \sim \gamma n_1\) and constant when \(n_3 \sim n_1^\alpha\), \(\alpha > 1\). These results are similar to ones obtained previously for random injections, for which the weakly connected components are cycles and linear trees.Multiplicative topological properties on degree based for fourth type of hex-derived networkshttps://zbmath.org/1491.050542022-09-13T20:28:31.338867Z"Ali, Haidar"https://zbmath.org/authors/?q=ai:ali.haidar"Dustigeer, Ghulam"https://zbmath.org/authors/?q=ai:dustigeer.ghulam"Li, Yong-Min"https://zbmath.org/authors/?q=ai:li.yongmin"Shafiq, Muhammad Kashif"https://zbmath.org/authors/?q=ai:shafiq.muhammad-kashif"Ali, Parvez"https://zbmath.org/authors/?q=ai:ali.parvez(no abstract)Sharp bounds on the arithmetic-geometric index of graphs and line graphshttps://zbmath.org/1491.050552022-09-13T20:28:31.338867Z"Li, Guohui"https://zbmath.org/authors/?q=ai:li.guohui"Zhang, Minjie"https://zbmath.org/authors/?q=ai:zhang.minjieSummary: As a degree-based topological index, the arithmetic-geometric index was firstly introduced by \textit{V. S. Shegehall} and \textit{R. Kanabur} [``Arithmetic-geometric indices of path graph'', J. Comp. Math. Sci. 6, No. 1, 19--24 (2015), \url{http://www.compmath-journal.org/dnload/Shegehalli-V-S-and-Rachanna-Kanabur/CMJV06I01P0019.pdf }] and was defined as \(AG=AG(G)=\sum_{uv\in E_G}\frac{d_u+d_v}{2\sqrt{d_ud_v}}\) for a nontrivial graph \(G\), where \(d_v\) is the degree of \(v\) in \(G\). In this paper, we determine some sharp upper and lower bounds on \(AG\) of graphs and characterize the corresponding extremal graphs, respectively. Through the relation between the graph \(G\) and its line graph \(L(G)\), some sharp upper and lower bounds on \(AG(L(G))\) are studied and the corresponding extremal graphs are also characterized.Bounds on general Randić index for \(F\)-sum graphshttps://zbmath.org/1491.050562022-09-13T20:28:31.338867Z"Li, Xu"https://zbmath.org/authors/?q=ai:li.xu"Ahmad, Maqsood"https://zbmath.org/authors/?q=ai:ahmad.maqsood"Javaid, Muhammad"https://zbmath.org/authors/?q=ai:javaid.muhammad"Saeed, Muhammad"https://zbmath.org/authors/?q=ai:saeed.muhammad-sarwar|saeed.muhammad-omer-bin|saeed.muhammad-tariq"Liu, Jia-Bao"https://zbmath.org/authors/?q=ai:liu.jia-baoSummary: A topological invariant is a numerical parameter associated with molecular graph and plays an imperative role in the study and analysis of quantitative structure activity/property relationships (QSAR/QSPR). The correlation between the entire \(\pi\)-electron energy and the structure of a molecular graph was explored and understood by the first Zagreb index. Recently, \textit{J.-B. Liu} et al. [``Computing first general Zagreb index of operations on graphs'', IEEE Access 7, 47494--47502 (2019; \url{doi:10.1109/ACCESS.2019.2909822})] calculated the first general Zagreb index of the \(F\)-sum graphs. In the same paper, they also proposed the open problem to compute the general Randić index \(R_\alpha(\Gamma)={\sum_{u v \in E (\Gamma)} [\mathrm{d}_\Gamma (u) \times \mathrm{d}_\Gamma (v)]^\alpha}\) of the \(F\)-sum graphs, where \(\alpha\in\mathbb{R}\) and \(\mathrm{d}_\Gamma (u)\) denote the valency of the vertex \(u\) in the molecular graph \(\Gamma\). Aim of this paper is to compute the lower and upper bounds of the general Randić index for the \(F\)-sum graphs when \(\alpha\in\mathbb{N}\). We present numerous examples to support and check the reliability as well as validity of our bounds. Furthermore, the results acquired are the generalization of the results offered by \textit{H. Deng} et al. [Appl. Math. Comput. 275, 422--431 (2016; Zbl 1410.05176)], who studied the general Randić index for exactly \(\alpha =1\).On topological properties of degree-based entropy of hex-derived network of type 3https://zbmath.org/1491.050572022-09-13T20:28:31.338867Z"Zhu, Cun-Bin"https://zbmath.org/authors/?q=ai:zhu.cun-bin"Ali, Haidar"https://zbmath.org/authors/?q=ai:ali.haidar"Ali, Bilal"https://zbmath.org/authors/?q=ai:ali.bilal"Ali, Parvez"https://zbmath.org/authors/?q=ai:ali.parvez"Liu, Jia-Bao"https://zbmath.org/authors/?q=ai:liu.jia-bao(no abstract)On crossing-families in planar point setshttps://zbmath.org/1491.050582022-09-13T20:28:31.338867Z"Aichholzer, Oswin"https://zbmath.org/authors/?q=ai:aichholzer.oswin"Kynčl, Jan"https://zbmath.org/authors/?q=ai:kyncl.jan"Scheucher, Manfred"https://zbmath.org/authors/?q=ai:scheucher.manfred"Vogtenhuber, Birgit"https://zbmath.org/authors/?q=ai:vogtenhuber.birgit"Valtr, Pavel"https://zbmath.org/authors/?q=ai:valtr.pavelSummary: A \(k\)-crossing family in a point set \(S\) in general position is a set of \(k\) segments spanned by points of \(S\) such that all \(k\) segments mutually cross. In this short note we present two statements on crossing families which are based on sets of small cardinality: (1) Any set of at least \(15\) points contains a crossing family of size \(4\). (2) There are sets of \(n\) points which do not contain a crossing family of size larger than \(8\lceil\frac{n}{41}\rceil\). Both results improve the previously best known bounds.On the spanning and routing ratios of the directed \(\Theta_6\)-graphhttps://zbmath.org/1491.050592022-09-13T20:28:31.338867Z"Akitaya, Hugo A."https://zbmath.org/authors/?q=ai:akitaya.hugo-a"Biniaz, Ahmad"https://zbmath.org/authors/?q=ai:biniaz.ahmad"Bose, Prosenjit"https://zbmath.org/authors/?q=ai:bose.prosenjit-kSummary: The family of \(\Theta_k\)-graphs is an important class of sparse geometric spanners with a small spanning ratio. Although they are a well-studied class of geometric graphs, no bound is known on the spanning and routing ratios of the directed \(\Theta_6\)-graph. We show that the directed \(\Theta_6\)-graph of a point set \(P\), denoted \(\overrightarrow{\Theta}_6(P)\), is a \(7\)-spanner and there exist point sets where the spanning ratio is at least \(4-\varepsilon\), for any \(\varepsilon > 0\). It is known that the standard greedy \(\Theta\)-routing algorithm may have an unbounded routing ratio on \(\overrightarrow{\Theta}_6(P)\). We design a simple, online, local, memoryless routing algorithm on \(\overrightarrow{\Theta}_6(P)\) whose routing ratio is at most \(8\) and show that no algorithm can have a routing ratio better than \(6-\varepsilon\).Triangulability of convex graphs and convex skewnesshttps://zbmath.org/1491.050602022-09-13T20:28:31.338867Z"Ali, Niran Abbas"https://zbmath.org/authors/?q=ai:ali.niran-abbas"Chia, Gek L."https://zbmath.org/authors/?q=ai:chia.gek-ling"Trao, Hazim Michman"https://zbmath.org/authors/?q=ai:trao.hazim-michman"Kilicman, Adem"https://zbmath.org/authors/?q=ai:kilicman.ademA graph associated to a commutative semiringhttps://zbmath.org/1491.050612022-09-13T20:28:31.338867Z"Atani, Shahabaddin Ebrahimi"https://zbmath.org/authors/?q=ai:ebrahimi-atani.shahabaddin"Khoramdel, Mehdi"https://zbmath.org/authors/?q=ai:khoramdel.mehdi"Hesari, Saboura Dolati Pish"https://zbmath.org/authors/?q=ai:dolati-pishhesari.sabouraSummary: Let \(R\) be a commutative finite semiring with nonzero identity and \(H\) be an arbitrary multiplicatively closed subset \(R\). The generalized identity-summand graph of \(R\) is the (simple) graph \(G_H (R)\) with all elements of \(R\) as the vertices, and two distinct vertices \(x\) and \(y\) are adjacent if and only if \(x + y \in H\). In this paper, we study some basic properties of \(G_H (R)\). Moreover, we characterize the planarity, chromatic number, clique number and independence number of \(G_H (R)\).Subcubic planar graphs of girth 7 are class Ihttps://zbmath.org/1491.050622022-09-13T20:28:31.338867Z"Bonduelle, Sebastien"https://zbmath.org/authors/?q=ai:bonduelle.sebastien"Kardoš, František"https://zbmath.org/authors/?q=ai:kardos.frantisekSummary: We prove that planar graphs of maximum degree 3 and of girth at least 7 are 3-edge-colorable, extending the previous result for girth at least 8 by Kronk, Radlowski, and Franen
from 1974.Another tight description of faces in plane triangulations with minimum degree 4https://zbmath.org/1491.050632022-09-13T20:28:31.338867Z"Borodin, O. V."https://zbmath.org/authors/?q=ai:borodin.oleg-veniaminovich"Ivanova, A. O."https://zbmath.org/authors/?q=ai:ivanova.anna-olegovnaSummary: It follows from the classical theorem by \textit{H. Lebesgue} [J. Math. Pures Appl. (9) 19, 27--43 (1940; Zbl 0024.28701)] on the structure of minor faces in 3-polytopes that every plane triangulation with minimum degree at least 4 has a 3-face for which the set of degrees of its vertices is majorized by one of the following sequences:
\[
(4, 4, \infty), (4, 5, 19), (4, 6, 11), (4, 7, 9), (5, 5, 9), (5, 6, 7).
\]
\textit{S. Jendrol'} [Discrete Math. 196, No. 1--3, 177--196 (1999; Zbl 0934.05044)] gave the following description of faces: \((4, 4, \infty)\), \((4, 5, 13)\), \((4, 6, 17)\), \((4, 7, 8)\), \((5, 5, 7)\), \((5, 6, 6)\). Also, Jendrol' [loc. cit.] conjectured that there is a face of one of the types: \((4, 4, \infty)\), \((4, 5, 10)\), \((4, 6, 15)\), \((4, 7, 7)\), \((5, 5, 7)\), \((5, 6, 6)\).
Lebesgue's description was strengthened by \textit{O. V. Borodin} [Diskretn. Anal. Issled. Oper., Ser. 1 9, No. 3, 29--39 (2002; Zbl 1015.52008)] to \((4, 4, \infty)\), \((4, 5, 17)\), \((4, 6, 11)\), \((4, 7, 8)\), \((5, 5, 8)\), \((5, 6, 6)\). The authors [Sib. Math. J. 55, No. 1, 12--18 (2014; Zbl 1302.52012); translation from Sib. Mat. Zh. 55, No. 1, 17--24 (2014)] obtained the following tight description, which, in particular, disproves the above mentioned conjecture by Jendrol': \((4, 4, \infty)\), \((4, 5, 11)\), \((4, 6, 10)\), \((4, 7, 7)\), \((5, 5, 7)\), \((5, 6, 6)\).
The purpose of this paper is to give another tight description of faces in plane triangulations with minimum degree at least 4: \((4, 4, \infty)\), \((4, 6, 10)\), \((4, 7, 7)\), \((5, 5, 8)\), \((5, 6, 7)\).On polynomials counting essentially irreducible mapshttps://zbmath.org/1491.050642022-09-13T20:28:31.338867Z"Budd, Timothy"https://zbmath.org/authors/?q=ai:budd.timothy-gSummary: We consider maps on genus-\(g\) surfaces with \(n\) (labeled) faces of prescribed even degrees. It is known since work of \textit{P. Norbury} [Math. Res. Lett. 17, No. 3, 467--481 (2010; Zbl 1225.32023)] that, if one disallows vertices of degree one, the enumeration of such maps is related to the counting of lattice point in the moduli space of genus-\(g\) curves with \(n\) labeled points and is given by a symmetric polynomial \(N_{g,n} (\ell_1, \ldots, \ell_n)\) in the face degrees \(2\ell_1, \ldots, 2\ell_n\). We generalize this by restricting to genus-\(g\) maps that are essentially \(2b\)-irreducible for \(b\geqslant 0\), which loosely speaking means that they are not allowed to possess contractible cycles of length less than \(2b\) and each such cycle of length \(2b\) is required to bound a face of degree \(2b\). The enumeration of such maps is shown to be again given by a symmetric polynomial \(\hat{N}_{g,n}^{(b)}(\ell_1, \ldots, \ell_n)\) in the face degrees with a polynomial dependence on \(b\). These polynomials satisfy (generalized) string and dilaton equations, which for \(g\leqslant 1\) uniquely determine them. The proofs rely heavily on a substitution approach by \textit{J. Bouttier} and \textit{E. Guitter} [Electron. J. Comb. 21, No. 1, Research Paper P1.23, 18 p. (2014; Zbl 1300.05070)] and the enumeration of planar maps on genus-\(g\) surfaces.A sufficient condition for a planar graph to be \((\mathcal{F},\mathcal{F}_2)\)-partitionablehttps://zbmath.org/1491.050652022-09-13T20:28:31.338867Z"Liu, Runrun"https://zbmath.org/authors/?q=ai:liu.runrun"Wang, Weifan"https://zbmath.org/authors/?q=ai:wang.wei-fanSummary: An \((\mathcal{F},\mathcal{F}_d)\)-partition of a graph \(G\) is a partition of \(V(G)\) into sets \(V_1\) and \(V_2\) such that the induced graph \(G[V_1]\) is a forest and \(G[V_2]\) is a forest of maximum degree at most \(d\). It was known that every planar graph without triangles is \((\mathcal{F},\mathcal{F}_3)\)-partitionable. In this paper, we show that planar graphs without triangles and chordal 6-cycles are \((\mathcal{F},\mathcal{F}_2)\)-partitionable.A novel study of graphs based on \(m\)-polar cubic structureshttps://zbmath.org/1491.050662022-09-13T20:28:31.338867Z"Muhiuddin, G."https://zbmath.org/authors/?q=ai:muhiuddin.ghulam"Alanazi, A. M."https://zbmath.org/authors/?q=ai:alanazi.abdulaziz-m"Mahboob, A."https://zbmath.org/authors/?q=ai:mahboob.ahsan"Alkhaldi, A. H."https://zbmath.org/authors/?q=ai:alkhaldi.ali-h"Alatwai, Wejdan"https://zbmath.org/authors/?q=ai:alatwai.wejdan(no abstract)Some results on an intersection graph of a topologyhttps://zbmath.org/1491.050672022-09-13T20:28:31.338867Z"Muneshwar, R. A."https://zbmath.org/authors/?q=ai:muneshwar.raju-a"Bondar, K. L."https://zbmath.org/authors/?q=ai:bondar.kirankumar-lIn this paper, the authors define the intersection graph \(I_\tau(X)\) as follows: its vertices are all topologies defined on a finite set \(X\), except the discrete and the indiscrete topologies, and two such topologies \((X, \tau_1), (X,\tau_2)\) are adjacent if the intersection of \(\tau_1\) and \(\tau_2\) is not the indiscrete topology. The authors study several properties of \(I_\tau(X)\): its diameter, girth, connectivity, maximal independent sets, and different variants of the domination number. They also derive upper and lower bounds on its clique number and chromatic number.
Reviewer: Josef Lauri (Msida)Positively curved graphshttps://zbmath.org/1491.050682022-09-13T20:28:31.338867Z"Yancey, Matthew P."https://zbmath.org/authors/?q=ai:yancey.matthew-pSummary: This paper consists of two halves. In the first half of the paper, we consider real-valued functions \(f\) whose domain is the vertex set of a graph \(G\) and that are Lipschitz with respect to the graph distance. By placing a uniform distribution on the vertex set, we treat as a random variable. We investigate the link between the isoperimetric function of \(G\) and the functions \(f\) that have maximum variance or meet the bound established by the subgaussian inequality. We present several results describing the extremal functions, and use those results to (a) resolve a conjecture by \textit{S. G. Bobkov} et al. [Isr. J. Math. 156, 255--283 (2006; Zbl 1134.60016)] characterizing the extremal functions of the subgaussian inequality of the odd cycle and (b) providing a construction that gives a partial negative answer to a question by \textit{N. Alon} et al. [Geom. Funct. Anal. 8, No. 3, 411--436 (1998; Zbl 0907.60018)] on the relationship between maximum variance functions and the isoperimetric function of product graphs. While establishing a discrete analogue of the curved Brunn-Minkowski inequality for the discrete hypercube, \textit{Y. Ollivier} and \textit{C. Villani} [SIAM J. Discrete Math. 26, No. 3, 983--996 (2012; Zbl 1267.52010)] suggested several avenues for research. We resolve them in the second half of the paper as follows:
\par i) They propose that a bound on \(t\)-midpoints can be obtained by repeated application of the bound on midpoints if the original sets are convex. We construct a specific example where this reasoning fails, and then prove our construction is general by characterizing the convex sets in the discrete hypercube.
\par ii) A second proposed technique to bound \(t\)-midpoints involves new results in the concentration of measure. We follow through on this proposal, with heavy use of results from the first half of the paper.
\par iii) We show that the curvature of the discrete hypercube is not positive or zero, but we also give a result indicating that it may satisfy a weaker version of curvature.On some properties of edge quasi-distance-balanced graphshttps://zbmath.org/1491.050692022-09-13T20:28:31.338867Z"Aliannejadi, Zohreh"https://zbmath.org/authors/?q=ai:aliannejadi.zohreh"Gilani, Alireza"https://zbmath.org/authors/?q=ai:gilani.alireza"Alaeiyan, Mehdi"https://zbmath.org/authors/?q=ai:alaeiyan.mehdi"Asadpour, Jafar"https://zbmath.org/authors/?q=ai:asadpour.jafarSummary: For an edge \(e = uv\) in a graph \(G\), \(M^G_u (e)\) is introduced as the set all edges of \(G\) that are at shorter distance to \(u\) than to \(v\). We say that \(G\) is an edge quasi-distance-balanced graph whenever for every arbitrary edge \(e = uv\) ,there exists a constant \(\lambda > 1\) such that \(m^G_u(e) = \lambda^{\pm 1} m^G_v(e)\). We investigate that edge quasi-distance-balanced graphs are complete bipartite graphs \(K_{m,n}\) with \(m \neq n\). The aim of this paper is to investigate the notion of cycles in edge quasi-distance-balanced graphs, and expand some techniques generalizing new outcome that every edge quasi-distance-balanced graph is complete bipartite graph. As well as, it is demonstrated that connected quasi-distance-balanced graph admitting a bridge is not edge quasi-distance-balanced graph.Concatenating bipartite graphshttps://zbmath.org/1491.050702022-09-13T20:28:31.338867Z"Chudnovsky, Maria"https://zbmath.org/authors/?q=ai:chudnovsky.maria"Hompe, Patrick"https://zbmath.org/authors/?q=ai:hompe.patrick"Scott, Alex"https://zbmath.org/authors/?q=ai:scott.alexander-d"Seymour, Paul"https://zbmath.org/authors/?q=ai:seymour.paul-d"Spirkl, Sophie"https://zbmath.org/authors/?q=ai:spirkl.sophie-theresaSummary: Let \(x, y\in (0,1]\), and let \(A\), \(B\), \(C\) be disjoint nonempty stable subsets of a graph \(G\), where every vertex in \(A\) has at least \(x|B|\) neighbours in \(B\), and every vertex in \(B\) has at least \(y|C|\) neighbours in \(C\), and there are no edges between \(A\), \(C\). We denote by \(\phi(x, y)\) the maximum \(z\) such that, in all such graphs \(G\), there is a vertex \(v\in C\) that is joined to at least \(z|A|\) vertices in \(A\) by two-edge paths. This function has some interesting properties: we show, for instance, that \(\phi(x, y)=\phi(y, x)\) for all \(x\), \(y\), and there is a discontinuity in \(\phi(x, x)\) when \(1/x\) is an integer. For \(z=1/2, 2/3, 1/3, 3/4, 2/5, 3/5\), we try to find the (complicated) boundary between the set of pairs \((x, y)\) with \(\phi(x, y)\geqslant z\) and the pairs with \(\phi(x, y)<z\). We also consider what happens if in addition every vertex in \(B\) has at least \(x|A|\) neighbours in \(A\), and every vertex in \(C\) has at least \(y|B|\) neighbours in \(B\).
We raise several questions and conjectures; for instance, it is open whether \(\phi(x, x)\geqslant 1/2\) for all \(x>1/3\).Isometric subgraphs for Steiner distancehttps://zbmath.org/1491.050712022-09-13T20:28:31.338867Z"Weißauer, Daniel"https://zbmath.org/authors/?q=ai:weissauer.danielLet \(G\) be a connected graph, \(H\) its subgraph and \(l:E(G) \to {\mathbb{R}}^+\) a length-function on \(G\). The length of \(H\), \(l(H)\), is the sum of lengths of its edges. The Steiner distance of \(A \subseteq V(G)\), sd\(_G(A)\), is the minimum length of a connected subgraph of \(G\) that contains \(A\). For \(k \geq 2\), a subgraph \(H\) of a graph \(G\) is \(k\)-isometric in \(G\) if sd\(_H(A) \leq\) sd\(_G(A)\) for any \(A \subseteq V(H)\) of cardinality at most \(k\). A subgraph is fully isometric if it is \(k\)-isometric for any \(k \in \mathbb{N}\). For a graph \(H\), a tree \(T\) and length-function \(l\) on \(T \cup H\), \(T\) is called a shortcut tree for \(H\) if the vertices contained in \(T\) and \(H\) are exactly the leaves of \(T\) (denoted by \(L(T)\)), \(E(T) \cap E(H) = \emptyset\), \(l(T) <\) sd\(_H(L(T))\), and sd\(_H(B) \leq\) sd\(_T(B)\) for any \(B \subset L(T)\).
For any subgraph \(H\) of a graph \(G\) it holds that \(H\) being \(k\)-isometric implies that \(H\) is \(m\)-isometric for any \(m < k\). The authors of this paper investigate for which graphs \(G\) and \(H \subseteq G\) hold that \(H\) being \(k\)-isometric subgraph implies that \(H\) is fully isometric. They first consider subgraphs that are trees and prove that if a tree \(T \subseteq G\) is 2-isometric, then it is fully isometric. Then they consider a subgraph \(C\) of \(G\) which is a cycle. It is proved that if \(C\) is 6-isometric, then it is fully isometric. Moreover, an example proving that 6 is optimal is presented.
Finally, the following graph families are considered.
\par i) \({\mathcal{H}}_k\) is the set of graphs \(H\) having the following property: if \(H\) is a \(k\)-isometric subgraph of a graph \(G\) (with respect to the given length-function), then \(H\) is fully isometric.
\par ii) For a tree \(T\), \({\mathcal{G}}_T\) is the class of graphs for which there exists no shortcut tree isomorphic to \(T\).
The authors prove several properties for both families \({\mathcal{H}}_k\) and \({\mathcal{G}}_T\). It is proved that \({\mathcal{H}}_2\) is the class of forests and \({\mathcal{G}}_{K_{1,4}}\) is the class of outerplanar graphs.
Reviewer: Tanja Dravec (Maribor)The Erdős-Hajnal conjecture for three colors and triangleshttps://zbmath.org/1491.050722022-09-13T20:28:31.338867Z"Axenovich, Maria"https://zbmath.org/authors/?q=ai:axenovich.maria-a"Snyder, Richard"https://zbmath.org/authors/?q=ai:snyder.richard"Weber, Lea"https://zbmath.org/authors/?q=ai:weber.lea-louiseAuthors' abstract: \textit{P. Erdős} and \textit{G. Szekeres}'s quantitative version of Ramsey's theorem [Compos. Math. 2, 463--470 (1935; Zbl 0012.27010)] asserts that in every \(2\)-edge-coloring of \(K_n\) there is a monochromatic clique on at least \(\frac{1}{2}\log n\) vertices. The famous Erdős-Hajnal conjecture claims that forbidding fixed colorings on subgraphs ensures much larger monochromatic cliques. Specifically, the most general, multi-color version of the conjecture states that for any fixed integers \(k\), \(s\) and any \(s\)-edge-coloring \(c\) of \(K_k\), there exists \(\varepsilon > 0\) such that in any \(s\)-edge-coloring of \(K_n\) that avoids \(c\) there is a clique on at least \(n\varepsilon\) vertices, using at most \(s-1\) colors. The conjecture is open in general, though a few partial results are known.
Here, we focus on quantitative aspects of this conjecture in the case when \(k =3\) and \(s = 3\), and when there are several forbidden subgraph colorings. More precisely, for a family \(\mathcal{H}\) of triangles, each edge-colored with colors from \(\{r, b, y\}\), \(\textrm{Forb}(n, H)\) denotes the family of edge-colorings of \(K_n\) using colors from \(\{r, b, y\}\) and containing none of the colorings from \(\mathcal{H}\). Let \(h_2(n, H)\) be the maximum \(q\) such that any coloring from \(\textrm{Forb}(n, H)\) has a clique on at least \(q\) vertices using at most two colors. We provide bounds on \(h_2(n, H)\) for all families \(\mathcal{H}\) consisting of at most three triangles. For most of them, our bounds are asymptotically tight. This, in particular, extends a result of \textit{J. Fox} et al. [J. Comb. Theory, Ser. B 111, 75--125 (2015; Zbl 1307.05069)], who determined \(h_2(n, H)\) for \(\mathcal{H}\) consisting of a rainbow triangle. In addition, we prove that for some \(\mathcal{H}\), \(h_2(n, H)\) corresponds to certain classical Ramsey numbers, the smallest independence number in graphs of given odd girth, or some other natural graph-theoretic parameters.
Reviewer: Borut Lužar (Šmarješke Toplice)Defective colorings on \(k\)-uniform hypergraphshttps://zbmath.org/1491.050732022-09-13T20:28:31.338867Z"Boonklurb, Ratinan"https://zbmath.org/authors/?q=ai:boonklurb.ratinan"Muaengwaeng, Artchariya"https://zbmath.org/authors/?q=ai:muaengwaeng.artchariya"Singhun, Sirirat"https://zbmath.org/authors/?q=ai:singhun.siriratThe coloring of graphs is a central topic in graph theory.
In this paper, the authors extend the definition of defective coloring from graphs to hypergraphs as follows.
Definition \(1.1\): Let \(d \geq 0\). A \((\lambda, d)\)-defective coloring is a \(\lambda\)-coloring of a hypergraph \(H\) in which there are at most \(d\) monochromatic edges. If \(H\) admits a \((\lambda, d)\)-defective coloring, then \(\chi_{\leq d}(H)\) denotes the least integer \(\lambda\). Note that \((\lambda, 0)\)-defective coloring of a hypergraph \(H\) is a proper \(\lambda\)-coloring of such hypergraph.
Many properties and relationships among these colorings on hypergraphs are explored and the chromatic number of each type of coloring for several hypergraphs, in particular, a complete \(k\)-uniform hypergraph on \(n\) vertices and a complete \(r\)-partite \(k\)-uniform hypergraph are obtained. Lastly, they raise the following conjecture.
Conjecture: Let \(m \geq 3\) and \(t=\left\lfloor\frac{m}{2}\right\rfloor\). If \(K_{3 \times m}^{(3)}\) is a complete tripartite 3-uniform hypergraph with \(m^{3}-(t+1) m^{2}+t^{2} m > d> 0\), then \(\chi_{\leq d}\left(K_{3 \times m}^{(3)}\right)=3\).
Reviewer: Vinayak Joshi (Pune)Acyclic, star, and injective colouring: bounding the diameterhttps://zbmath.org/1491.050742022-09-13T20:28:31.338867Z"Brause, Christoph"https://zbmath.org/authors/?q=ai:brause.christoph"Golovach, Petr"https://zbmath.org/authors/?q=ai:golovach.petr-a"Martin, Barnaby"https://zbmath.org/authors/?q=ai:martin.barnaby-d"Ochem, Pascal"https://zbmath.org/authors/?q=ai:ochem.pascal"Paulusma, Daniël"https://zbmath.org/authors/?q=ai:paulusma.daniel"Smith, Siani"https://zbmath.org/authors/?q=ai:smith.sianiSummary: We examine the effect of bounding the diameter for a number of natural and well-studied variants of the colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as \(L(1, 1)\)-Labelling and we also consider the framework of \(L(a, b)\)-Labelling. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most \(d\), Acyclic \(3\)-Colouring is polynomial-time solvable if \(d\leqslant 2\) but NP-complete if \(d\geqslant 4\), and Star \(3\)-Colouring is polynomial-time solvable if \(d\leqslant 3\) but NP-complete for \(d\geqslant 8\). As far as we are aware, Star \(3\)-Colouring is the first problem that exhibits a complexity jump for some \(d\geqslant 3\). Our third main result is that \(L(1, 2)\)-Labelling is NP-complete for graphs of diameter \(2\); we relate the latter problem to a special case of Hamiltonian Path.On the chromatic number of some \(P_5\)-free graphshttps://zbmath.org/1491.050752022-09-13T20:28:31.338867Z"Dong, Wei"https://zbmath.org/authors/?q=ai:dong.wei"Xu, Baogang"https://zbmath.org/authors/?q=ai:xu.baogang"Xu, Yian"https://zbmath.org/authors/?q=ai:xu.yianSummary: Let \(G\) be a graph. We say that \(G\) is perfectly divisible if for each induced subgraph \(H\) of \(G\), \(V(H)\) can be partitioned into \(A\) and \(B\) such that \(H [A]\) is perfect and \(\omega(H [B]) < \omega(H)\). We use \(P_t\) and \(C_t\) to denote a path and a cycle on \(t\) vertices, respectively. For two disjoint graphs \(F_1\) and \(F_2\), we use \(F_1 \cup F_2\) to denote the graph with vertex set \(V( F_1) \cup V( F_2)\) and edge set \(E( F_1) \cup E( F_2)\), and use \(F_1 + F_2\) to denote the graph with vertex set \(V( F_1) \cup V( F_2)\) and edge set \(E( F_1) \cup E( F_2) \cup \{x y \mid x \in V( F_1) \text{ and } y \in V( F_2) \} \). In this paper, we prove that (i) \(( P_5, C_5, K_{2 , 3})\)-free graphs are perfectly divisible, (ii) \( \chi(G) \leq 2 \omega^2(G) - \omega(G) - 3\) if \(G\) is \(( P_5, K_{2 , 3})\)-free with \(\omega(G) \geq 2\), (iii) \( \chi(G) \leq \frac{ 3}{ 2}( \omega^2(G) - \omega(G))\) if \(G\) is \(( P_5, K_1 + 2 K_2)\)-free, and (iv) \( \chi(G) \leq 3 \omega(G) + 11\) if \(G\) is \(( P_5, K_1 +( K_1 \cup K_3))\)-free.Bipartite completion of colored graphs avoiding chordless cycles of given lengthshttps://zbmath.org/1491.050762022-09-13T20:28:31.338867Z"Eschen, Elaine M."https://zbmath.org/authors/?q=ai:eschen.elaine-m"Sritharan, R."https://zbmath.org/authors/?q=ai:sritharan.rSummary: We consider a well-known restriction of the graph sandwich problem: Given a graph \(G\) with a proper vertex coloring, determine if there is a completion of \(G\) (formed by adding edges to \(G\) while maintaining the proper coloring) that has property \(P\). We are interested in completions of \(G\) that are bipartite graphs without induced cycles of prescribed lengths. It is known that deciding whether there is a chordal bipartite completion, namely one without induced cycles on six or more vertices, is NP-complete when the input graph is colored with an arbitrary number of colors. We consider the case when the input graph is 3-colored and show that the problem of deciding whether there is a bipartite completion that avoids induced cycles \(C_6,C_8,\dots,C_{2p}\), for fixed \(p\geq 3\), is NP-complete. In contrast, we characterize chordal bipartite completions of 3-colored graphs, and based on this, show that deciding whether a 3-colored graph can be completed to be chordal bipartite is solvable in \(O(m+n\alpha(n))\) time. When the input admits a chordal bipartite completion, a size-\(n\) representation of a chordal bipartite completion can be constructed within the same time bound. It follows from our results that for every fixed \(k\geq 3\), and for every fixed \(p\geq 3\), deciding whether a \(k\)-colored graph can be completed to be bipartite and \((C_6,C_8,\dots,C_{2p})\)-free is NP-complete. Also, the corresponding graph sandwich problems are hard.An incremental search heuristic for coloring vertices of a graphhttps://zbmath.org/1491.050772022-09-13T20:28:31.338867Z"Ghosal, Subhankar"https://zbmath.org/authors/?q=ai:ghosal.subhankar"Ghosh, Sasthi C."https://zbmath.org/authors/?q=ai:ghosh.sasthi-cIn this paper, the authors propose an incremental search heuristic (ISH) method for vertex coloring. First, they expound on the greedy coloring by predecessors and list several good orders of vertices for coloring. Then, the authors prove several related theorems about coloring order, by which an algorithm framework ISH is developed. The algorithm is simple and fast. On small sparse graphs, the algorithm can obtain the same or even a few smaller chromatic numbers than other classical algorithms. However, compared with the hybrid genetic algorithm, the accuracy of the algorithm needs to be improved. The algorithm only achieved a smaller chromatic number on one test set, while the genetic algorithm achieved a smaller chromatic number on six test sets.
For the entire collection see [Zbl 1465.05002].
Reviewer: Enqiang Zhu (Peking)Switching 3-edge-colorings of cubic graphshttps://zbmath.org/1491.050782022-09-13T20:28:31.338867Z"Goedgebeur, Jan"https://zbmath.org/authors/?q=ai:goedgebeur.jan"Östergård, Patric R. J."https://zbmath.org/authors/?q=ai:ostergard.patric-r-jSummary: The chromatic index of a cubic graph is either 3 or 4. Edge-Kempe switching, which can be used to transform edge-colorings, is here considered for 3-edge-colorings of cubic graphs. Computational results for edge-Kempe switching of cubic graphs up to order 30 and bipartite cubic graphs up to order 36 are tabulated. Families of cubic graphs of orders \(4 n + 2\) and \(4 n + 4\) with \(2^n\) edge-Kempe equivalence classes are presented; it is conjectured that there are no cubic graphs with more edge-Kempe equivalence classes. New families of nonplanar bipartite cubic graphs with exactly one edge-Kempe equivalence class are also obtained. Edge-Kempe switching is further connected to cycle switching of Steiner triple systems, for which an improvement of the established classification algorithm is presented.Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphshttps://zbmath.org/1491.050792022-09-13T20:28:31.338867Z"Goldwasser, John"https://zbmath.org/authors/?q=ai:goldwasser.john-l"Hansen, Ryan"https://zbmath.org/authors/?q=ai:hansen.ryanFor a graph \(G\) and a family \(\mathcal{H}\) of subgraphs of \(G\), we say a (not necessarily proper) colouring of the edges of \(G\) is \(\mathcal{H}\)-polychromatic if every graph in \(\mathcal{H}\) has edges of every colour used in the colouring of \(G\). The largest possible number of colourings in an \(\mathcal{H}\)-polychromatic colouring of \(G\) is called the \(\mathcal{H}\)-polychromatic number of \(G\) and is denoted by poly\(_{\mathcal{H}}(G)\).
We consider the case where \(G\) is a complete graph on \(n\) vertices and abuse notation by writing poly\(_{\mathcal H}(n)\) for poly\(_{\mathcal H}(K_{n})\). As by Ramsey's theorem, if the graphs in \(\mathcal{H}\) were of bounded size we would get poly\(_{\mathcal H}(n)\)=1, we should only look at cases where the graphs in \(\mathcal{H}\) increase in size with \(n\).
In [\textit{M. Axenovich} et al., J. Graph Theory 87, No. 4, 660--671 (2018; Zbl 1386.05051)] the value of poly\(_{\mathcal{H}}(n)\) is determined when \(\mathcal{H}\) is the set of perfect matchings (\(n\) even) and is approximated to within a small additive constant when \(\mathcal{H}\) is the set of 2-regular graphs or \(\mathcal{H}\) is the set of Hamilton cycles.
The paper under review deals with the cases where (for a fixed integer \(q\)) \(\mathcal{H}\) is the set of all matchings covering \(n-q\) vertices, all \((n-q)\) cycles and all 2-regular graphs on at least \(n-q\) vertices. In all cases the exact answer is obtained. Note that for \(q=0\) the results confirm and extend those of Axenovich et al.
The optimal colourings are based on certain orderings. There are links with extensions of results on Ramsey numbers for cycles in a graph. A conjecture more general than most of the results in the paper is also made.
Reviewer: David B. Penman (Colchester)Complete edge-colored permutation graphshttps://zbmath.org/1491.050802022-09-13T20:28:31.338867Z"Hartmann, Tom"https://zbmath.org/authors/?q=ai:hartmann.tom"Bannach, Max"https://zbmath.org/authors/?q=ai:bannach.max"Middendorf, Martin"https://zbmath.org/authors/?q=ai:middendorf.martin"Stadler, Peter F."https://zbmath.org/authors/?q=ai:stadler.peter-f"Wieseke, Nicolas"https://zbmath.org/authors/?q=ai:wieseke.nicolas"Hellmuth, Marc"https://zbmath.org/authors/?q=ai:hellmuth.marcSummary: We introduce the concept of complete edge-colored permutation graphs as complete graphs that are the edge-disjoint union of ``classical'' permutation graphs. We show that a graph \(G = (V, E)\) is a complete edge-colored permutation graph if and only if each monochromatic subgraph of \(G\) is a ``classical'' permutation graph and \(G\) does not contain a triangle with 3 different colors. Using the modular decomposition as a framework we demonstrate that complete edge-colored permutation graphs are characterized in terms of their strong prime modules, which induce also complete edge-colored permutation graphs. This leads to an \(\mathcal{O}(| V |^2)\)-time recognition algorithm. We show, moreover, that complete edge-colored permutation graphs form a superclass of so-called symbolic ultrametrics and that the coloring of such graphs is always a Gallai coloring.Upper bounds for positive semidefinite propagation timehttps://zbmath.org/1491.050812022-09-13T20:28:31.338867Z"Hogben, Leslie"https://zbmath.org/authors/?q=ai:hogben.leslie"Hunnell, Mark"https://zbmath.org/authors/?q=ai:hunnell.mark"Liu, Kevin"https://zbmath.org/authors/?q=ai:liu.kevin-fong-rey"Schuerger, Houston"https://zbmath.org/authors/?q=ai:schuerger.houston"Small, Ben"https://zbmath.org/authors/?q=ai:small.ben"Zhang, Yaqi"https://zbmath.org/authors/?q=ai:zhang.yaqiSummary: The tight upper bound \(\operatorname{pt}_+(G) \leq \lceil \frac{ | V ( G ) | - \operatorname{Z}_+ ( G )}{ 2} \rceil\) is established for the positive semidefinite propagation time of a graph in terms of its positive semidefinite zero forcing number. To prove this bound, two methods of transforming one positive semidefinite zero forcing set into another and algorithms implementing these methods are presented. Consequences of the bound, including a tight Nordhaus-Gaddum sum upper bound on positive semidefinite propagation time, are established.Multicolor Turán numbershttps://zbmath.org/1491.050822022-09-13T20:28:31.338867Z"Imolay, András"https://zbmath.org/authors/?q=ai:imolay.andras"Karl, János"https://zbmath.org/authors/?q=ai:karl.janos"Nagy, Zoltán Lóránt"https://zbmath.org/authors/?q=ai:nagy.zoltan-lorant"Váli, Benedek"https://zbmath.org/authors/?q=ai:vali.benedekSummary: We consider a natural generalization of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi problem by studying the maximum number \(\text{ex}_F(n, G)\) of edge-disjoint copies of a fixed graph \(F\) can be placed on an \(n\)-vertex ground set without forming a subgraph \(G\) whose edges are from different \(F\)-copies. We determine the pairs \(\{F, G \}\) for which the order of magnitude of \(\text{ex}_F(n, G)\) is quadratic and prove several asymptotic results using various tools from the regularity lemma and supersaturation to graph packing results.Rainbow dominator coloring in graphshttps://zbmath.org/1491.050832022-09-13T20:28:31.338867Z"Jagannatharao, Kulkarni Sunita"https://zbmath.org/authors/?q=ai:jagannatharao.kulkarni-sunita"Rajendra, S. K."https://zbmath.org/authors/?q=ai:rajendra.s-k"Murali, R."https://zbmath.org/authors/?q=ai:murali.ramdossSummary: Let \(G\) be a connected graph. The rainbow vertex connection number of \(G\) is the minimum number of colors necessary to color \(G\) such that for each pair of its vertices, there is a path connecting them whose internal vertices are assigned distinct colors. A dominator coloring of \(G\) is a proper coloring in which each vertex of \(G\) dominates every vertex of some color class. The dominator chromatic number is the minimum number of color classes in a dominator coloring. In this paper, we introduce a new vertex coloring parameter called rainbow dominator chromatic number and determine this parameter for some standard graphs.Vertex-disjoint rainbow cycles in edge-colored graphshttps://zbmath.org/1491.050842022-09-13T20:28:31.338867Z"Li, Luyi"https://zbmath.org/authors/?q=ai:li.luyi"Li, Xueliang"https://zbmath.org/authors/?q=ai:li.xueliangThe existence of cycles, e.g. Hamiltonian cycles or cycles of a fixed length, in graphs (and directed cycles in digraphs) is a well-studied topic, containing classic results such as Dirac's theorem. Related to this, one can also wonder about sufficient conditions for a coloured graph to have a rainbow cycle, i.e. a cycle whose vertices or edges all have different colours.
The authors of this paper consider a version of a problem in this direction.
Let \(G\) be an edge-colored graph of order \(n\). Then there exists a smallest function \(f(n)\) such that if every pair of vertices \((u,v)\) together see at least \(f(n)\) colours, i.e. the union of their color-neighborhood is at least \(f(n)\), then the graph \(G\) necessarily contains a rainbow cycle.
In this paper, it is proved that \(f(n) \le \lfloor \frac n2 \rfloor\). The analog of this problem where one is interested in having \(k\) vertex-disjoint rainbow cycles, is also considered.
Reviewer: Stijn Cambie (Nijmegen)Edge-disjoint rainbow triangles in edge-colored graphshttps://zbmath.org/1491.050852022-09-13T20:28:31.338867Z"Li, Luyi"https://zbmath.org/authors/?q=ai:li.luyi"Li, Xueliang"https://zbmath.org/authors/?q=ai:li.xueliangSummary: Let \(G\) be an edge-colored graph. A triangle of \(G\) is called rainbow if any two edges of the triangle have distinct colors. We use \(m(G)\) and \(c(G)\) to denote the number of edges of \(G\) and the number of colors appearing on the edges of \(G\), respectively. \textit{H. Yu} and \textit{B. Wu} [Discrete Math. 344, No. 9, Article ID 112519, 7 p. (2021; Zbl 1467.05141)] proved that every edge-colored graph of order \(n\) with \(m(G)+c(G)\geq n(n+1)/2\) contains a rainbow triangle and this result is best possible. \textit{S. Fujita} et al. [ibid. 342, No. 7, 1956--1965 (2019; Zbl 1414.05115)] characterized all graphs \(G\) satisfying \(m(G)+c(G)\geq n(n+1)/2-1\) but containing no rainbow triangle. In this paper, we conjecture that every edge-colored graph of order \(n\) with \(m(G)+c(G)\geq n(n+1)/2+3(k-1)\) contains \(k\) edge-disjoint rainbow triangles. We show that the conjecture holds for \(k=2\) and 3 and these results are best possible. Furthermore, we characterize all graphs \(G\) satisfying \(m(G)+c(G)\geq n(n+1)/2+2\) but not containing two edge-disjoint rainbow triangles. At the end, we propose a conjecture on the number of vertex-disjoint rainbow triangles in an edge-colored graph.Gallai-Ramsey numbers for rainbow \(S_3^+\) and monochromatic pathshttps://zbmath.org/1491.050862022-09-13T20:28:31.338867Z"Li, Xihe"https://zbmath.org/authors/?q=ai:li.xihe"Wang, Ligong"https://zbmath.org/authors/?q=ai:wang.ligongFor two finite simple graphs \(G\) and \(H\), the \(k\)-colored Gallai-Ramsey number for edge-colorings, denoted \(\operatorname{gr}_k(G : H)\), is defined to be the minimum positive integer \(n\) such that every \(k\)-coloring of the complete graph on \(n\) vertices contains either a rainbow copy of \(G\) (i.e., no two edges have the same color) or a monochromatic copy of \(H\) (i.e., all the edges have the same color). Let \(S_3^+\) be the graph on four vertices consisting of a triangle with a pendant edge.
In the paper under review, it is shown that \(\operatorname{gr}_k(S_3^+ : P_5) = k +4\) for \(k \geq 5\), where \(P_n\) is a path of length \(n\), \(\operatorname{gr}_k(S_3^+ : mP_2) = (m-1)k +m+1\) for \(k \geq 1\), where \(mP_n\) denotes the union of \(n\) disjoint copies of \(P_n\), \(\operatorname{gr}_k(S_3^+ : P_3 \cup P_2) = k + 4\) for \(k \geq 5\), and \(\operatorname{gr}_k(S_3^+ : 2P_3) = k + 5\) for \(k \geq 1\).
Reviewer: Lorenz Halbeisen (Bern)On the plane and its coloringhttps://zbmath.org/1491.050872022-09-13T20:28:31.338867Z"Parts, Jaan"https://zbmath.org/authors/?q=ai:parts.jaanSummary: We provide a human-verifiable proof that, in a certain sense, the chromatic number of the plane is exactly 7.The maximum size of an edge 2-neighborhood in \(P_5\)-free graphshttps://zbmath.org/1491.050882022-09-13T20:28:31.338867Z"Xu, Weilun"https://zbmath.org/authors/?q=ai:xu.weilun"Zhang, Xia"https://zbmath.org/authors/?q=ai:zhang.xiaSummary: For a graph \(G = (V, E)\) and an edge \(u v \in E(G)\), the 2-neighborhood of \(uv\) is the set of all edges having at least one endvertex in \(N(u) \cup N(v)\). A graph is called \(P_5\)-free if it contains no induced subgraphs isomorphic to a path with 5 vertices. For \(P_5\)-free graphs, we show that the maximum cardinality of an edge 2-neighborhood is at most \(\frac{ 5 \Delta^2}{ 4} \), where \(\Delta\) is the maximum degree of graphs. When \(\Delta\) is even, this bound is tight and confirms the strong edge coloring conjecture of Erdős and Nešetřil for \(P_5\)-free graphs.Tensor networks and the enumerative geometry of graphshttps://zbmath.org/1491.050892022-09-13T20:28:31.338867Z"Zograf, P. G."https://zbmath.org/authors/?q=ai:zograf.peterSummary: We propose a universal approach to a range of enumeration problems in graphs by means of tensor networks. The key point is in contracting suitably chosen symmetric tensors placed at the vertices of a graph along the edges. This approach leads to simple formulas that count, in particular, the number of \(d\)-regular subgraphs of an arbitrary graph (including the number of \(d\)-factors) and of proper edge colorings. We briefly discuss the computational complexity of the algorithms based on these formulas.Tournaments with maximal decomposabilityhttps://zbmath.org/1491.050902022-09-13T20:28:31.338867Z"Ben Salha, Cherifa"https://zbmath.org/authors/?q=ai:ben-salha.cherifaSummary: Given a tournament \(T\), a module of \(T\) is a subset \(M\) of \(V(T)\) such that for \(x, y \in M\) and \(v \in V(T) \setminus M\), \((x, v) \in A(T)\) if and only if \((y, v) \in A(T)\). The trivial modules of \(T\) are \(\emptyset, \{u \}\) (\(u \in V(T)\)) and \(V(T)\). The tournament \(T\) is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of \(T\), denoted by \(\delta(T)\), is the smallest number of arcs of \(T\) that must be reversed to make \(T\) indecomposable. In this paper, we characterize the tournaments \(T\) with \(\delta \)-maximal decomposability, i.e., such that \(\delta(T)\) is maximum among the tournaments with \(| V(T) |\) vertices.Some results on Berge's conjecture and begin-end conjecturehttps://zbmath.org/1491.050912022-09-13T20:28:31.338867Z"Bezerra Freitas, Lucas Ismaily"https://zbmath.org/authors/?q=ai:freitas.lucas-ismaily-bezerra"Lee, Orlando"https://zbmath.org/authors/?q=ai:lee.orlandoSummary: Let \(D\) be a digraph. A subset \(S\) of \(V(D)\) is stable if every pair of vertices in \(S\) is non-adjacent in \(D\). A collection of disjoint paths \(\mathcal{P}\) of \(D\) is a path partition of \(V(D)\), if every vertex in \(V(D)\) is on a path of \(\mathcal{P}\). We say that a stable set \(S\) and a path partition \(\mathcal{P}\) are orthogonal if every path of \(\mathcal{P}\) contains exactly one vertex of \(S\). A digraph \(D\) satisfies the \(\alpha\)-property if for every maximum stable set \(S\) of \(D\), there is a path partition \(\mathcal{P}\) orthogonal to \(S\). A digraph \(D\) is \(\alpha\)-diperfect if every induced subdigraph of \(D\) satisfies the \(\alpha\)-property. \textit{C. Berge} [Combinatorica 2, 213--222 (1982; Zbl 0511.05035)], Berge proposed a characterization of \(\alpha\)-diperfect digraphs in terms of forbidden anti-directed odd cycles. \textit{M. Sambinelli} et al. [Discrete Math. 345, No. 5, Article ID 112759, 12 p. (2022; Zbl 1484.05088)] proposed a similar conjecture. A digraph \(D\) satisfies the Begin-End-property or BE-property if for every maximum stable set \(S\) of \(D\), there is a path partition \(\mathcal{P}\) such that (i) \(S\) and \(\mathcal{P}\) are orthogonal and (ii) for each path \(P\in \mathcal{P}\), either the initial or the final of \(P\) lies in \(S\). A digraph \(D\) is BE-diperfect if every induced subdigraph of \(D\) satisfies the BE-property. Sambinelli et al. [loc. cit.] proposed a characterization of BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this paper, we show some structural results for \(\alpha\)-diperfect and BE-diperfect digraphs. In particular, we show that in every minimal counterexample \(D\) to both conjectures, it follows that \(\alpha (D) < \vert V(D)\vert /2\). Moreover, we prove both conjectures for arc-locally (out) in-semicomplete digraphs.Competitively orientable complete multipartite graphshttps://zbmath.org/1491.050922022-09-13T20:28:31.338867Z"Choi, Myungho"https://zbmath.org/authors/?q=ai:choi.myungho"Kwak, Minki"https://zbmath.org/authors/?q=ai:kwak.minki"Kim, Suh-Ryung"https://zbmath.org/authors/?q=ai:kim.suh-ryungSummary: We say that a digraph \(D\) is competitive if any pair of vertices has a common out-neighbor in \(D\) and that a graph \(G\) is competitively orientable if there exists a competitive orientation of \(G\). The competition graph of a digraph \(D\) is defined as the graph with the vertex set \(V(D)\) and an edge \(uv\) if and only if \(u\) and \(v\) compete in \(D\). The notion of competitive digraph arose while studying digraph whose competition graphs are complete. We derive some useful properties of competitively orientable graphs and show that a complete graph of order \(n\) is competitively orientable if and only if \(n \geq 7\). Then we completely characterize a competitively orientable complete multipartite graph in terms of the sizes of its partite sets. Moreover, we present a way to build a competitive multipartite tournament in each of competitively orientable cases.\( \chi \)-diperfect digraphshttps://zbmath.org/1491.050932022-09-13T20:28:31.338867Z"de Paula Silva, Caroline Aparecida"https://zbmath.org/authors/?q=ai:de-paula-silva.caroline-aparecida"Nunes da Silva, Cândida"https://zbmath.org/authors/?q=ai:da-silva.candida-nunes"Lee, Orlando"https://zbmath.org/authors/?q=ai:lee.orlandoSummary: Let \(D\) be a digraph. A coloring \(\mathcal{C}\) and a path \(P\) of \(D\) are orthogonal if \(P\) contains exactly one vertex of each color class in \(\mathcal{C} \). \textit{C. Berge} [Combinatorica 2, 213--222 (1982; Zbl 0511.05035)] defined the class of \(\chi \)-diperfect digraphs. A digraph \(D\) is \(\chi \)-diperfect if for every minimum coloring \(\mathcal{C}\) of \(D\), there exists a path \(P\) orthogonal to \(\mathcal{C}\) and this property holds for every induced subdigraph of \(D\). Berge showed that every symmetric digraph is \(\chi \)-diperfect, as well as every digraph whose underlying graph is perfect. However, he also showed that not every super-orientation of an odd cycle or complement of an odd cycle is \(\chi \)-diperfect. Non-\( \chi \)-diperfect super-orientations of odd cycles and their complements may play an important role in the characterization of \(\chi \)-diperfect digraphs, similarly to the role they play in the characterization of perfect graphs. In this paper, we present a characterization of super-orientations of odd cycles and a characterization of super-orientations of complements of odd cycles that are \(\chi \)-diperfect. Moreover, we show that certain classes of digraphs that are free of such non-\( \chi \)-diperfect structures are \(\chi \)-diperfect.Extremal digraphs avoiding distinct walks of length 3 with the same endpointshttps://zbmath.org/1491.050942022-09-13T20:28:31.338867Z"Huang, Zejun"https://zbmath.org/authors/?q=ai:huang.zejun"Lyu, Zhenhua"https://zbmath.org/authors/?q=ai:lyu.zhenhuaSummary: In this paper, we determine the maximum size of digraphs on \(n\) vertices which avoid two distinct walks of length 3 with the same initial vertex and the same terminal vertex. The digraphs attaining this maximum size are also characterized. Combining this with previous results, we obtain a full solution to a problem proposed by X. Zhan in 2007.Self-converse mixed graphs are extremely rarehttps://zbmath.org/1491.050952022-09-13T20:28:31.338867Z"Wissing, Pepijn"https://zbmath.org/authors/?q=ai:wissing.pepijnSummary: A mixed graph is cospectral to its converse, with respect to the usual adjacency matrices. Hence, it is easy to see that a mixed graph whose eigenvalues occur uniquely, up to isomorphism, must be isomorphic to its converse. It is therefore natural to ask whether or not this is a common phenomenon. This note contains the theoretical evidence to confirm that the fraction of self-converse mixed graphs tends to zero.Arc reversals of cycles in orientations of \(G\) vertex-multiplicationshttps://zbmath.org/1491.050962022-09-13T20:28:31.338867Z"Wong, H. W. Willie"https://zbmath.org/authors/?q=ai:wong.h-w-willie"Tay, E. G."https://zbmath.org/authors/?q=ai:tay.eng-guanSummary: \textit{H. J. Ryser} [in: Recent advances in matrix theory. Proceedings of an advanced seminar conducted by the Mathematics Research Center, United States Army, at the University of Wisconsin, Madison, October 14--16, 1963. Madison, WI: The University of Wisconsin Press. 103--124 (1964; Zbl 0129.00802)] proved that any two tournaments with the same score sequence are \(C_3\)-equivalent while \textit{L. W. Beineke} and \textit{J. W. Moon} [in: The theory and applications of graphs. Fourth international conference, May 6--9, 1980, Western Michigan University, Kalamazoo, Michigan. New York, NY etc.: John Wiley \& Sons 55--71 (1981; Zbl 0473.05031)] proved the \(C_4\)-equivalence for any two bipartite tournaments with the same score lists. In this paper, we extend these results to orientations of \(G\) vertex-multiplications. We focus on two main areas, namely orientations with the same score list and with score-list parity. Our main tools are extensions of the refinement technique, directed difference graph and a reduction lemma.On judicious bipartitions of directed graphshttps://zbmath.org/1491.050972022-09-13T20:28:31.338867Z"Wu, Shufei"https://zbmath.org/authors/?q=ai:wu.shufei"Hou, Jianfeng"https://zbmath.org/authors/?q=ai:hou.jianfengSummary: Let \(d \geq 4\) be an fixed integer. \textit{C. Lee} et al. [Random Struct. Algorithms 48, No. 1, 147--170 (2016; Zbl 1330.05078)] conjectured that every directed graph \(D\) with \(m\) arcs and minimum outdegree at least \(d\) admits a bipartition \(V(D) = V_1 \cup V_2\) such that
\[
\min \{e( V_1, V_2), e( V_2, V_1) \} \geq \left(\frac{ d - 1}{ 2 ( 2 d - 1 )} + o(1)\right) m,
\]
where \(e( V_i, V_j)\) denote the number of arcs in \(D\) from \(V_i\) to \(V_j\) for \(\{i, j \} = \{1, 2 \} \). Let \(\overrightarrow{K_{d , 2}}\) denote the directed graph obtained by orienting each edge of a bipartite graph \(K_{2 , d}\) from the part of size \(d\) to the other part. In this paper, we show that the conjecture holds for \(\overrightarrow{K_{d , 2}} \)-free directed graphs. Then, we prove that the conjecture holds under the additional condition that the minimum indegree is also at least \(d - 1\), which improves a result given by \textit{J. Hou} et al. [Sci. China, Math. 63, No. 2, 297--308 (2020; Zbl 1434.05063)].Induced signed graphs of some classes of graphshttps://zbmath.org/1491.050982022-09-13T20:28:31.338867Z"Aniyan, Achu"https://zbmath.org/authors/?q=ai:aniyan.achu"Naduvath, Sudev"https://zbmath.org/authors/?q=ai:naduvath.sudevA signed graph is a graph with positive and negative signs assigned to edges introduced by \textit{T. Zaslavsky} [Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)].
The induced signed graph concept was introduced by \textit{B. D. Acharya} [J. Comb. Inf. Syst. Sci. 37, No. 2--4, 145--167 (2012; Zbl 1301.05155)].
An induced signed graph is a signed graph constructed from a given graph according to some pre-defined protocols.
In this article, two types of signed graphs -- degree induced and eccentricity induced from given graph classes -- are studied for their characteristics, balance, clusterability, and many more. The study can be extended to many other graph classes. graph products and graph powers.
It is an interesting article and has wide approaches for signed graph researchers
Reviewer: V. Lokesha (Bangalore)An extension of the Lindström-Gessel-Viennot theoremhttps://zbmath.org/1491.050992022-09-13T20:28:31.338867Z"Lee, Yi-Lin"https://zbmath.org/authors/?q=ai:lee.yi-linSummary: Consider a weighted directed acyclic graph \(G\) having an upward planar drawing. We give a formula for the total weight of the families of non-intersecting paths on \(G\) with any given starting and ending points. While the Lindström-Gessel-Viennot theorem gives the signed enumeration of these weights (according to the connection type), our result provides the straight count, expressing it as a determinant whose entries are signed counts of lattice paths with given starting and ending points.Weyl orbits of matrix morsifications and a Coxeter spectral classification of positive signed graphs and quasi-Cartan matrices of Dynkin type \(\mathbb{A}_n\)https://zbmath.org/1491.051002022-09-13T20:28:31.338867Z"Simson, Daniel"https://zbmath.org/authors/?q=ai:simson.danielSummary: By applying an advanced technique of Weyl orbits of matrix morsifications of Dynkin graphs we obtain a complete classification (up to the strong Gram \(\mathbb{Z}\)-congruence) of the connected positive signed graphs \(\Delta\), with \(n \geq 2\) vertices, of Dynkin type \(\mathbb{A}_n\) (see Problem 2.1(a)), by a reduction of the problem to the combinatorial properties of the Weyl group of type \(\mathbb{A}_n\) and to the classification of the conjugacy classes of the integer orthogonal matrices \(C\) in \(\mathbb{M}_{n + 1}(\mathbb{Z})\) such that the characteristic polynomial of \(C\) is of the form \(\operatorname{char}_C(t) = t^{n + 1} - 1\). Following the usual Coxeter spectral analysis technique of edge-bipartite graphs applied in \textit{D. Simson} [Linear Algebra Appl. 557, 105--133 (2018; Zbl 1396.05049)], we study such positive signed graphs \(\Delta\), with \(n \geq 2\) vertices, by means of the non-symmetric Gram matrix \(\check{G}_{\Delta} \in \mathbb{M}_n(\mathbb{Z})\) defining \(\Delta\), its Gram quadratic form \(q_{\Delta} : \mathbb{Z}^n \to \mathbb{Z}\), \(v \mapsto v \cdot \check{G}_{\Delta} \cdot v^{t r}\), the complex spectrum \(\mathrm{specc}_{\Delta} \subset \mathcal{S}^1 : = \{z \in \mathbb{C}, | z | = 1 \}\) of the Coxeter matrix \(\mathrm{Cox}_{\Delta} : = - \check{G}_{\Delta} \cdot \check{G}_{\Delta}^{- t r} \in \mathbb{M}_n(\mathbb{Z})\), called the Coxeter spectrum of \(\Delta\), and the Coxeter polynomial \(\mathrm{cox}_{\Delta}(t) : = \det(t \cdot E - \mathrm{Cox}_{\Delta}) \in \mathbb{Z} [t]\). We define \(\Delta\) to be positive if the quadratic form \(q_{\Delta} : \mathbb{Z}^n \to \mathbb{Z}\) is positive definite, or equivalently the symmetric Gram matrix \(G_{\Delta} : = \frac{ 1}{ 2} [ \check{G}_{\Delta} + \check{G}_{\Delta}^{tr}] = E + \frac{ 1}{ 2} \operatorname{Ad}_{\Delta} \in \mathbb{M}_n(\frac{ 1}{ 2} \mathbb{Z})\) of \(\Delta\) is positive definite, where \(\operatorname{Ad}_{\Delta} \in \mathbb{M}_n(\mathbb{Z})\) is the adjacency matrix of \(\Delta\).
Here we classify such positive signed graphs, up to the strong Gram \(\mathbb{Z}\)-congruence \(\Delta \approx_{\mathbb{Z}} \Delta^\prime\), where \(\Delta \approx_{\mathbb{Z}} \Delta^\prime\) means that \(\check{G}_{\Delta^\prime} = B^{tr} \cdot \check{G}_{\Delta} \cdot B\), for some \(B \in \mathbb{M}_n(\mathbb{Z})\) with \(\det B = \pm 1\). The main result of the paper asserts that, given such a connected positive signed graph \(\Delta\) of Dynkin type \(\mathbb{A}_n\) (equivalently, \(\det 2 G_{\Delta} = n + 1)\), we have
\par (i) the Coxeter polynomial \(\mathrm{cox}_{\Delta}(t)\) has the form \(t^n + t^{n - 1} + \cdots + t + 1\) (i.e., it coincides with the Coxeter polynomial \(\mathrm{cox}_{\mathbb{A}_n}(t)\) of the Dynkin graph \(\mathbb{A}_n)\), and
\par (ii) there is a strong Gram \(\mathbb{Z}\)-congruence \(\Delta \approx_{\mathbb{Z}} \mathbb{A}_n\).
As a consequence we obtain the following solution of the Coxeter spectral hypothesis stated in [\textit{D. Simson}, SIAM J. Discrete Math. 27, No. 2, 827--854 (2013; Zbl 1272.05072); Linear Algebra Appl. 586, 190--238 (2020; Zbl 1429.05133)]:
\par (a) Given a pair \(\Delta\), \(\Delta^\prime\) of connected positive signed graphs of Dynkin type \(\mathbb{A}_n\), with \(n \geq 2\) vertices, there is a congruence \(\Delta \approx_{\mathbb{Z}} \Delta^\prime\) if and only if \(\mathbf{specc}_{\Delta} = \mathrm{specc}_{\Delta^\prime}\), and
\par (b) Given a positive definite connected quasi-Cartan matrix \(C \in \mathbb{M}_n(\mathbb{Z})\) (in the sense of [\textit{M. Barot} et al., J. Lond. Math. Soc., II. Ser. 73, No. 3, 545--564 (2006; Zbl 1093.05070)]) of Dynkin type \(\mathbb{A}_n\) (equivalently, \(\det C = n + 1)\), the Coxeter polynomial \(\mathrm{cox}_C(t) \in \mathbb{Z} [t]\) of \(C\) coincides with the Coxeter polynomial \(\mathrm{cox}_{\mathbb{A}_n}(t) = t^n + t^{n - 1} + \cdots + t + 1\) of the Dynkin graph \(\mathbb{A}_n\) and \(C\) is strongly \(\mathbb{Z}\)-congruent with the canonical symmetrizable Cartan matrix \(\mathbb{A}_n\) of the root system of type \(\mathbb{A}_n\).On the spectrum of Cayley graphshttps://zbmath.org/1491.051012022-09-13T20:28:31.338867Z"Ghorbani, M."https://zbmath.org/authors/?q=ai:ghorbani.modjtaba"Songhori, M."https://zbmath.org/authors/?q=ai:songhori.mahinSummary: The set of eigenvalues of the adjacency matrix of a graph is called the spectrum of it. In the present paper, we introduce the spectrum of Cayley graphs of order \(pqr\) in terms of character table, where \(p, q, r\) are prime numbers. We also, stablish some properties of Cayley graphs of non-abelian groups with a normal symmetric connected subset.Zero-divisor graphs and total coloring conjecturehttps://zbmath.org/1491.051022022-09-13T20:28:31.338867Z"Khandekar, Nilesh"https://zbmath.org/authors/?q=ai:khandekar.nilesh"Joshi, Vinayak"https://zbmath.org/authors/?q=ai:joshi.vinayak-vSummary: In this paper, we prove that the zero-divisor graphs of a special class of pseudocomplemented posets satisfy the total coloring conjecture. Also, we determine the edge chromatic number of the zero-divisor graphs of this special class of pseudocomplemented posets. These results are applied to zero-divisor graphs of finite reduced commutative rings.Generalized rainbow Turán problemshttps://zbmath.org/1491.051032022-09-13T20:28:31.338867Z"Gerbner, Dániel"https://zbmath.org/authors/?q=ai:gerbner.daniel"Mészáros, Tamás"https://zbmath.org/authors/?q=ai:meszaros.tamas"Methuku, Abhishek"https://zbmath.org/authors/?q=ai:methuku.abhishek"Palmer, Cory"https://zbmath.org/authors/?q=ai:palmer.cory-tSummary: \textit{N. Alon} and \textit{C. Shikhelman} [J. Comb. Theory, Ser. B 121, 146--172 (2016; Zbl 1348.05100)] initiated the systematic study of the following generalized Turán problem: for fixed graphs \(H\) and \(F\) and an integer \(n\), what is the maximum number of copies of \(H\) in an \(n\)-vertex F-free graph?
An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Turán number of \(F\) is defined as the maximum number of edges in a properly edge-colored graph on \(n\) vertices with no rainbow copy of \(F\). The study of rainbow Turán problems was initiated by \textit{P. Keevash} et al. [Comb. Probab. Comput. 16, No. 1, 109--126 (2007; Zbl 1119.05058)].
Motivated by the above problems, we study the following problem: What is the maximum number of copies of \(F\) in a properly edge-colored graph on \(n\) vertices without a rainbow copy of \(F\)? We establish several results, including when \(F\) is a path, cycle or tree.Turán number of disjoint triangles in 4-partite graphshttps://zbmath.org/1491.051042022-09-13T20:28:31.338867Z"Han, Jie"https://zbmath.org/authors/?q=ai:han.jie"Zhao, Yi"https://zbmath.org/authors/?q=ai:zhao.yiSummary: Let \(k\geqslant 2\) and \(n_1\geqslant n_2\geqslant n_3\geqslant n_4\) be integers such that \(n_4\) is sufficiently larger than \(k\). We determine the maximum number of edges of a 4-partite graph with parts of sizes \(n_1, \ldots, n_4\) that does not contain \(k\) vertex-disjoint triangles. For any \(r> t\geqslant 3\), we give a conjecture on the maximum number of edges of an \(r\)-partite graph that does not contain \(k\) vertex-disjoint cliques \(K_t\).On a colored Turán problem of Diwan and Mubayihttps://zbmath.org/1491.051052022-09-13T20:28:31.338867Z"Lamaison, Ander"https://zbmath.org/authors/?q=ai:lamaison.ander"Müyesser, Alp"https://zbmath.org/authors/?q=ai:muyesser.alp"Tait, Michael"https://zbmath.org/authors/?q=ai:tait.michaelSummary: Suppose that \(R\) (red) and \(B\) (blue) are two graphs on the same vertex set of size \(n\), and \(H\) is some graph with a red-blue coloring of its edges. How large can \(R\) and \(B\) be if \(R \cup B\) does not contain a copy of \(H\)? Call the largest such integer \(\operatorname{mex}(n, H)\). This problem was introduced by \textit{A. Diwan} and \textit{D. Mubayi} [``Turán's theorem with colors'', Preprint, \url{https://www.math.cmu.edu/~mubayi/papers/webturan.pdf}], who conjectured that (except for a few specific exceptions) when \(H\) is a complete graph on \(k + 1\) vertices with any coloring of its edges \(\operatorname{mex}(n, H) = \operatorname{ex}(n, K_{k + 1})\). This conjecture generalizes Turán's theorem.
Diwan and Mubayi also asked for an analogue of Erdős-Stone-Simonovits theorem in this context. We prove the following upper bound on the extremal threshold in terms of the chromatic number \(\chi(H)\) and the reduced maximum matching number \( \mathcal{M}(H)\) of \(H\).
\[
\operatorname{mex}(n, H) \leq \left( 1 - \frac{ 1}{ 2 ( \chi ( H ) - 1 )} - \frac{ \mathcal{M} ( H )}{ 9 \chi ( H )^2} \right) \frac{ n^2}{ 2}.
\]
\(\mathcal{M}(H)\) is, among the set of proper \(\chi(H)\)-colorings of \(H\), the largest set of disjoint pairs of color classes where each pair is connected by edges of just a single color. The result is also proved for more than 2 colors and is tight up to the implied constant factor. We also study \(\operatorname{mex}(n, H)\) when \(H\) is a cycle with a red-blue coloring of its edges, and we show that \(\operatorname{mex}(n, H) \lesssim \frac{ 1}{ 2} \binom{n}{2}\), which is tight.The number of maximal independent sets in trees with a given number of leaveshttps://zbmath.org/1491.051062022-09-13T20:28:31.338867Z"Taletskii, D. S."https://zbmath.org/authors/?q=ai:taletskii.dmitriy-s"Malyshev, D. S."https://zbmath.org/authors/?q=ai:malyshev.dmitrii-sergeevichSummary: For any \(n\) and \(l\), we completely describe trees with the maximum and minimum numbers of maximal independent sets among all \(n\)-vertex trees with \(l\) leaves.Generalized Turán number for linear forestshttps://zbmath.org/1491.051072022-09-13T20:28:31.338867Z"Zhu, Xiutao"https://zbmath.org/authors/?q=ai:zhu.xiutao"Chen, Yaojun"https://zbmath.org/authors/?q=ai:chen.yaojunSummary: The generalized Turán number \(\mathrm{ex}(n, K_s, H)\) is defined to be the maximum number of copies of a complete graph \(K_s\) in any \(H\)-free graph on \(n\) vertices. Let \(F\) be a linear forest consisting of \(k\) paths of orders \(\ell_1, \ell_2, \ldots, \ell_k\). By characterizing the structure of the \(F\)-free graph with large minimum degree, we determine the value of \(\mathrm{ex}(n, K_s, F)\) for \(n = \Omega ( | F |^s )\) and \(k \geq 2\) except some \(\ell_i = 3\), and the corresponding extremal graphs. Our result confirms a conjecture, due to \textit{L. T. Yuan} and \textit{X. D. Zhang} [``Turán numbers for disjoint paths'', J. Graph Theory 98, No. 3, 499--524 (2021; \url{doi:10.1002/jgt.22710})], on classical Turán number of any linear forest for \(n = \Omega ( | F |^2 )\) and each \(\ell_i \neq 3\), and improves some known results on classical Turán number of linear forest.Integral-root polynomials and chromatic uniqueness of graphshttps://zbmath.org/1491.051082022-09-13T20:28:31.338867Z"Al-Janabi, Haneen"https://zbmath.org/authors/?q=ai:al-janabi.haneen"Bacsó, Gábor"https://zbmath.org/authors/?q=ai:bacso.gaborThis paper presents results on chromatic polynomials. Of particular interest are conditions which imply chromatic uniqueness of graphs. Interestingly, the authors show that a graph whose chromatic polynomial has integral roots is chromatically unique if and only if exactly one of its roots has multiplicity two and the rest are simple. The basic tool is that of an \(r\)-clique join graph. For the proof, they compute the chromatic polynomial of successively more complicated graphs. Also, they construct graphs whose chromatic polynomials have roots forming arbitrary non-negative integer intervals. The reader should beware of numerous misprints and unclear statements.
Reviewer: Alberto Luis Delgado (Normal)Some remarks on the Zarankiewicz problemhttps://zbmath.org/1491.051092022-09-13T20:28:31.338867Z"Conlon, David"https://zbmath.org/authors/?q=ai:conlon.davidSummary: The Zarankiewicz problem asks for an estimate on \(z(m,n;s,t)\), the largest number of 1's in an \(m\times n\) matrix with all entries 0 or 1 containing no \(s\times t\) submatrix consisting entirely of 1's. We show that a classical upper bound for \(z(m, n; s, t)\) due to \textit{T. Kövári} et al. [Colloq. Math. 3, 50--57 (1954; Zbl 0055.00704)] is tight up to the constant for a broad range of parameters. The proof relies on a new quantitative variant of the random algebraic method.Some intriguing upper bounds for separating hash familieshttps://zbmath.org/1491.051102022-09-13T20:28:31.338867Z"Ge, Gennian"https://zbmath.org/authors/?q=ai:ge.gennian"Shangguan, Chong"https://zbmath.org/authors/?q=ai:shangguan.chong"Wang, Xin"https://zbmath.org/authors/?q=ai:wang.xin.2Summary: An \(N\times n\) matrix on \(q\) symbols is called \(\{w_1,\dots,w_t\}\)-separating if for arbitrary \(t\) pairwise disjoint column sets \(C_1,\dots,C_t\) with \(|C_i| = w_i\) for \(1 \leqslant i \leqslant t\), there exists a row \(f\) such that \(f(C_1),\dots, f(C_t)\) are also pairwise disjoint, where \(f(C_i)\) denotes the collection of components of \(C_i\) restricted to row \(f\). Given integers \(N\), \(q\) and \(w_1,\dots,w_t\), denote by \(C(N,q, \{w_1,\dots,w_t\})\) the maximal \(n\) such that a corresponding matrix does exist. The determination of \(C(N,q, \{w_1,\dots,w_t\})\) has received remarkable attention during the recent years. The main purpose of this paper is to introduce two novel methodologies to attack the upper bound of \(C(N,q, \{w_1,\dots,w_t\})\). The first one is a combination of the famous graph removal lemma in extremal graph theory and a Johnson-type recursive inequality in coding
theory, and the second one is the probabilistic method. As a consequence, we obtain several intriguing upper bounds for some parameters of \(C(N,q, \{w_1,\dots,w_t\})\), which significantly improve the previously known results.On the power of random greedy algorithmshttps://zbmath.org/1491.051112022-09-13T20:28:31.338867Z"Guo, He"https://zbmath.org/authors/?q=ai:guo.he"Warnke, Lutz"https://zbmath.org/authors/?q=ai:warnke.lutzSummary: In this paper we solve two problems of Esperet, Kang and Thomassé as well as Li concerning (i) induced bipartite subgraphs in triangle-free graphs and (ii) van der Waerden numbers. Each time random greedy algorithms allow us to go beyond the Lovász Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method.On trees and unicyclic graphs with equal forcing-type numbershttps://zbmath.org/1491.051122022-09-13T20:28:31.338867Z"Jiang, Hui"https://zbmath.org/authors/?q=ai:jiang.hui"Li, Wenjing"https://zbmath.org/authors/?q=ai:li.wenjing.1"Zhang, Jingshu"https://zbmath.org/authors/?q=ai:zhang.jingshuSummary: Zero-forcing is an iterative graph coloring process whereby a colored vertex with a single uncolored neighbor is colored. A vertex set \(S\) in a graph \(G\) is a forcing set if by iteratively applying the zero-forcing process, all vertices of \(V(G)\) become colored. If \(S\) has the added property that it induces an isolate-free subgraph, then \(S\) is a total forcing set of \(G\); while \(S\) is a connected forcing set of \(G\) if it induces a connected subgraph. Let \(F(G)\), \(F_t(G)\) and \(F_c(G)\) denote the forcing number, total forcing number, and connected forcing number of \(G\), i.e., the minimum cardinality taken over all forcing, total forcing, and connected forcing sets of \(G\), respectively. In this paper, we characterize trees and unicyclic graphs \(G\) with \(F(G)=F_t(G)\) and \(F_t(G)=F_c(G)\), respectively.On color isomorphic subdivisionshttps://zbmath.org/1491.051132022-09-13T20:28:31.338867Z"Xu, Zixiang"https://zbmath.org/authors/?q=ai:xu.zixiang"Ge, Gennian"https://zbmath.org/authors/?q=ai:ge.gennianFor \(k \geq 2\) and graph \(H\), let \(f_k(n,H)\) denote the smallest positive integer \(C\) such that there is a proper edge-coloring of the complete graph \(K_n\) with \(C\) colors containing no \(k\) vertex-disjoint color isomorphic copies of \(H\).
In this work, the authors study the growth rate of \(f_2(n,H_t)\), where \(H_t\) is the 1-subdivision of \(K_t\), \(t\geq 3\). Specifically, in the main result of the paper, they prove that
\[ f_2(n,H_t) = \Omega \Big(n^{1+\frac{1}{2t-3}}\Big).\]
The introduction of the function \(f_k(n,H)\) originated from the work of \textit{D. Conlon} and \textit{M. Tyomkyn} [SIAM J. Discrete Math. 35, No. 3, 2249--2264 (2021; Zbl 1478.05049)].
Reviewer: Italo Simonelli (Durham)Degree sums and spanning brooms of a graphhttps://zbmath.org/1491.051142022-09-13T20:28:31.338867Z"Wu, Yueyu"https://zbmath.org/authors/?q=ai:wu.yueyu"Zhang, Yunqing"https://zbmath.org/authors/?q=ai:zhang.yunqing"Chen, Yaojun"https://zbmath.org/authors/?q=ai:chen.yaojunSummary: A broom is a tree obtained by identifying an endpoint of a path with the center of a star. Let \(G\) be a connected graph of order \(n \geq 3\). \textit{G. Chen} et al. [J. Graph Theory 77, No. 3, 237--250 (2014; Zbl 1303.05027)] conjectured that if the degree sum is at least \(n - 2\) for any three pairwise nonadjacent vertices, then \(G\) contains a spanning broom. In this paper, we confirm the conjecture for \(n > 50\).The maximum average connectivity among all orientations of a graphhttps://zbmath.org/1491.051152022-09-13T20:28:31.338867Z"Casablanca, Rocío M."https://zbmath.org/authors/?q=ai:casablanca.rocio-m"Dankelmann, Peter"https://zbmath.org/authors/?q=ai:dankelmann.peter"Goddard, Wayne"https://zbmath.org/authors/?q=ai:goddard.wayne-d"Mol, Lucas"https://zbmath.org/authors/?q=ai:mol.lucas-a-s"Oellermann, Ortrud"https://zbmath.org/authors/?q=ai:oellermann.ortrud-rThis paper studies the maximum average connectivity among all orientations of a graph. The average connectivity of a directed graph \(D\) is denoted by \(\bar{k}(D)\), which is the average of the connectivity between two vertices over all such possible pairs in \(D\). The maximum average connectivity among all orientations of a given graph \(G\) is denoted by \(\bar{k}_{\max}(G)\). If a graph \(G\) is \(r\)-regular over \(n\) vertices for some odd \(r\), it is shown that \(\bar{k}_{\max}(G)\le\frac{r-1}{2}+\frac{n}{4(n-1)}\). If \(G\) is minimally 2-connected over \(n\) vertices, then \(1\le \bar{k}_{\max}(G)<5/4\). For each minimally 2-connected graph \(G\), it is shown that \(4/9<\bar{k}_{\max}(G)/\bar{k}(G)<5/8\). When \(G\) is a maximal outerplanar graph, it is shown that \(\bar{k}_{\max}(G)\le 3/2+(n-5)/(n^2-n)\).
Reviewer: Yilun Shang (Newcastle)5-shredders of contraction-critical 5-connected graphshttps://zbmath.org/1491.051162022-09-13T20:28:31.338867Z"Qin, Chengfu"https://zbmath.org/authors/?q=ai:qin.chengfu"Yang, Weihua"https://zbmath.org/authors/?q=ai:yang.weihuaSufficient conditions for a graph to have all \([a, b]\)-factors and \((a, b)\)-parity factorshttps://zbmath.org/1491.051172022-09-13T20:28:31.338867Z"Yang, Zixuan"https://zbmath.org/authors/?q=ai:yang.zixuan"Zhang, Xuechun"https://zbmath.org/authors/?q=ai:zhang.xuechun"Lu, Hongliang"https://zbmath.org/authors/?q=ai:lu.hongliang"Lin, Yuqing"https://zbmath.org/authors/?q=ai:lin.yuqingSummary: Let \(G\) be a graph with vertex set \(V\) and let \(b>a\) be two positive integers. We say that \(G\) has all \([a, b]\)-factors if \(G\) has an \(h\)-factor for every \(h: V\rightarrow{\mathbb{N}}\) such that \(a \le h(v) \le b\) for every \(v\in V\) and \(\sum_{v\in V}h(v)\equiv 0\pmod 2\). A spanning subgraph \(F\) of \(G\) is called an \((a, b)\)-parity factor, if \(d_F (v) \equiv a \equiv b \) (mod 2) and \(a \le d_F (v) \le b\) for all \(v \in V\). In this paper, we have developed sufficient conditions for the existence of all \([a, b]\)-factors and \((a, b)\)-parity factors of \(G\) in terms of the independence number and connectivity of \(G\). This work extended an earlier result of \textit{T. Nishimura} [J. Graph Theory 13, No. 1, 63--69 (1989; Zbl 0682.05053)]. Furthermore, we show that these results are best possible in some cases.Transformations of assembly number for 4-regular graphshttps://zbmath.org/1491.051182022-09-13T20:28:31.338867Z"Guterman, A. E."https://zbmath.org/authors/?q=ai:guterman.alexander-e"Kreines, E. M."https://zbmath.org/authors/?q=ai:kreines.elena-m"Ostroukhova, N. V."https://zbmath.org/authors/?q=ai:ostroukhova.n-vSummary: Simple assembly graphs characterize the process of DNA recombination in living cells. The assembly number, number of distinct Hamiltonian sets of polygonal paths, one-sided and middle additivity of a graph are important characteristics of such graphs. This paper investigates transformations of simple assembly graphs that allow one to increase their assembly numbers or to obtain middle additive graphs. Also the minimum number of loops that must be added to the edges of a tangled cord graph in order to increase its assembly number by 1 is computed.Hamilton cycles in line graphs of 3-hypergraphshttps://zbmath.org/1491.051192022-09-13T20:28:31.338867Z"Kaiser, Tomáš"https://zbmath.org/authors/?q=ai:kaiser.tomas"Vrána, Petr"https://zbmath.org/authors/?q=ai:vrana.petrThe authors prove that a 52-connected line graph of a rank 3 hypergraph is Hamiltonian.
Reviewer: Hang Lau (Montréal)A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphshttps://zbmath.org/1491.051202022-09-13T20:28:31.338867Z"Patel, Viresh"https://zbmath.org/authors/?q=ai:patel.viresh"Stroh, Fabian"https://zbmath.org/authors/?q=ai:stroh.fabianPowers of cycle graph which are \(k\)-self complementary and \(k\)-co-self complementaryhttps://zbmath.org/1491.051212022-09-13T20:28:31.338867Z"Bhat, K. Arathi"https://zbmath.org/authors/?q=ai:bhat.k-arathi"Sudhakara, G."https://zbmath.org/authors/?q=ai:sudhakara.gSummary: \textit{E. Sampathkumar} and \textit{L. Pushpalatha} [Graphs Comb. 14, No. 4, 377--392 (1998; Zbl 0914.05056)] introduced a generalized version of complement of a graph with respect to a given partition of its vertex set. Let \(G=(V,E)\) be a graph and \(P=\{V_1,V_,\dots,V_k\}\) be a partition of \(V\) of order \(k\geq 1\). The \(k\)-complement \(G^P_k\) of \(G\) with respect to \(P\) is defined as follows: For all \(V_i\) and \(V_j\) in \(P,i\neq j\), remove the edges between \(V_i\) and \(V_j\), and add the edges which are not in \(G\). Analogues to self complementary graphs, a graph \(G\) is \(k\)-self complementary (k-s.c.) if \(G^P_k \cong G\) and is \(k\)-co-self complementary (k-co.s.c.) if \(G^P_k \cong\overline{G}\) with respect to a partition \(P\) of \(V(G)\). The \(m^{th}\) power of an undirected graph \(G\), denoted by \(G^m\) is another graph that has the same set of vertices as that of \(G\), but in which two vertices are adjacent when their distance in \(G\) is at most \(m\).
In this article, we study powers of cycle graphs which are k-self complementary and \(k\)-co-self complementary with respect to a partition \(P\) of its vertex set and derive some interesting results. Also, we characterize \(k\)-self complementary \(C^2_n\) and the respective partition \(P\) of \(V (C^2_n)\). Finally, we prove that none of the \(C^2_n\) is \(k\)-co-self complementary for any partition \(P\) of \(V(C^2_n)\).Laplacian pretty good fractional revivalhttps://zbmath.org/1491.051222022-09-13T20:28:31.338867Z"Chan, Ada"https://zbmath.org/authors/?q=ai:chan.ada"Johnson, Bobae"https://zbmath.org/authors/?q=ai:johnson.bobae"Liu, Mengzhen"https://zbmath.org/authors/?q=ai:liu.mengzhen"Schmidt, Malena"https://zbmath.org/authors/?q=ai:schmidt.malena"Yin, Zhanghan"https://zbmath.org/authors/?q=ai:yin.zhanghan"Zhan, Hanmeng"https://zbmath.org/authors/?q=ai:zhan.hanmengSummary: We develop the theory of pretty good fractional revival in quantum walks on graphs using their Laplacian matrices as the Hamiltonian. We classify the paths and the double stars that have Laplacian pretty good fractional revival.Eigenvalues of graph Laplacians via rank-one perturbationshttps://zbmath.org/1491.051232022-09-13T20:28:31.338867Z"Klee, Steven"https://zbmath.org/authors/?q=ai:klee.steven"Stamps, Matthew T."https://zbmath.org/authors/?q=ai:stamps.matthew-tSummary: We show how the spectrum of a graph Laplacian changes with respect to a certain type of rank-one perturbation. We apply our finding to give new short proofs of the spectral version of Kirchhoff's Matrix Tree Theorem and known derivations for the characteristic polynomials of the Laplacians for several well-known families of graphs, including complete, complete multipartite, crown, and threshold graphs.Mixed graphs with smallest eigenvalue greater than \(- \frac{ \sqrt{ 5} + 1}{ 2} \)https://zbmath.org/1491.051242022-09-13T20:28:31.338867Z"Lu, Lu"https://zbmath.org/authors/?q=ai:lu.lu"Lou, Zhenzhen"https://zbmath.org/authors/?q=ai:lou.zhenzhen"Huang, Qiongxiang"https://zbmath.org/authors/?q=ai:huang.qiongxiangSummary: The classical problem of characterizing the graphs whose eigenvalues lie in a given interval may date back to the work of \textit{J. H. Smith} [in: Comb. Struct. Appl., Proc. Calgary Int. Conf. Comb. Struct. Appl., Calgary 1969, 403--406 (1970; Zbl 0249.05136)]. Especially, the research on graphs with smallest eigenvalues not less than \(-2\) has attracted widespread attention. Mixed graphs are natural generalizations of undirected graphs. In this paper, we completely characterize the mixed graphs with smallest Hermitian eigenvalue greater than \(- \frac{ \sqrt{ 5} + 1}{ 2} \). In fact, we found three infinite classes of mixed graphs and 30 scattered mixed graphs.New results on the minimum edge dominating energy of a graphhttps://zbmath.org/1491.051252022-09-13T20:28:31.338867Z"Movahedi, Fateme"https://zbmath.org/authors/?q=ai:movahedi.fateme"Akhbari, Mohammad Hadi"https://zbmath.org/authors/?q=ai:akhbari.mohammad-hadiSummary: Let \(G\) be a graph with \(n\) vertices and \(m\) edges. The minimum edge dominating energy is defined as the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of the graph \(G\). In this paper, some lower and upper bounds for the minimum edge dominating energy of the graph \(G\) are established.A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacianhttps://zbmath.org/1491.051262022-09-13T20:28:31.338867Z"Tudisco, Francesco"https://zbmath.org/authors/?q=ai:tudisco.francesco"Hein, Matthias"https://zbmath.org/authors/?q=ai:hein.matthiasSummary: We consider the nonlinear graph \(p\)-Laplacian and its set of eigenvalues and associated eigenfunctions of this operator defined by a variational principle. We prove a nodal domain theorem for the graph \(p\)-Laplacian for any \(p\geq1\). While for \(p>1\) the bounds on the number of weak and strong nodal domains are the same as for the linear graph Laplacian \((p=2)\), the behavior changes for \(p=1\). We show that the bounds are tight for \(p\geq1\) as the bounds are attained by the eigenfunctions of the graph \(p\)-Laplacian on two graphs. Finally, using the properties of the nodal domains, we prove a higher-order Cheeger inequality for the graph \(p\)-Laplacian for \(p>1\). If the eigenfunction associated to the \(k\)-th variational eigenvalue of the graph \(p\)-Laplacian has exactly \(k\) strong nodal domains, then the higher order Cheeger inequality becomes tight as \(p\to1\).Spectral determinations and eccentricity matrix of graphshttps://zbmath.org/1491.051272022-09-13T20:28:31.338867Z"Wang, Jianfeng"https://zbmath.org/authors/?q=ai:wang.jianfeng"Lu, Mei"https://zbmath.org/authors/?q=ai:lu.mei"Brunetti, Maurizio"https://zbmath.org/authors/?q=ai:brunetti.maurizio"Lu, Lu"https://zbmath.org/authors/?q=ai:lu.lu"Huang, Xueyi"https://zbmath.org/authors/?q=ai:huang.xueyiSummary: Let \(G\) be a connected graph on \(n\) vertices. For a vertex \(u \in G\), the eccentricity of \(u\) is defined as \(\varepsilon(u) = \max \{d(u, v) \mid v \in V(G)\}\), where \(d(u, v)\) denotes the distance between \(u\) and \(v\). The eccentricity matrix \(\mathcal{E}(G) = (\epsilon_{uv})\), where
\[
\epsilon_{u v} : =\begin{cases}
d(u, v) & \text{if } d(u, v) = \min \{\varepsilon (u), \varepsilon (v)\}, \\
0 & \text{otherwise,} \end{cases}
\] has been firstly introduced in Chemical Graph Theory. In literature, it is also known as the \(D_{\operatorname{MAX}}\)-matrix. Graphs with the diameter equal to the radius are called self-centered graphs. Two non-isomorphic graphs are said to be \(M\)-cospectral with respect to a given matrix \(M\) if they have the same \(M\)-eigenvalues. In this paper, we show that, when \(n \to \infty\), the fractions of non-isomorphic cospectral graphs with respect to the adjacency and the eccentricity matrix behave like those only concerning the self-centered graphs with diameter two. Secondly, we prove that a graph \(G\) has just two distinct \(\mathcal{E}\)-eigenvalues if and only if \(G\) is an \(r\)-antipodal graph. Thirdly, we obtain many pairs of \(\mathcal{E} \)-cospectral graphs by using strong and lexicographic products. Finally we formulate some problems waiting to be solved in order to build up a spectral theory based on the eccentricity matrix.Spectra of weighted uniform hypertreeshttps://zbmath.org/1491.051282022-09-13T20:28:31.338867Z"Wan, Jiang-Chao"https://zbmath.org/authors/?q=ai:wan.jiang-chao"Wang, Yi"https://zbmath.org/authors/?q=ai:wang.yi.9"Hu, Fu-Tao"https://zbmath.org/authors/?q=ai:hu.futaoSummary: Let \(T\) be a \(k\)-tree equipped with a weighting function \(\mathfrak{w}: V(T)\cup E(T) \rightarrow \mathbb{C}\), where \(k\geqslant 3\). The weighted matching polynomial of the weighted \(k\)-tree \((T, \mathfrak{w})\) is defined to be \[\mu(T, \mathfrak{w}, x) = \sum_{M \in \mathcal{M}(T)} (-1)^{|M|} \prod_{e \in E(M)} \mathfrak{w}(e)^k \prod_{v \in V(T)\backslash V(M)} (x-\mathfrak{w}(v)),\] where \(\mathcal{M}(T)\) denotes the set of matchings (including empty set) of \(T\). In this paper, we investigate the eigenvalues of the adjacency tensor \(\mathcal{A}(T, \mathfrak{w})\) of the weighted \(k\)-tree \((T, \mathfrak{w})\). The main result provides that \(\mathfrak{w}(v)\) is an eigenvalue of \(\mathcal{A}(T, \mathfrak{w})\) for every \(v\in V(T)\), and if \(\lambda\neq \mathfrak{w}(v)\) for every \(v\in V(T)\), then \(\lambda\) is an eigenvalue of \(\mathcal{A}(T, \mathfrak{w})\) if and only if there exists a subtree \(T^\prime\) of \(T\) such that \(\lambda\) is a root of \(\mu(T^\prime, \mathfrak{w}, x)\). Moreover, the spectral radius of \(\mathcal{A}(T, \mathfrak{w})\) is equal to the largest root of \(\mu(T, \mathfrak{w}, x)\) when \(\mathfrak{w}\) is real and nonnegative. The result extends a work by \textit{G. J. Clark} and \textit{J. N. Cooper} [Electron. J. Comb. 25, No. 2, Research Paper P2.48, 8 p. (2018; Zbl 1391.15082)] to weighted \(k\)-trees. As applications, two analogues of the above work for the Laplacian and the signless Laplacian tensors of \(k\)-trees are obtained.Relation between the nullity of a graph and its matching numberhttps://zbmath.org/1491.051292022-09-13T20:28:31.338867Z"Zhou, Qi"https://zbmath.org/authors/?q=ai:zhou.qi.1"Wong, Dein"https://zbmath.org/authors/?q=ai:wong.dein"Tian, Fenglei"https://zbmath.org/authors/?q=ai:tian.fengleiLet \(G\) be a connected graph of order \(n(G)\) and size \(e(G)\). The nullity of \(G\), denoted by \(\eta(G)\), is the multiplicity of eigenvalue zero of the adjacency matrix of \(G\). \textit{L. Wang} and \textit{D. Wong} [ibid. 166, 276--281 (2014; Zbl 1283.05226)] bounded \(\eta(G)\) as \[ n(G)-2m(G)-c(G) \le\eta(G) \le n(G)-2m(G) + 2c(G), \] where \(m(G)\) is the matching number of \(G\) and \(c(G)\), defined by \(c(G) = e(G)-n(G) + 1\), is the dimension of cycle space of \(G\). The authors found that the upper and the lower bounds for \(\eta(G)\) both fail to accurate if the edges in \(G\) are dense, namely if \(c(G)\) is large enough. In this paper, the authors improved the above bounds. They proved that \[ n(G)-2m(G)-\sigma(G) \le \eta(G)\le n(G)-2m(G) + 2\omega(G), \] where \(\sigma(G)\) is the largest number of disjoint odd cycles in \(G\) and \(\omega(G)\) is the number of even cycles in \(G\). The cycle-disjoint connected graphs with nullity \(n(G)-2m(G)-\sigma(G)\) were also characterized.
Reviewer: Xiaogang Liu (Xi'an)On the Ramsey numbers of odd-linked double starshttps://zbmath.org/1491.051302022-09-13T20:28:31.338867Z"Karamchedu, Chaitanya D."https://zbmath.org/authors/?q=ai:karamchedu.chaitanya-d"Klawe, Maria M."https://zbmath.org/authors/?q=ai:klawe.maria-margaretSummary: The linked double star \(S_c(n, m)\), where \(n \geq m \geq 0\), is the graph consisting of the union of two stars \(K_{1 , n}\) and \(K_{1 , m}\) with a path on \(c\) vertices joining the centers. Its Ramsey number \(r( S_c(n, m))\) is the smallest integer \(r\) such that every 2-coloring of the edges of a \(K_r\) admits a monochromatic \(S_c(n, m)\). In this paper, we study the Ramsey numbers of linked double stars when \(c\) is odd. In particular, we establish bounds on the value of \(r( S_c(n, m))\) and determine the exact value of \(r( S_c(n, m))\) if \(n \geq c\), or if \(n \leq \lfloor \frac{ c}{ 2} \rfloor - 2\) and \(m = 2\).On Ramsey numbers for arbitrary sequences of graphshttps://zbmath.org/1491.051312022-09-13T20:28:31.338867Z"Karas, V. S."https://zbmath.org/authors/?q=ai:karas.v-s"Raigorodskii, A. M."https://zbmath.org/authors/?q=ai:raigorodskii.andrei-mSummary: In this work, we study nontrivial generalizations of Ramsey numbers to the case of arbitrary sequences of graphs. For many classes of sequences, exact values or asymptotics of Ramsey numbers are found.Ramsey numbers of several \(K_{t,s}\) and a large \(K_{m,n}\)https://zbmath.org/1491.051322022-09-13T20:28:31.338867Z"Wang, Ye"https://zbmath.org/authors/?q=ai:wang.ye"Li, Yusheng"https://zbmath.org/authors/?q=ai:li.yusheng"Li, Yan"https://zbmath.org/authors/?q=ai:li.yan.9|li.yan.6|li.yan.8|li.yan.3|li.yan|li.yan.1|li.yan.5|li.yan.2|li.yan.7|li.yan.10|li.yan.4Summary: For graphs \(G\) and \(H\), denote by \(r_{k + 1}(G; H)\) the minimum \(N\) such that any edge-coloring of \(K_N\) by \(k + 1\) colors contains either a monochromatic \(G\) in the first \(k\) colors or a monochromatic \(H\) in the last color. As usual, we write \(r_2(G; H)\) as \(r(G, H)\). We show that if integers \(s \geq t \geq m \geq 1\), then \(r_{k + 1}( K_{t , s}; K_{m , n}) \leq n +(1 + o(1)) ( s - t + 1 )^{1 / t} k m n^{1 - 1 / t}\) as \(n \to \infty \). The upper bound is shown to be sharp up to the asymptotical sub-linear term for \(r_{k + 1}( K_{2 , s}; K_{1 , n}), r_{k + 1}( K_{3 , 3}; K_{1 , n}), r( K_{2 , s}, K_{2 , n})\) and \(r( K_{3 , 3}, K_{m , n})\) for \(m \leq 3\).Simplicial dollar gamehttps://zbmath.org/1491.051332022-09-13T20:28:31.338867Z"Kim, Jesse"https://zbmath.org/authors/?q=ai:kim.jesse"Perkinson, David"https://zbmath.org/authors/?q=ai:perkinson.davidSummary: The dollar game is a chip-firing game introduced in [\textit{M. Baker} and \textit{S. Norine}, Adv. Math. 215, No. 2, 766--788 (2007; Zbl 1124.05049)] as a context in which to formulate and prove the Riemann-Roch theorem for graphs. A divisor on a graph is a formal integer sum of vertices. Each determines a dollar game, the goal of which is to transform the given divisor into one that is effective (nonnegative) using chip-firing moves. We use Duval, Klivans, and Martin's theory of chip-firing on simplicial complexes to generalize the dollar game and results related to the Riemann-Roch theorem for graphs to higher dimensions. In particular, we extend the notion of the degree of a divisor on a graph to a (multi)degree of a chain on a simplicial complex and use it to establish two main results. The first of these generalizes the fact that if a divisor on a graph has large enough degree (at least as large as the genus of the graph), it is winnable; and the second generalizes the fact that trees (graphs of genus \(0)\) are exactly the graphs on which every divisor of degree \(0\), interpreted as an instance of the dollar game, is winnable.Computability and the game of cops and robbers on graphshttps://zbmath.org/1491.051342022-09-13T20:28:31.338867Z"Stahl, Rachel D."https://zbmath.org/authors/?q=ai:stahl.rachel-dSummary: Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \(\alpha \), any winning strategy has complexity at least \(0^{(\alpha )}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and graphs are explored. The Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed.\(Z\)-oriented triangulations of surfaceshttps://zbmath.org/1491.051352022-09-13T20:28:31.338867Z"Tyc, Adam"https://zbmath.org/authors/?q=ai:tyc.adamSummary: The main objects of the paper are \(z\)-oriented triangulations of connected closed 2-dimensional surfaces. A \(z\)-orientation of a map is a minimal collection of zigzags which double covers the set of edges. We have two possibilities for an edge -- zigzags from the \(z\)-orientation pass through this edge in different directions (type I) or in the same direction (type II). Then there are two types of faces in a triangulation: the first type is when two edges of the face are of type I and one edge is of type II and the second type is when all edges of the face are of type II. We investigate \(z\)-oriented triangulations with all faces of the first type (in the general case, any \(z\)-oriented triangulation can be shredded to a \(z\)-oriented triangulation of such type). A zigzag is homogeneous if it contains precisely two edges of type I after any edge of type II. We give a topological characterization of the homogeneity of zigzags; in particular, we describe a one-to-one correspondence between \(z\)-oriented triangulations with homogeneous zigzags and closed 2-cell embeddings of directed Eulerian graphs in surfaces. At the end, we give an application to one type of the \(z\)-monodromy.The poset of morphism-extension classes of countable graphshttps://zbmath.org/1491.051362022-09-13T20:28:31.338867Z"Aranda, Andrés"https://zbmath.org/authors/?q=ai:aranda.andresSummary: Let \(\mathrm{XY}_{L,T}\) consist of all countable \(L\)-structures \(M\) that satisfy the axioms \(T\) and in which all homomorphisms of type X (these could be plain homomorphisms, monomorphisms, or isomorphisms) between finite substructures of \(M\) are restrictions of an endomorphism of \(M\) of type Y (for example, an automorphism or a surjective endomorphism). Lockett and Truss introduced 18 such classes for relational structures. For a given pair \(L, T\) however, two or more morphism-extension properties may define the same class of structures.
In this paper, we establish all equalities and inequalities between morphism-extension classes of countable graphs.Maximum number of almost similar triangles in the planehttps://zbmath.org/1491.051372022-09-13T20:28:31.338867Z"Balogh, József"https://zbmath.org/authors/?q=ai:balogh.jozsef"Clemen, Felix Christian"https://zbmath.org/authors/?q=ai:clemen.felix-christian"Lidický, Bernard"https://zbmath.org/authors/?q=ai:lidicky.bernardSummary: A triangle \(T^\prime\) is \(\varepsilon\)-similar to another triangle \(T\) if their angles pairwise differ by at most \(\varepsilon\). Given a triangle \(T,\varepsilon > 0\) and \(n\in\mathbb{N}\), Bárány and Füredi asked to determine the maximum number of triangles \(h(n,T,\varepsilon)\) being \(\varepsilon\)-similar to \(T\) in a planar point set of size \(n\). We show that for almost all triangles \(T\) there exists \(\varepsilon=\varepsilon(T) > 0\) such that \(h(n,T,\varepsilon)=(1+o(1))n^3/24\). Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof.The existence of uniform hypergraphs for which the interpolation property of complete coloring failshttps://zbmath.org/1491.051382022-09-13T20:28:31.338867Z"Haghparast, Nastaran"https://zbmath.org/authors/?q=ai:haghparast.nastaran"Hasanvand, Morteza"https://zbmath.org/authors/?q=ai:hasanvand.morteza"Ohno, Yumiko"https://zbmath.org/authors/?q=ai:ohno.yumikoThe authors study the so-called interpolation property for uniform hypergraphs, which concerns complete (vertex) colorings of uniform hypergraphs. The main result of the paper states that for any \(k \geq 3\), there exist \(k\)-uniform hypergraphs that do not have the interpolation property in a strong sense (defined below).
A \(k\)-uniform hypergraph \(H\) is a hypergraph whose edges all have cardinality \(k\). A \(t\)-coloring of a hypergraph \(H\) is an assignment of colors to the vertices of \(H\), where the colors come from a collection of \(t\) colors. A coloring is proper if any two vertices that are in an edge receive distinct colors. The chromatic number of \(H\), denoted by \(\chi(H)\), is the minimum number of colors needed to properly color \(H\). A coloring of a \(k\)-uniform hypergraph \(H\) is complete if is proper and every subset of \(k\)-colors appears on at least one edge of \(H\). The achromatic number of \(H\), denoted by \(\psi(H)\) is the largest integer \(t\) such that there is a complete \(t\)-coloring of \(H\).
It is known that every graph \(G\) has a complete coloring. A result of \textit{F. Harary} et al. [Port. Math. 26, 453--462 (1967; Zbl 0187.20903)] states that that if \(G\) is a graph, then \(G\) admits a \(t\)-coloring for every \(t\) such that \(\chi(G) \leq t \leq \psi(G)\). In other words, every graph has the interpolation property. On the other hand, \textit{K. Edwards} and \textit{P. Rzążewski} [Discrete Math. 343, No. 2, Article ID 111673, 12 p. (2020; Zbl 1429.05065)] showed that, for all \(k \geq 9\), there exist hypergraphs \(H\) which have complete \(\chi(H)\)-coloring and \(\psi(H)\)-colorings, but no complete \(t\)-coloring for some \(\chi(H) \leq t \leq \psi(H)\).
The authors strengthen the result of Edwards and Rzążewski [loc. cit.], and show that for any \(k \geq 3\), there exist hypergraphs \(H\) which have complete \(\chi(H)\)-coloring and \(\psi(H)\)-colorings, but no complete \(t\)-coloring for any \(\chi(H) \leq t \leq \psi(H)\).
Reviewer: Abdul Basit (Notre Dame)Coloring intersection hypergraphs of pseudo-diskshttps://zbmath.org/1491.051392022-09-13T20:28:31.338867Z"Keszegh, Balázs"https://zbmath.org/authors/?q=ai:keszegh.balazsSummary: We prove that the intersection hypergraph of a family of \(n\) pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with 4 colors and a conflict-free coloring with \(O(\log n)\) colors. Along the way we prove that the respective Delaunay-graph is planar. We also prove that the intersection hypergraph of a family of \(n\) regions with linear union complexity with respect to a family of pseudo-disks admits a proper coloring with constantly many colors and a conflict-free coloring with \(O(\log n)\) colors. Our results serve as a common generalization and strengthening of many earlier results, including ones about proper and conflict-free coloring points with respect to pseudo-disks, coloring regions of linear union complexity with respect to points and coloring disks with respect to disks.
For the entire collection see [Zbl 1390.68027].Further progress on the total Roman \(\{2\}\)-domination number of graphshttps://zbmath.org/1491.051402022-09-13T20:28:31.338867Z"Abdollahzadeh Ahangar, Hossein"https://zbmath.org/authors/?q=ai:ahangar.hossein-abdollahzadeh"Chellali, Mustapha"https://zbmath.org/authors/?q=ai:chellali.mustapha.1"Hajjari, Maryam"https://zbmath.org/authors/?q=ai:hajjari.maryam"Sheikholeslami, Seyed Mahmoud"https://zbmath.org/authors/?q=ai:sheikholeslami.seyed-mahmoudSummary: For a graph \(\Gamma \), let \(\gamma (\Gamma)\), \(\gamma_t(\Gamma)\), and \(\gamma_{tR2}(\Gamma)\) denote the domination number, the total domination number, and the total Roman \(\{2\}\)-domination number, respectively. It was shown in [the first author et al., Discuss. Math., Graph Theory 42, No. 3, 937--958 (2022; Zbl 07551398)] that for each nontrivial connected graph \(\Gamma\), \(\gamma_t(\Gamma)\leq \gamma_{tR2}(\Gamma)\leq 3\gamma (\Gamma)\). The problem that arises naturally is to characterize the graphs attaining each bound. For the left inequality, we establish a necessary and sufficient condition for nontrivial connected graphs \(\Gamma\) with \(\gamma_{tR2} (\Gamma)=\gamma_t(\Gamma)\), and we characterize those graphs that are \(\{C_3,C_6\}\)-free or block. For the right inequality, we present a necessary condition for nontrivial connected graphs \(\Gamma\) with \(\gamma_{tR2}(\Gamma)=3\gamma (\Gamma)\), and we characterize those graphs that are diameter-2 or trees.On the domination polynomial of a digraph: a generation function approachhttps://zbmath.org/1491.051412022-09-13T20:28:31.338867Z"Alencar, Jorge"https://zbmath.org/authors/?q=ai:alencar.jorge"de Lima, Leonardo"https://zbmath.org/authors/?q=ai:de-lima.leonardo-sIn the present paper, the authors consider different versions of the domination polynomial in directed graphs (also called digraphs). To present the results, several definitions are needed.
Let \(G=(V(G),E(G))\) be a digraph with vertex set \(V(G)\) and arc set \(E(G)\). Every element of \(E(G)\) is a directed arc and if \((u,v) \in E(G)\), then we say that \(u\) dominates \(v\) or that \(v\) is dominated by \(u\). A subset \(S \subseteq V(G)\) is
\par i) an in-dominating set of \(G\) if every vertex in \(V(G) \setminus S\) dominates at least one vertex in \(S\);
\par ii) an out-dominating set of \(G\) if every vertex in \(V(G) \setminus S\) is dominated by at least one vertex in \(S\);
\par iii) a total in-dominating set of \(G\) if every vertex in \(V(G)\) dominates at least one vertex in \(S\);
\par iv) a total out-dominating set of \(G\) if every vertex in \(V(G)\) is dominated by at least one vertex in \(S\).
The in-domination number \(\gamma^- (G)\), the out-domination number \(\gamma^+ (G)\), the total in-domination number \(\gamma_t^- (G)\), and the total out-domination number \(\gamma_t^+ (G)\) of a graph \(G\) are defined as the minimum cardinality of an in-dominating set, an out-dominating set, a total in-dominating set, and a total out-dominating set, respectively.
Moreover, let \(d^-(G,i)\), \(d^+(G,i)\), \(d_t^-(G,i)\), and \(d_t^+(G,i)\) represent the numbers of in-dominating sets with \(i\) vertices, out-dominating sets with \(i\) vertices, total in-dominating sets with \(i\) vertices, and total out-dominating sets with \(i\) vertices, respectively.
Finally, the in-domination polynomial \(D^- (G,x)\), the out-domination polynomial \(D^+(G,x)\), the total in-domination polynomial \(D_t^-(G,x)\), and the total out-domination polynomial \(D_t^+(G,x)\) of a graph \(G\) with \(n\) vertices are defined as:
\[D^-(G,x) = \sum_{i=\gamma^- (G)}^{n} d^-(G,i)x^i,\quad D^+(G,x) = \sum_{i=\gamma^+ (G)}^{n} d^+(G,i)x^i,\] \[D_t^-(G,x) = \sum_{i=\gamma_t^- (G)}^{n} d_t^-(G,i)x^i, \quad D_t^+(G,x) = \sum_{i=\gamma_t^+ (G)}^{n} d_t^+(G,i)x^i.\]
If \(G\) is an undirected graph, we define in a similar way also the domination polynomial \(D(G,x)\) and the total domination polynomial \(D_t(G,x)\).
As the main result of the paper, it is proved that in-domination and out-domination polynomials of digraphs can be obtained by using an ordinary generating function. Moreover, some examples are considered to show how this generating function approach can be used to obtain the domination polynomials for graphs and digraphs.
In the last section, the Minimum-Weighted Dominating Set problem is studied. Let \(G=(V(G), E(G), w)\) be an undirected graph where \(w: V(G) \rightarrow \mathbb{R}^+\) is a weight on vertices. The aim of the mentioned problem is to find the dominating set with the smallest weight, i.e. to find the dominating set for which the sum of the weights of vertices from the set is the smallest possible. It is shown in the paper how the presented generating function approach can be applied to the Minimum-Weighted Dominating Set problem.
Reviewer: Niko Tratnik (Maribor)On the unimodality of domination polynomialshttps://zbmath.org/1491.051422022-09-13T20:28:31.338867Z"Beaton, Iain"https://zbmath.org/authors/?q=ai:beaton.iain"Brown, Jason I."https://zbmath.org/authors/?q=ai:brown.jason-iLet \(G\) be a graph of order \(n\). A subset \(S\) of \(V(G)\) is a dominating set of \(G\) if every vertex in \(V(G) \backslash S\) is adjacent to at least one vertex of \(S\). The domination polynomial of \(G\) is the polynomial \(D(G, x) = \sum^n_{i=\gamma(G)} d(G, i)x^i\), where \(d(G, i)\) is the number of dominating sets of \(G\) of size \(i\), and \(\gamma(G)\) is the size of a smallest dominating set of \(G\), called the domination number of \(G\).
A finite sequence of real numbers \((a_0, a_1, a_2, \ldots, a_n)\) is said to be unimodal (with mode \(k\)) if \(a_0\le a_1 \le \cdots \le a_{k-1} \le a_k \ge a_{k+1} \ge \cdots \ge a_n\) for some \(k\in \{0,1,2,\ldots,n\}\); and is logarithmically-concave (or simply log-concave) if the inequality \(a^2_k \ge a_{k-1} a_{k+1}\) is valid for every \(k\in \{1,2,\ldots,n-1\}\). Hence, a polynomial \(\sum^n_{k=0} a_kx^k\) is said to be unimodal (or log-concave) if the coefficient sequence \(\{a_k\}\) is unimodal (or log-concave).
Motivated by a conjecture by \textit{S. Alikhani} and \textit{Y.-h. Peng} [Opusc. Math. 30, No. 1, 37--51 (2010; Zbl 1220.05084)] which states that the domination polynomial of any graph is unimodal, the authors have shown that the domination polynomial of paths, cycles, and complete multipartite graphs are unimodal. Also, they proved that the domination polynomial of almost every graph is unimodal with mode \(\lceil\frac{n}{2}\rceil\).
Reviewer: Saeid Alikhani (Yazd)Double Roman domination in generalized Petersen graphshttps://zbmath.org/1491.051432022-09-13T20:28:31.338867Z"Gao, Hong"https://zbmath.org/authors/?q=ai:gao.hong"Huang, Jiahuan"https://zbmath.org/authors/?q=ai:huang.jiahuan"Yang, Yuansheng"https://zbmath.org/authors/?q=ai:yang.yuansheng.2|yang.yuansheng.1Summary: The double Roman domination can be described as a strengthened defense strategy. In an empire, each city can be protected by at most three troops. Every city having no troops must be adjacent to at least two cities with two troops or one city with three troops. Every city having one troop must be adjacent to at least one city with more than one troop. Such an assignment is called a double Roman dominating function (DRDF) of an empire/a graph. The minimum number of troops under such an assignment is the double Roman domination number, denoted as \(\gamma_{dR}\). \textit{Z. Shao} et al. [``Discharging approach for double Roman domination in graphs'', IEEE Access 6, 63345--63351 (2018; \url{doi:10.1109/ACCESS.2018.2876460})] determine the exact value of \(\gamma_{dR}(P(n,1))\). \textit{H. Jiang} et al. [``The double Roman domination numbers of generalized Petersen graphs \(P(n, 2)\)'', Mathematics 6, No. 10, Paper No. 206, 11 p. (2018; \url{doi:10.3390/math6100206})] determine \(\gamma_{dR}(P(n,2))\). In this article, we investigate the double Roman domination number of \(P(n, k)\) for \(k\ge 3\). We determine the exact value of \(\gamma_{dR}(P(n,k))\) for \(n\equiv 0(\bmod 4)\) and \(k\equiv 1(\bmod 2)\), and present an improved upper bound of \(\gamma_{dR}(P(n,k))\) for \(n\not \equiv 0(\bmod 4)\) or \(k\not \equiv 1(\bmod 2)\). Our results imply \(P(n, 3)\) for \(n\equiv 0(\bmod 4)\) is double Roman which can partially answer the open question present by \textit{R. A. Beeler} et al. [Discrete Appl. Math. 211, 23--29 (2016; Zbl 1348.05146)].A note on exact minimum degree threshold for fractional perfect matchingshttps://zbmath.org/1491.051442022-09-13T20:28:31.338867Z"Lu, Hongliang"https://zbmath.org/authors/?q=ai:lu.hongliang"Yu, Xingxing"https://zbmath.org/authors/?q=ai:yu.xingxingA \(k\)-uniform hypergraph \(H\) or simply a \(k\)-graph is a generalization of a graph in which each hyperedge is a subset of \(V(H)\) of cardinality \(k\).
A fractional matching in a hypergraph \(H\) is a function that assigns a fraction in \([0,1]\) to each hyperedge, such that for every vertex \(v \in V(H)\), the sum of fractions of hyperedges containing \(v\) is at most 1.
The size of a fractional matching is the sum of fractions of all hyperedges. The fractional matching number of a hypergraph \(H\) is the largest size of a fractional matching in \(H\).
For integers \(n\), \(k\), \(d\) and positive rational number \(s\) satisfying \(0\leq d\leq k-1\) and \(s\leq n\slash k\), let \(f_d^{s}(k,n)\) denote the minimum integer \(m\) such that every \(k\)-graph \(H\) on \(n\) vertices with the minimum \(d\)-degree greater or equal to \(m \) has a fractional matching of size \(s\).
In this note, based on the results of \textit{P. Frankl} and \textit{A. Kupavskii} [``The Erdős matching conjecture and concentration inequalities'', Preprint, \url{arXiv:1806.08855}], the exact value of \(f_d^{n\slash k}(k,n)\) for certain ranges of \(d\) is determined.
Reviewer: Petra Žigert Pleteršek (Maribor)Note on the number of balanced independent sets in the Hamming cubehttps://zbmath.org/1491.051452022-09-13T20:28:31.338867Z"Park, Jinyoung"https://zbmath.org/authors/?q=ai:park.jinyoungSummary: Let \(Q_d\) be the \(d\)-dimensional Hamming cube and \(N=|V(Q_d)|=2^d\). An independent set \(I\) in \(Q_d\) is called balanced if \(I\) contains the same number of even and odd vertices. We show that the logarithm of the number of balanced independent sets in \(Q_d\) is \[(1-\Theta(1/\sqrt{d}))N/2.\] The key ingredient of the proof is an improved version of ``Sapozhenko's graph container lemma''.Well-partitioned chordal graphshttps://zbmath.org/1491.051462022-09-13T20:28:31.338867Z"Ahn, Jungho"https://zbmath.org/authors/?q=ai:ahn.jungho"Jaffke, Lars"https://zbmath.org/authors/?q=ai:jaffke.lars"Kwon, O-joung"https://zbmath.org/authors/?q=ai:kwon.ojoung"Lima, Paloma T."https://zbmath.org/authors/?q=ai:lima.paloma-tSummary: We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call well-partitioned chordal graphs. A connected graph \(G\) is a well-partitioned chordal graph if there exist a partition \(\mathcal{P}\) of the vertex set of \(G\) into cliques and a tree \(\mathcal{T}\) having \(\mathcal{P}\) as a vertex set such that for distinct \(X, Y \in \mathcal{P} \), (1) the edges between \(X\) and \(Y\) in \(G\) form a complete bipartite subgraph whose parts are some subsets of \(X\) and \(Y\), if \(X\) and \(Y\) are adjacent in \(\mathcal{T} \), and (2) there are no edges between \(X\) and \(Y\) in \(G\) otherwise. A split graph with vertex partition \((C, I)\) where \(C\) is a clique and \(I\) is an independent set is a well-partitioned chordal graph as witnessed by a star \(\mathcal{T}\) having \(C\) as the center and each vertex in \(I\) as a leaf, viewed as a clique of size 1. We characterize well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given a graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal.
We observe that there are problems, for instance \textsc{Densest} \(k\)-\textsc{Subgraph} and \(b\)-\textsc{Coloring}, that are polynomial-time solvable on split graphs but become NP-hard on well-partitioned chordal graphs. On the other hand, we show that the Geodetic Set problem, known to be NP-hard on chordal graphs, can be solved in polynomial time on well-partitioned chordal graphs.
We also answer two combinatorial questions on well-partitioned chordal graphs that are open on chordal graphs, namely that each well-partitioned chordal graph admits a polynomial-time constructible tree 3-spanner, and that each (2-connected) well-partitioned chordal graph has a vertex that intersects all its longest paths (cycles).On 4-connected 4-regular graphs without even cycle decompositionshttps://zbmath.org/1491.051472022-09-13T20:28:31.338867Z"Liu, Wenzhong"https://zbmath.org/authors/?q=ai:liu.wenzhong"Cui, Qing"https://zbmath.org/authors/?q=ai:cui.qing"Wang, Yunzhuo"https://zbmath.org/authors/?q=ai:wang.yunzhuoSummary: An even cycle decomposition of a graph is a partition of its edges into even cycles. \textit{K. Markström} [ibid. 312, No. 17, 2676--2681 (2012; Zbl 1246.05087)] constructed infinitely many 2-connected 4-regular graphs without even cycle decompositions. \textit{E. Máčajová} and \textit{J. Mazák} [ibid. 313, No. 17, 1697--1699 (2013; Zbl 1277.05067)] then constructed an infinite family of 3-connected 4-regular graphs without even cycle decompositions. In this note, we further show that there exists an infinite family of 4-connected 4-regular graphs without even cycle decompositions.Balanced judicious bipartition is fixed-parameter tractablehttps://zbmath.org/1491.051482022-09-13T20:28:31.338867Z"Lokshtanov, Daniel"https://zbmath.org/authors/?q=ai:lokshtanov.daniel"Saurabh, Saket"https://zbmath.org/authors/?q=ai:saurabh.saket"Sharma, Roohani"https://zbmath.org/authors/?q=ai:sharma.roohani"Zehavi, Meirav"https://zbmath.org/authors/?q=ai:zehavi.meiravSummary: The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is ``judicious'' in the sense that neither side is burdened by too many edges, and Balanced JB also requires that the sizes of the sides themselves are ``balanced'' in the sense that neither of them is too large. Both of these problems were defined in the work by Bollobás and Scott, and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is FPT (which also proves that JB is FPT).
For the entire collection see [Zbl 1388.68010].Graphs \(G\) in which \(G-N[v]\) has a prescribed property for each vertex \(v\)https://zbmath.org/1491.051492022-09-13T20:28:31.338867Z"Zhang, Bo"https://zbmath.org/authors/?q=ai:zhang.bo.2|zhang.bo.6|zhang.bo.3|zhang.bo.9|zhang.bo|zhang.bo.5|zhang.bo.1|zhang.bo.7|zhang.bo.4|zhang.bo.8"Wu, Baoyindureng"https://zbmath.org/authors/?q=ai:wu.baoyindurengSummary: Let \(\mathcal{F}\) be a family of graphs. We characterize all graphs \(G\) such that for any vertex \(v\in V(G)\), \(G-N[v]\) is isomorphic to a member of the family \(\mathcal{F}\) if \(\mathcal{F}\) is one of the following four families of graphs: \(\{K_{1,t}\}\) for any fixed nonnegative integer \(t\); \(\{P_l\}\) for any fixed integer \(l\geq 1\); 1-regular graphs; all cliques. This partially solves some open problems raised by \textit{H. Yu} and \textit{B. Wu} [Discrete Math. 344, No. 9, Article ID 112519, 7 p. (2021; Zbl 1467.05141)].A new class for large sets of almost Hamilton cycle decompositionshttps://zbmath.org/1491.051502022-09-13T20:28:31.338867Z"Zhao, Hong-Tao"https://zbmath.org/authors/?q=ai:zhao.hongtaoSummary: A \(k\)-cycle system of order \(v\) with index \(\lambda\), denoted by \(\mathrm{CS}(v, k, \lambda)\), is a collection \(\mathcal{A}\) of \(k\)-cycles (blocks) of \(K_v\) such that each edge in \(K_{v}\) appears in exactly \(\lambda\) blocks of \(\mathcal{A}\). A large set of \(\mathrm{CS}(v, k, \lambda)\mathrm{s}\) is a partition of the set of all \(k\)-cycles of \(K_v\) into \(\mathrm{CS}(v, k, \lambda)\mathrm{s}\), and is denoted by \(\mathrm{LCS}(v, k, \lambda)\). A \((v -1)\)-cycle in \(K_v\) is called almost Hamilton. The completion of the existence problem for \(\mathrm{LCS}(v, v-1, \lambda)\) depends only on one case: all \(v\geq 4\) for \(\lambda = 2\). In this paper, it is shown that there exists an \(\mathrm{LCS}(v, v-1, 2)\) for all \(v\equiv 2\) (mod 4), \(v\geq 6\).Complex Pythagorean fuzzy threshold graphs with application in petroleum replenishmenthttps://zbmath.org/1491.051512022-09-13T20:28:31.338867Z"Akram, Muhammad"https://zbmath.org/authors/?q=ai:akram.muhammad"Ahmad, Uzma"https://zbmath.org/authors/?q=ai:ahmad.uzma"Rukhsar"https://zbmath.org/authors/?q=ai:rukhsar."Karaaslan, Faruk"https://zbmath.org/authors/?q=ai:karaaslan.faruk(no abstract)Dual hesitant \(q\)-rung orthopair fuzzy Hamacher graphs with applicationhttps://zbmath.org/1491.051522022-09-13T20:28:31.338867Z"Akram, Muhammad"https://zbmath.org/authors/?q=ai:akram.muhammad|akram.muhammad-nauman|akram.muhammad-javed|akram.muhammad-saeed"Naz, Sumera"https://zbmath.org/authors/?q=ai:naz.sumera"Ziaa, Faiza"https://zbmath.org/authors/?q=ai:ziaa.faizaSummary: Yager's \(q\)-rung orthopair fuzzy sets (\(q\)-ROFSs) can powerfully modify the range of indication of choice data by changing a parameter \(q\) based on the different hesitation degree and the dual hesitant \(q\)-rung orthopair fuzzy set (DHq-ROFS), a new technique to consider human's hesitance, can be more substantial of dealing with real multi-attribute decision making (MADM) problems. In this paper, we introduce the innovative concept of dual hesitant \(q\)-rung orthopair fuzzy graphs based on Hamacher operator called dual hesitant \(q\)-rung orthopair fuzzy Hamacher graphs (DHq-ROFHGs) and determine its energy and Randić energy. In particular, we present the energy of a generalized splitting DHq-ROFHG and generalized shadow DHq-ROFHG. Finally, a numerical instance related to the potential evaluation of emerging technology commercialization is presented to demonstrate the validity of the proposed concept in decision making and a comparison with existing method is provided. The experimental results show that the proposed approach outperforms the existing MADM approaches.Extension of threshold graphs under complex intuitionistic fuzzy environmenthttps://zbmath.org/1491.051532022-09-13T20:28:31.338867Z"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"Karaaslan, Faruk"https://zbmath.org/authors/?q=ai:karaaslan.farukSummary: In this article, we merge the attributes of two important concepts, namely complex intuitionistic fuzzy sets and threshold graphs, and bring up the idea of complex intuitionistic fuzzy threshold graphs (CIFTGs). In CIFTGs, we deal with thresholds of amplitude and phase term for membership grades as well as for non membership grades. Henceforth, we introduce the novel concept of CIFTG, as well as some related concepts such as complex intuitionistic fuzzy (CIF) alternating 4-cycle, complex intuitionistic fuzzy threshold dimension (CIFTD), and complex intuitionistic fuzzy threshold partition number (CIFTPN). Moreover, we establish certain interesting results along with examples, which are helpful to comprehend the theory of CIFTGs. Finally, we discuss the implementation of CIFTGs in the solar energy system to reveal the applicability of our approach.Covering problem on fuzzy graphs and its application in disaster management systemhttps://zbmath.org/1491.051542022-09-13T20:28:31.338867Z"Mandal, Sonia"https://zbmath.org/authors/?q=ai:mandal.sonia"Patra, Nupur"https://zbmath.org/authors/?q=ai:patra.nupur"Pal, Madhumangal"https://zbmath.org/authors/?q=ai:pal.madhumangalSummary: Nowadays the fuzzy graphs gained popularity due to their wide applications in different areas of science, engineering, social sciences, etc. In this paper, we consider covering problem in fuzzy graph. Different types of covering problems have been defined in this paper. Almost all problems are new. For each of these problems separate study is required. Also, the covering set, strong covering set, minimal covering set, etc., are defined and explained with examples. In a graph, each vertex can cover only those vertices that lie within its covering radius along shortest path and no vertex can cover itself. Here, an algorithm is designed to find the different types of covering sets on a fuzzy graph. An imprecise number, instead of a real number, namely interval number and triangular fuzzy number are considered as arc length of a fuzzy graph. To the best of our knowledge no works are available for covering problem on fuzzy graphs/networks. An application of covering set in natural disaster management is discussed to highlight the importance of the covering problem. In this application, an algorithm is designed to find all the facility vertices (or supply vertices) for given vertex and covering radius.Isomorphism on generalized fuzzy graphs and image visualizationshttps://zbmath.org/1491.051552022-09-13T20:28:31.338867Z"Samanta, Sovan"https://zbmath.org/authors/?q=ai:samanta.sovan"Sarkar, Biswajit"https://zbmath.org/authors/?q=ai:sarkar.biswajitSummary: The graph theory is being used for representation in networks and chemical atomic structures very frequently. However, these days, uncertainties are imposed on such networks. Isomorphism in generalized fuzzy graphs has been introduced here to capture the similarity of uncertainties in different networks. Homomorphism, weak isomorphism, co-weak isomorphism and nearly isomorphism are defined with examples. Also, an application of image visualization is described.Notion of complex spherical fuzzy graph with applicationhttps://zbmath.org/1491.051562022-09-13T20:28:31.338867Z"Shoaib, Muhammad"https://zbmath.org/authors/?q=ai:shoaib.muhammad"Mahmood, Waqas"https://zbmath.org/authors/?q=ai:mahmood.waqas"Albalawi, Weded"https://zbmath.org/authors/?q=ai:albalawi.weded"Shami, Faria Ahmad"https://zbmath.org/authors/?q=ai:shami.faria-ahmad(no abstract)The structure of the Heawood graphhttps://zbmath.org/1491.051572022-09-13T20:28:31.338867Z"Lawrence, Emille Davie"https://zbmath.org/authors/?q=ai:lawrence.emille-davie"Wilson, Robin T."https://zbmath.org/authors/?q=ai:wilson.robin-toddSummary: The Heawood graph, named after British mathematician Percy John Heawood, is the graph shown below in Figure 1. The Heawood graph, often denoted by \(C_{14}\), is one of 14 graphs in what is known as the \(K_7\)-family of graphs. Each graph in this family is obtained from the complete graph \(K_7\) by some finite sequence of \(\Delta Y\)- and \(Y \Delta\)-exchanges. A \(\Delta Y\)-exchange is performed by deleting the edges of a 3-cycle \(xyz\), and adding a new degree 3 vertex \(v\) that is adjacent to the vertices \(x,y\), and \(z\). A \(Y\Delta\)-exchange is the reverse of this operation. All of the graphs in the \(K_7\)-family are known to be intrinsically knotted \textit{R. Nikkuni} and \textit{K. Taniyama} [J. Knot Theory Ramifications 21, No. 7, 1250067, 14 p. (2012; Zbl 1239.57007)]. \par The graph \(C_{14}\) has been an object of study for some time, and some of the structural properties of the graph which we detail have been stated in the literature without proof. We attempt to fill that gap here. Our main results establish transitivity of the action of the automorphism group on 14-, 12-, and disjoint pairs of 6-cycles in \(C_{14}\). We also verify using Mathematica the number of cycles of each type that occur in \(C_{14}\).On the facets of stable set polytopes of circular interval graphshttps://zbmath.org/1491.051582022-09-13T20:28:31.338867Z"Oriolo, Gianpaolo"https://zbmath.org/authors/?q=ai:oriolo.gianpaolo"Stauffer, Gautier"https://zbmath.org/authors/?q=ai:stauffer.gautierSummary: A linear description of the stable set polytope \(STAB (G)\) of a quasi-line graph \(G\) is given in [\textit{F. Eisenbrand} et al., Combinatorica 28, No. 1, 45--67 (2008; Zbl 1246.05138)], where the so called Ben Rebea Theorem [\textit{G. Oriolo}, Discrete Appl. Math. 132, No. 1--3, 185--201 (2003; Zbl 1052.90108)] is proved. Such a theorem establishes that, for quasi-line graphs, \( STAB (G)\) is completely described by non-negativity constraints, clique inequalities, and clique family inequalities (CFIs). As quasi-line graphs are a superclass of line graphs, Ben Rebea Theorem can be seen as a generalization of Edmonds' characterization of the matching polytope [\textit{J. Edmonds}, J. Res. Natl. Bur. Stand., Sect. B 69, 125--130 (1965; Zbl 0141.21802)], showing that the matching polytope can be described by non-negativity constraints, degree constraints and odd-set inequalities. Unfortunately, the description given by the Ben Rebea Theorem is not minimal, i.e., it is not known which are the (non-rank) clique family inequalities that are facet defining for \(STAB (G)\). To the contrary, it would be highly desirable to have a minimal description of \(STAB (G)\), pairing that of \textit{W. Pulleyblank} and \textit{J. Edmonds} [Lect. Notes Math. 411, 214--242 (1974; Zbl 0317.05119)] for the matching polytope. In this paper, we start the investigation of a minimal linear description for the stable set polytope of quasi-line graphs. We focus on circular interval graphs, a subclass of quasi-line graphs that is central in the proof of the Ben Rebea Theorem. For this class of graphs, we move an important step forward, showing some strong sufficient conditions for a CFI to induce a facet of \(STAB (G)\). In particular, such conditions come out to be related to the existence of certain proper circulant graphs as subgraphs of \(G\). These results allows us to settle two conjectures on the structure of facet defining inequalities of the stable set polytope of circulant graphs [\textit{A. Pêcher} and \textit{A. K. Wagler}, Math. Program. 105, No. 2--3 (B), 311--328 (2006; Zbl 1083.05032)] and of (fuzzy) circular graphs [\textit{G. Oriolo} and \textit{G. Stauffer}, Math. Program. 115, No. 2 (A), 291--317 (2008; Zbl 1176.90655)], and to slightly refine the Ben Rebea Theorem itself.Forced pairs in \(A\)-Stick graphshttps://zbmath.org/1491.051592022-09-13T20:28:31.338867Z"Rusu, Irena"https://zbmath.org/authors/?q=ai:rusu.irenaSummary: A Stick graph \(G = (A \cup B, E)\) is the intersection graph of a set \(A\) of horizontal segments and a set \(B\) of vertical segments in the plane, whose left and respectively bottom endpoints lie on the same ground line with slope \(-1\). These endpoints are respectively called \(A\)-origins and \(B\)-origins. When a total order is provided for the \(A\)-origins, the resulting graphs are called \(A\)-Stick graphs.
In this paper, we propose a characterization of the class of \(A\)-Stick graphs using forced pairs, which are pairs of segments in \(B\) with the property that only one left-to-right order of their origins is possible on the ground line. We deduce a recognition algorithm for \(A\)-Stick graphs running in \(O(| A | + | B | + | E |)\) time, thus improving the running time of \(O(| A | \cdot | B |)\) of the best current algorithm. We also introduce the problem of finding, for a Stick graph, a representation using segments of minimum total length. The canonical order on the \(A\)- and \(B\)-origins, output by our recognition algorithm, allows us to obtain partial results on this problem.Radio-\(k\)-labeling of cycles for large \(k\)https://zbmath.org/1491.051602022-09-13T20:28:31.338867Z"Bloomfield, Colin"https://zbmath.org/authors/?q=ai:bloomfield.colin"Liu, Daphne Der-Fen"https://zbmath.org/authors/?q=ai:liu.daphne-der-fen"Ramirez, Jeannette"https://zbmath.org/authors/?q=ai:ramirez.jeannetteThis paper investigates the radio-\(k\)-number \(rn_k(C_n)\) of cycles and determines the values of \(rn_k(C_n)\) for \(k \ge n-3\) and for \(k < n-3\) with \(n \equiv k \pmod 2\). In the case of \(k < n-3\) and \(k \not\equiv n \pmod 2\), the study establishes lower and upper bounds for \(rn_k(C_n)\) and shows that these bounds are sharp for some values of \(k\) and \(n\).
Reviewer: Sunil C. Mathew (Kuravilangad)A novel approach for cyclic decompositions of balanced complete bipartite graphs into infinite graph classeshttps://zbmath.org/1491.051612022-09-13T20:28:31.338867Z"El-Mesady, A."https://zbmath.org/authors/?q=ai:el-mesady.ahmed"Bazighifan, Omar"https://zbmath.org/authors/?q=ai:bazighifan.omar"Askar, S. S."https://zbmath.org/authors/?q=ai:askar.sameh-s(no abstract)V-Super vertex magic labeling of some families of graphshttps://zbmath.org/1491.051622022-09-13T20:28:31.338867Z"Kumar, R. Vimal"https://zbmath.org/authors/?q=ai:kumar.r-vimal"Vijayalakshmi, D."https://zbmath.org/authors/?q=ai:vijayalakshmi.duraisamySummary: Let \(G\) be a finite simple graph with \(p\) vertices and \(q\) edges. A vertex magic total labeling is a bijection from \(V(G)\cup E(G)\) to the consecutive integers \(1,2,3,\dots \dots, p + q\) with the property that every \(u\in V(G)\), \(f(u) +\sum\limits_{v\in N(u)} f(uv)=k\) for some constant \(\mathrm{K}\). Such a labeling is V-Super if \(f[V(G)] =1,2,3,\dots, p\). A graph \(G\) is called V-Super vertex magic if it admits a V-Super vertex magic labeling. In this paper, we establish the V-Super vertex magic labeling of some classes of \(H_{2r+1,3n}\) graph, \(H_{4,2n+5}\) graph and parity graph.Typical distances in a geometric model for complex networkshttps://zbmath.org/1491.051632022-09-13T20:28:31.338867Z"Abdullah, Mohammed Amin"https://zbmath.org/authors/?q=ai:abdullah.mohammed-amin"Bode, Michel"https://zbmath.org/authors/?q=ai:bode.michel"Fountoulakis, Nikolaos"https://zbmath.org/authors/?q=ai:fountoulakis.nikolaosSummary: We study typical distances in a geometric random graph on the hyperbolic plane. Introduced by \textit{D. Krioukov} et al. [Phys. Rev. E (3) 82, No. 3, Article ID 036106, 18 p. (2010; \url{doi:10.1103/PhysRevE.82.036106})] as a model for complex networks, \(N\) vertices are drawn randomly within a bounded subset of the hyperbolic plane and any two of them are joined if they are within a threshold hyperbolic distance. With appropriately chosen parameters, the random graph is sparse and exhibits power law degree distribution as well as local clustering. In this paper we show a further property: the distance between two uniformly chosen vertices that belong to the same component is doubly logarithmic in \(N\), i.e., the graph is an \textit{ultra-small world}. More precisely, we show that the distance rescaled by \(\log \log N\) converges in probability to a certain constant that depends on the exponent of the power law. The same constant emerges in an analogous setting with the well-known \textit{Chung-Lu} model for which the degree distribution has a power law tail.Degree-degree distribution in a power law random intersection graph with clusteringhttps://zbmath.org/1491.051642022-09-13T20:28:31.338867Z"Bloznelis, Mindaugas"https://zbmath.org/authors/?q=ai:bloznelis.mindaugasSummary: The bivariate distribution of degrees of adjacent vertices, degree-degree distribution, is an important network characteristic defining the statistical dependencies between degrees of adjacent vertices. We show the asymptotic degree-degree distribution of a sparse inhomogeneous random intersection graph and discuss its relation to the clustering and power law properties of the graph.Metastability for the contact process on the preferential attachment graphhttps://zbmath.org/1491.051652022-09-13T20:28:31.338867Z"Can, Van Hao"https://zbmath.org/authors/?q=ai:can.van-haoSummary: We consider the contact process on the preferential attachment graph. The work of \textit{N. Berger} et al. [in: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23--25, 2005. New York, NY: ACM Press. 301--310 (2005; Zbl 1297.68029)] confirmed physicists predictions that the contact process starting from a typical vertex becomes endemic for an arbitrarily small infection rate \(\lambda\) with positive probability. More precisely, they showed that with probability \(\lambda^{\Theta (1)}\), it survives for a time exponential in the largest degree. Here we obtain sharp bounds for the density of infected sites at a time close to exponential in the number of vertices (up to some logarithmic factor).Birds of a feather or opposites attract -- effects in network modellinghttps://zbmath.org/1491.051662022-09-13T20:28:31.338867Z"Deijfen, Maria"https://zbmath.org/authors/?q=ai:deijfen.maria"Fitzner, Robert"https://zbmath.org/authors/?q=ai:fitzner.robertSummary: We study properties of some standard network models when the population is split into two types and the connection pattern between the types is varied. The studied models are generalizations of the Erdős-Rényi graph, the configuration model and a preferential attachment graph. For the Erdős-Rényi graph and the configuration model, the focus is on the component structure. We derive expressions for the critical parameter, indicating when there is a giant component in the graph, and study the size of the largest component by aid of simulations. When the expected degrees in the graph are fixed and the connections are shifted so that more edges connect vertices of different types, we find that the critical parameter decreases. The size of the largest component in the supercritical regime can be both increasing and decreasing as the connections change, depending on the combination of types. For the preferential attachment model, we analyze the degree distributions of the two types and derive explicit expressions for the degree exponents. The exponents are confirmed by simulations that also illustrate other properties of the degree structure.Central limit theorem for the largest component of random intersection graphhttps://zbmath.org/1491.051672022-09-13T20:28:31.338867Z"Dong, Liang"https://zbmath.org/authors/?q=ai:dong.liang"Hu, Zhishui"https://zbmath.org/authors/?q=ai:hu.zhishuiSummary: Random intersection graphs are models of random graphs in which each vertex is assigned a subset of objects independently and two vertices are adjacent if their assigned subsets are adjacent. Let \(n\) and \(m=[\beta n^{\alpha}]\) denote the number of vertices and objects respectively. We get a central limit theorem for the largest component of the random intersection graph \(G(n, m, p)\) in the supercritical regime and show that it changes between \(\alpha>1\), \(\alpha=1\) and \(\alpha<1\).Recurrence versus transience for weight-dependent random connection modelshttps://zbmath.org/1491.051682022-09-13T20:28:31.338867Z"Gracar, Peter"https://zbmath.org/authors/?q=ai:gracar.peter"Heydenreich, Markus"https://zbmath.org/authors/?q=ai:heydenreich.markus"Mönch, Christian"https://zbmath.org/authors/?q=ai:monch.christian"Mörters, Peter"https://zbmath.org/authors/?q=ai:morters.peterSummary: We investigate random graphs on the points of a Poisson process in \(d\)-dimensional space, which combine scale-free degree distributions and long-range effects. Every Poisson point carries an independent random mark and given marks and positions of the points we form an edge between two points independently with a probability depending via a kernel on the two marks and the distance of the points. Different kernels allow the mark to play different roles, like weight, radius or birth time of a vertex. The kernels depend on a parameter \(\gamma\), which determines the power-law exponent of the degree distributions. A further independent parameter \(\delta\) characterises the decay of the connection probabilities of vertices as their distance increases. We prove transience of the infinite cluster in the entire supercritical phase in regimes given by the parameters \(\gamma\) and \(\delta \), and complement these results by recurrence results if \(d=2\). Our results are particularly interesting for the soft Boolean graph model discussed in [\textit{P. Gracar} et al., ``Chemical distance in geometric random graphs with long edges and scale-free degree distribution'', Preprint, \url{arXiv:2108:11252}] and the age-dependent random connection model recently introduced by \textit{P. Gracar} et al. [Queueing Syst. 93, No. 3--4, 309--331 (2019; Zbl 1432.60090)].Assortativity in generalized preferential attachment modelshttps://zbmath.org/1491.051692022-09-13T20:28:31.338867Z"Krot, Alexander"https://zbmath.org/authors/?q=ai:krot.alexander-m"Prokhorenkova, Liudmila Ostroumova"https://zbmath.org/authors/?q=ai:ostroumova-prokhorenkova.liudmilaSummary: In this paper, we analyze assortativity of preferential attachment models. We deal with a wide class of preferential attachment models (PA-class). It was previously shown that the degree distribution in all models of the PA-class follows a power law. Also, the global and the average local clustering coefficients were analyzed. We expand these results by analyzing the assortativity property of the PA-class of models. Namely, we analyze the behavior of \(d_{nn}(d)\) which is the average degree of a neighbor of a vertex of degree \(d\).Local clustering coefficient in generalized preferential attachment modelshttps://zbmath.org/1491.051702022-09-13T20:28:31.338867Z"Krot, Alexander"https://zbmath.org/authors/?q=ai:krot.alexander-m"Prokhorenkova, Liudmila Ostroumova"https://zbmath.org/authors/?q=ai:ostroumova-prokhorenkova.liudmilaSummary: In this paper, we analyze the local clustering coefficient of preferential attachment models. A general approach to preferential attachment was introduced in [the second author et al., Lect. Notes Comput. Sci. 8305, 185--202 (2013; Zbl 1347.68020)], where a wide class of models (PA-class) was defined in terms of constraints that are sufficient for the study of the degree distribution and the clustering coefficient. It was previously shown that the degree distribution in all models of the PA-class follows a power law. Also, the global clustering coefficient was analyzed and a lower bound for the average local clustering coefficient was obtained. We expand the results of [loc. cit.] by analyzing the local clustering coefficient for the PA-class of models. Namely, we analyze the behavior of \(C(d)\) which is the average local clustering for the vertices of degree \(d\).\(\gamma\)-variable first-order logic of uniform attachment random graphshttps://zbmath.org/1491.051712022-09-13T20:28:31.338867Z"Malyshkin, Y. A."https://zbmath.org/authors/?q=ai:malyshkin.yu-a"Zhukovskii, M. E."https://zbmath.org/authors/?q=ai:zhukovskiy.mikhail-e|zhukovskii.maximThis paper examines the convergence of the probability that a first-order statement holds in a uniform attachment graph. To build such a random graph, we start from a complete graph of \(m\) vertices, and, at each step, we add a new vertex with \(m\) new edges, with the endpoints chosen uniformly at random from the already existing vertices, without replacement. The authors prove that if the number of different variables in a first-order sentence is at most \(m-2\), then the probability that the sentence is satisfied for this random graph with \(n\) vertices converges. It was already known that (contrary to many other random graph models, e.g. random regular graphs) the zero-one law is not true for this graph model for first-order sentences; the current paper shows that although the limit of the probabilities is not necessarily \(0\) or \(1\), it exists if the number of different variables is at most \(m-2\).
As for the method of the proof, the authors rely on an already known connection between first-order logic statements and the winning strategy of a so-called pebble game, and certain local properties of uniform attachment graphs. Namely, in order to make use of this correspondence, the authors describe the typical position of cycles and paths of a given length in a uniform attachment graph.
Reviewer: Ágnes Backhausz (Budapest)On the strong chromatic number of random hypergraphshttps://zbmath.org/1491.051722022-09-13T20:28:31.338867Z"Matveeva, T. G."https://zbmath.org/authors/?q=ai:matveeva.t-g"Khuzieva, A. E."https://zbmath.org/authors/?q=ai:khuzieva.alina-e"Shabanov, D. A."https://zbmath.org/authors/?q=ai:shabanov.dmitry-aSummary: We study the probability threshold for the property of strong colorability with a given number of colors of a random \(k\)-uniform hypergraph in the binomial model \(H(n,k,p)\). A vertex coloring of a hypergraph is said to be strong if any edge does not have two vertices of the same color under it. The problem of finding a sharp probability threshold for the existence of a strong coloring with \(q\) colors for \(H(n,k,p)\) is studied. By using the second moment method, we obtain fairly tight bounds for this quantity, provided that \(q\) is large enough in comparison with \(k\).Maps on random hypergraphs and random simplicial complexeshttps://zbmath.org/1491.051732022-09-13T20:28:31.338867Z"Ren, Shiquan"https://zbmath.org/authors/?q=ai:ren.shiquan"Wu, Chengyuan"https://zbmath.org/authors/?q=ai:wu.chengyuan"Wu, Jie"https://zbmath.org/authors/?q=ai:wu.jie.2Mixing time of random walk on Poisson geometry small worldhttps://zbmath.org/1491.051742022-09-13T20:28:31.338867Z"Wu, Xian-Yuan"https://zbmath.org/authors/?q=ai:wu.xian-yuanSummary: This paper focuses on the problem of modeling for \textit{small world effect} on complex networks. Let's consider the supercritical Poisson continuous percolation on \(d\)-dimensional torus \(T^d_n\) with volume \(n^d\). By adding ``long edges (short cuts)'' randomly to the largest percolation cluster, we obtain a random graph \(\mathscr{G}_n\). In the present paper, we first prove that the diameter of \(\mathscr{G}_n\) grows at most polynomially fast in \(\lg n\) and we call it the Poisson Geometry Small World. Secondly, we prove that the random walk on \(\mathscr{G}_n\) possesses the rapid mixing property, namely, the random walk mixes in time at most polynomially large in \(\lg n\).Several topological indices of random caterpillarshttps://zbmath.org/1491.051752022-09-13T20:28:31.338867Z"Zhang, Panpan"https://zbmath.org/authors/?q=ai:zhang.panpan"Wang, Xiaojing"https://zbmath.org/authors/?q=ai:wang.xiaojingSummary: In chemical graph theory, caterpillar trees have been an appealing model to represent the molecular structures of benzenoid hydrocarbon. Meanwhile, topological index has been thought of as a powerful tool for modeling quantitative structure-property relationship and quantitative structure-activity between molecules in chemical compounds. In this article, we consider a class of caterpillar trees that are incorporated with randomness, called random caterpillars, and investigate several popular topological indices of this random class, including Zagreb index, Randić index and Wiener index, etc. Especially, a central limit theorem is developed for the asymptotic distribution of the Zagreb index of random caterpillars.Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependencehttps://zbmath.org/1491.051762022-09-13T20:28:31.338867Z"Zhang, Rui-Ray"https://zbmath.org/authors/?q=ai:zhang.rui-rayThe binomial random \(r\)-uniform hypergraph \(H_r(n,p)\) is formed by considering a ground set of size \(n\) and including each of the \(\binom{n}{r}\) possible \(r\)-subsets as an edge to \(H\) independently, each with probability \(p\). A hypergraph is linear if no two of its edges intersect in two vertices or more. The article studies the (asymptotic as \(n \rightarrow \infty\), and over suitable choices of \(p = p(n)\)) probability \(\Pr(H_r(n,p) \text{ is linear})\), which is the probability that a random binomial \(r\)-uniform hypergraph is linear.
The author utilises the method of cluster expansion, which is a tool from statistical physics which has found numerous applications in enumerative and probabilistic combinatorics. In summary, the probability of interest can be written as \(\Pr(X = 0)\), where \(X = \sum_{v} X_v\) is a certain sum of non-independent indicator random variables. The dependences of \(X_v\) are captured by a dependency graph \(D\). It turns out that \(\log \Pr(X = 0)\) allows a `cluster expansion', which means that it can be written as a formal infinite sum over clusters, which in this case correspond to certain sequences of connected subgraphs (polymers) of \(D\). Then, approximations and truncations of this infinite sum yield approximations to \(\Pr(X = 0)\), as desired. The paper provides a short and nice introduction to the cluster expansion machinery, story, and possible uses; tailored to this specific case.
The main result of the paper is a formula for \(\Pr(H_r(n,p) \text{ is linear})\), which is written in terms of a certain explicit dependency graph \(D\), and works in the range where \(p = o(n^{2-r})\). For a fixed value of \(r\), this allows for a calculation of \(\Pr(H_r(n,p) \text{ is linear})\) with more detail, subject to certain explicit calculations which depend on the corresponding dependency graph \(D\). As a proof of concept, the author studies the \(3\)-uniform case \(\Pr(H_3(n,p) \text{ is linear})\) in detail, and under the assumption \(p = o(n^{-7/5})\) provides an asymptotic formula for (the logarithm of) \(\Pr(H_3(n,p) \text{ is linear})\) with four additive terms. This particular calculation refines a result by \textit{B. D. McKay} and \textit{F. Tian} [Adv. Appl. Math. 115, Article ID 102000, 47 p. (2020; Zbl 1433.05159)], which gave a formula with two terms.
Reviewer: Nicolás Sanhueza-Matamala (Praha)Granulation of ecological networks under fuzzy soft environmenthttps://zbmath.org/1491.051772022-09-13T20:28:31.338867Z"Akram, Muhammad"https://zbmath.org/authors/?q=ai:akram.muhammad-javed|akram.muhammad-nauman|akram.muhammad-saeed|akram.muhammad"Luqman, Anam"https://zbmath.org/authors/?q=ai:luqman.anamSummary: The main idea of this work is the exploration of granular structures by applying the hybrid models of fuzzy soft sets and fuzzy soft graphs to discuss the indiscernibility partition of set of universe. The information granulation is examined by applying fuzzy soft theory, and the corresponding behavior of granules is reviewed. This article proposes a novel technique of formation of granular structures using fuzzy soft graphs and defines the fuzzy soft granules. Two degree-based models are introduced to explore the abstraction of these granular structure. Then, we use these two degree-based models to granulate the certain relationships between different species in an ecological system. Further, we develop and implement some algorithms of our proposed models to granulate the underconsideration networks. Finally, a comprehensive comparison of our proposed model with other existing techniques is presented to prove the applicability and effectiveness of fuzzy soft granulation.Asymptotic behavior of common connections in sparse random networkshttps://zbmath.org/1491.051782022-09-13T20:28:31.338867Z"Das, Bikramjit"https://zbmath.org/authors/?q=ai:das.bikramjit"Wang, Tiandong"https://zbmath.org/authors/?q=ai:wang.tiandong"Dai, Gengling"https://zbmath.org/authors/?q=ai:dai.genglingSummary: Random network models generated using sparse exchangeable graphs have provided a mechanism to study a wide variety of complex real-life networks. In particular, these models help with investigating power-law properties of degree distributions, number of edges, and other relevant network metrics which support the scale-free structure of networks. Previous work on such graphs imposes a marginal assumption of univariate regular variation (e.g., power-law tail) on the bivariate generating graphex function. In this paper, we study sparse exchangeable graphs generated by graphex functions which are multivariate regularly varying. We also focus on a different metric for our study: the distribution of the number of common vertices (connections) shared by a pair of vertices. The number being high for a fixed pair is an indicator of the original pair of vertices being connected. We find that the distribution of number of common connections are regularly varying as well, where the tail indices of regular variation are governed by the type of graphex function used. Our results are verified on simulated graphs by estimating the relevant tail index parameters.Construction of directed assortative configuration graphshttps://zbmath.org/1491.051792022-09-13T20:28:31.338867Z"Deprez, Philippe"https://zbmath.org/authors/?q=ai:deprez.philippe"Wüthrich, Mario V."https://zbmath.org/authors/?q=ai:wuthrich.mario-valentinSummary: Constructions of directed configuration graphs based on a given bi-degree distribution were introduced in random graph theory some years ago. These constructions lead to graphs where the degrees of two nodes belonging to the same edge are independent. However, it is observed that many real-life networks are assortative, meaning that edges tend to connect low degree nodes with high degree nodes, or variations thereof. In this article we provide an explicit algorithm to construct directed assortative configuration graphs based on a given bi-degree distribution and an arbitrary pre-specified assortativity.Average Fermat distances on Vicsek networkshttps://zbmath.org/1491.051802022-09-13T20:28:31.338867Z"Jia, Qi"https://zbmath.org/authors/?q=ai:jia.qi"Lei, Lei"https://zbmath.org/authors/?q=ai:lei.lei"Xi, Lifeng"https://zbmath.org/authors/?q=ai:xi.lifengMean Steiner distance of Vicsek networkshttps://zbmath.org/1491.051812022-09-13T20:28:31.338867Z"Lei, Lei"https://zbmath.org/authors/?q=ai:lei.lei"Jia, Qi"https://zbmath.org/authors/?q=ai:jia.qi"Zhao, Bing"https://zbmath.org/authors/?q=ai:zhao.bingExcluded checkerboard colourable ribbon graph minorshttps://zbmath.org/1491.051822022-09-13T20:28:31.338867Z"Guo, Xia"https://zbmath.org/authors/?q=ai:guo.xia"Jin, Xian'an"https://zbmath.org/authors/?q=ai:jin.xianan"Yan, Qi"https://zbmath.org/authors/?q=ai:yan.qiSummary: Motivated by the Eulerian ribbon graph minors, in this paper we introduce the notion of checkerboard colourable minors for ribbon graphs and its dual: bipartite minors for ribbon graphs. Motivated by the bipartite minors of abstract graphs, another bipartite minors for ribbon graphs, i.e. the bipartite ribbon graph join minors are also introduced. Using these minors then we give excluded minor characterizations of the classes of checkerboard colourable ribbon graphs, bipartite ribbon graphs, plane checkerboard colourable ribbon graphs and plane bipartite ribbon graphs.Arbitrarily regularizable graphshttps://zbmath.org/1491.051832022-09-13T20:28:31.338867Z"Bozzo, Enrico"https://zbmath.org/authors/?q=ai:bozzo.enrico"Franceschet, Massimo"https://zbmath.org/authors/?q=ai:franceschet.massimoSummary: A graph is regularizable if it is possible to assign weights to its edges so that all nodes have the same degree. Weights can be positive, nonnegative or arbitrary as soon as the regularization degree is not null. Positive and nonnegative regularizable graphs have been thoroughly investigated in the literature. In this work, we propose and study arbitrarily regularizable graphs. In particular, we investigate necessary and sufficient regularization conditions on the topology of the graph and of the corresponding adjacency matrix. Moreover, we study the computational complexity of the regularization problem and characterize it as a linear programming model.Algorithm for determining the mutual impact of nodes in weighted directed graphshttps://zbmath.org/1491.051842022-09-13T20:28:31.338867Z"Lande, Dmytro"https://zbmath.org/authors/?q=ai:lande.dmytro"Dmytrenko, Oleh"https://zbmath.org/authors/?q=ai:dmytrenko.oleh"Fu, Minglei"https://zbmath.org/authors/?q=ai:fu.minglei"Hu, Minchao"https://zbmath.org/authors/?q=ai:hu.minchao"Manko, Dmytro"https://zbmath.org/authors/?q=ai:manko.dmytro"Snarskii, Andrei"https://zbmath.org/authors/?q=ai:snarskii.andrei-aSummary: We propose an algorithm for computing the influence matrix and rank distribution of nodes of a weighted directed graph by calculating the nodes' mutual impact. The algorithm of accumulative impact solves problems of dimension and computational complexity arising in the analysis of large complex systems. The algorithm calculates the mutual impact of each pair of vertices, making it possible to rank the nodes according to their importance within the system and to determine the most influential components. It produces results similar to those of the commonly used impulse method when applied to graphs that are impulse-stable in an impulse process, while overcoming the disadvantages of the impulse method in other situations. Results are always obtained regardless of impulse stability; they do not depend on the initial impulse, so that the initial values of the weights affect the calculation results. When elements in the adjacency matrix of the weighted directed graph are multiplied by a constant factor, scale invariance is not violated, and the full affect for each of the nodes scales proportionally. Several examples of analyses of weighted directed graphs, including one related to the practical problem of urban solid waste removal, are provided to demonstrate the advantages of the proposed algorithm.Graph theoryhttps://zbmath.org/1491.051852022-09-13T20:28:31.338867Z"Akram, Dehnokhalaji"https://zbmath.org/authors/?q=ai:akram.dehnokhalaji"Nasim, Nasrabadi"https://zbmath.org/authors/?q=ai:nasim.nasrabadiFrom the introduction: This chapter provides a summary of basic definitions and in concepts graph theory.
For the entire collection see [Zbl 1466.92002].Generalized matrix polynomials of tree Laplacians indexed by symmetric functions and the GTS posethttps://zbmath.org/1491.051912022-09-13T20:28:31.338867Z"Nagar, Mukesh Kumar"https://zbmath.org/authors/?q=ai:nagar.mukesh-kumar"Sivasubramanian, Sivaramakrishnan"https://zbmath.org/authors/?q=ai:sivasubramanian.sivaramakrishnanSummary: Let \(T\) be a tree on \(n\) vertices with Laplacian matrix \(L_T\) and \(q\)-Laplacian \(\mathcal{L}_T^q\). Let \(\texttt{GTS}_n\) be the generalized tree shift poset on the set of unlabelled trees on \(n\) vertices. Inequalities are known between coefficients of the immanantal polynomial of \(L_T\) and \(\mathcal{L}_T^q\) as one moves up the poset \(\texttt{GTS}_{n}\). Using the Frobenius characteristic, this can be thought as a result involving the Schur symmetric function \(s_\lambda \). In this paper, we use an arbitrary symmetric function to define a generalized matrix function of an \(n \times n\) matrix. When the symmetric function is the monomial and the forgotten symmetric function, we generalize such inequalities among coefficients of the generalized matrix polynomial of \(\mathcal{L}_T^q\) as one moves up the \(\texttt{GTS}_n\) poset.On distance-regular Cayley graphs of generalized dicyclic groupshttps://zbmath.org/1491.051972022-09-13T20:28:31.338867Z"Huang, Xueyi"https://zbmath.org/authors/?q=ai:huang.xueyi"Das, Kinkar Chandra"https://zbmath.org/authors/?q=ai:das.kinkar-chandraSummary: Let \(G\) be a generalized dicyclic group with identity 1. An inverse closed subset \(S\) of \(G \setminus \{1 \}\) is called minimal if \(\langle S \rangle = G\) and there exists some \(s \in S\) such that \(\langle S \setminus \{s, s^{- 1} \} \rangle \neq G\). In this paper, we characterize distance-regular Cayley graphs \(\operatorname{Cay}(G, S)\) of \(G\) under the condition that \(S\) is minimal.Symmetries in graphs via simplicial automorphismshttps://zbmath.org/1491.051982022-09-13T20:28:31.338867Z"Kutnar, Klavdija"https://zbmath.org/authors/?q=ai:kutnar.klavdija"Marušič, Dragan"https://zbmath.org/authors/?q=ai:marusic.draganSummary: An automorphism \(\rho\) of a graph \(X\) is said to be semiregular provided all of its cycles in its cycle decomposition are of the same length, and is said to be simplicial if it is semiregular and the quotient multigraph \(X_\rho\) of \(X\) with respect to \(\rho\) is a simple graph, and thus of the same valency as \(X\). It is shown that, with the exception of the complete graph \(K_4\), the Petersen graph, the Coxeter graph and the so called H-graph (alternatively denoted as \(S(17)\), the smallest graph in the family of the so called Sextet graphs \(S(p), p \equiv \pm 1\pmod{16}\), every cubic arc-transitive graph with a primitive automorphism group admits a simplicial automorphism.Cubic graphical regular representations of \(\mathrm{PSU}_3(q)\)https://zbmath.org/1491.051992022-09-13T20:28:31.338867Z"Li, Jing Jian"https://zbmath.org/authors/?q=ai:li.jingjian"Xia, Binzhou"https://zbmath.org/authors/?q=ai:xia.binzhou"Zhang, Xiao Qian"https://zbmath.org/authors/?q=ai:zhang.xiaoqian"Zheng, Shasha"https://zbmath.org/authors/?q=ai:zheng.shashaSummary: A graphical regular representation (GRR) of a group \(G\) is a Cayley graph of \(G\) whose full automorphism group is equal to the right regular permutation representation of \(G\). Towards a proof of the conjecture that only finitely many finite simple groups have no cubic GRR, this paper shows that \(\mathrm{PSU}_3(q)\) has a cubic GRR if and only if \(q \geq 4\). Indeed, for each \(q\), we construct explicitly a cubic GRR of \(\mathrm{PSU}_3(q)\).There does not exist a strongly regular graph with parameters \((1911, 270, 105, 27)\)https://zbmath.org/1491.052012022-09-13T20:28:31.338867Z"Koolen, Jack H."https://zbmath.org/authors/?q=ai:koolen.jack-h"Gebremichel, Brhane"https://zbmath.org/authors/?q=ai:gebremichel.brhaneThis paper contributes to the ongoing research regarding strongly regular graphs with smallest eigenvalue \(-m\) for some fixed integer \(m \geq 1\). Sims (see Theorems 8.6.3 and 8.6.4 in [\textit{A. E. Brouwer} and \textit{H. Van Maldeghem}, Strongly regular graphs. Cambridge: Cambridge University Press (2022; Zbl 07437385)]) proved that a primitive strongly regular graph with parameters \((n,k,\lambda,\mu)\) and smallest eigenvalue \(-m\) for some fixed integer \(m \geq 2\), has either \(n \leq N(m)\) for some constant \(N(m) > 0\) or \(\mu \in \{m(m-1),m^2\}\). For \(m = 3\), it was known that \(276 \leq N(3) \leq 1911\) and the main result of this paper shows \(N(3) \leq 1344\). Moreover, it is conjectured that \(N(3) = 276\). There are twelve more open cases that need to be resolved in order to prove this conjecture.
The proof is a combination of interlacing techniques and an extension of a result due to [\textit{G. R. W. Greaves} et al., Eur. J. Comb. 97, Article ID 103384, 10 p. (2021; Zbl 1473.05323)] which restricts the possible orders of maximal cliques in strongly regular graphs. It is shown that a putative strongly regular graph with parameters \((1911, 270, 105, 27)\) contains two maximal cliques that intersect in many vertices. Building on this observation, the local structure of the graph is investigated until one arrives at a contradiction.
Reviewer: Sam Mattheus (Brussel)Remarks on pseudo-vertex-transitive graphs with small diameterhttps://zbmath.org/1491.052022022-09-13T20:28:31.338867Z"Koolen, Jack H."https://zbmath.org/authors/?q=ai:koolen.jack-h"Lee, Jae-Ho"https://zbmath.org/authors/?q=ai:lee.jaeho"Tan, Ying-Ying"https://zbmath.org/authors/?q=ai:tan.yingyingSummary: Let \(\Gamma\) denote a \(Q\)-polynomial distance-regular graph with vertex set \(X\) and diameter \(D\). Let \(A\) denote the adjacency matrix of \(\Gamma \). For a vertex \(x \in X\) and for \(0 \leq i \leq D\), let \(E_i^\ast(x)\) denote the projection matrix to the \(i\)-th subconstituent space of \(\Gamma\) with respect to \(x\). The Terwilliger algebra \(T(x)\) of \(\Gamma\) with respect to \(x\) is the semisimple subalgebra of \(\operatorname{Mat}_X(\mathbb{C})\) generated by \(A, E_0^\ast(x), E_1^\ast(x), \ldots, E_D^\ast(x)\). Let \(V\) denote a \(\mathbb{C} \)-vector space consisting of complex column vectors with rows indexed by \(X\). We say \(\Gamma\) is pseudo-vertex-transitive whenever for any vertices \(x, y \in X\), there exists a \(\mathbb{C} \)-vector space isomorphism \(\rho : V \to V\) such that \((\rho A - A \rho) V = 0\) and \((\rho E_i^\ast(x) - E_i^\ast(y) \rho) V = 0\) for all \(0 \leq i \leq D\). In this paper, we discuss pseudo-vertex transitivity for distance-regular graphs with diameter \(D \in \{2, 3, 4 \} \). For \(D = 2\), we show that a strongly regular graph is pseudo-vertex-transitive if and only if all its local graphs have the same spectrum. For \(D = 3\), we consider the Taylor graphs and show that they are pseudo-vertex transitive. For \(D = 4\), we consider the antipodal tight graphs and show that they are pseudo-vertex transitive.Some Schill graphs with \(b=4\) do not existhttps://zbmath.org/1491.052032022-09-13T20:28:31.338867Z"Mahnev, A. A."https://zbmath.org/authors/?q=ai:makhnev.aleksandr-a"Belousov, I. N."https://zbmath.org/authors/?q=ai:belousov.i-n"Zhen, Jui Cai"https://zbmath.org/authors/?q=ai:zhen.jui-caiLet \(\Gamma=(V,E)\) be a connected graph with diameter \(d\). The distance \(\delta(x,y)\) between any two vertices \(x\), \(y\) of \(V\) is the length of a shortest path between \(x\) and \(y\) in \(\Gamma\). For a vertex \(x\in V\), define \(\Gamma_i(x)\) to be the set of vertices which are at distance precisely \(i\) from \(x\) \((0\leq i\leq d)\). For \(x,y\in V\) with \(\delta(x,y)=i\), denote \[ a_i=|\Gamma_i(x)\cap\Gamma(y)|,\ b_i=|\Gamma_{i+1}(x)\cap\Gamma(y)|,\ c_i=|\Gamma_{i-1}(x)\cap\Gamma(y)|, \] where \(\Gamma(y)=\Gamma_1(y)\), \(\Gamma_{-1}(y)=\Gamma_{d+1}(y)=\emptyset\). The graph \(\Gamma\) is distance-regular if the values of \(a_i\), \(b_i\), \(c_i\) only depend on the choice of \(i\) and not on the particular vertices \(x,y\) (see [\textit{A. E. Brouwer} et al., Distance-regular graphs. Berlin etc.: Springer-Verlag (1989; Zbl 0747.05073)]). The numbers \(a_i\), \(b_i\), \(c_i\) are called intersection numbers. If \(k\) is the valency of \(\Gamma\), then \(a_i+b_i+c_i=k\). The sequence \[ (k,b_1,\ldots,b_{d-1};1,c_2,\ldots,c_d) \] is called the intersection array of \(\Gamma\).
Distance-regular graphs of diameter \(d\leq2\) are precisely the connected strongly regular graphs, and these exist in great numbers (see \textit{A. E. Brouwer} and \textit{H. Van Maldeghem} [Strongly regular graphs. Cambridge: Cambridge University Press (2022; Zbl 07437385)]).
One of the central problems of the theory of distance-regular graphs is as follows: Does a graph with a given intersection array exist? If so, is it unique?
The adjacency matrix of a distance-regular graph \(\Gamma\) with valency \(k\geq2\) and diameter \(d\geq2\) has precisely \(d+1\) distinct eigenvalues: \(k=\theta_0>\theta_1>\dots>\theta_d\). If \(d=3\), then \[ \theta_1\geq\min\left\{(a_1+\sqrt{a_1^2+4k})/2,a_3\right\}. \] A distance-regular graph with diameter \(3\) and valency \(k\) is called Shilla graph if \(\theta_1=a_3\). In this case, \(a_3=(a_1+\sqrt{a_1^2+4k})/2\) and hence \(k=(a_3-a_1)a_3\). The term ``Shilla graph'' was introduced by J. Koolen, Shilla is an ancient Korean kingdom. \textit{J. H. Koolen} and \textit{J. Park} [Eur. J. Comb. 31, No. 8, 2064--2073 (2010; Zbl 1221.05117)] proved that for given \(b\geq2\), there are finitely many Shilla graphs \(\Gamma\) with \(b=a_3-a_1\). There they also listed all Shilla graphs with \(b=2\) and listed all the possible intersection arrays, if \(b=3\). \textit{I. N. Belousov} [Proc. Steklov Inst. Math. 307, S23--S33 (2019; Zbl 1478.05036); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 24, No. 3, 16--26 (2018)] generated all the possible intersection arrays of Shilla graphs for \(b=4\) and \(b=5\).
In the paper under review, the authors prove that there are no Shilla graphs with some intersection arrays at \(b=4\) from Belousov's list.
Reviewer: Mikhail Kabenyuk (Kemerovo)A new view toward vertex decomposable graphshttps://zbmath.org/1491.052052022-09-13T20:28:31.338867Z"Guo, Jin"https://zbmath.org/authors/?q=ai:guo.jin"Li, Meiyan"https://zbmath.org/authors/?q=ai:li.meiyan"Wu, Tongsuo"https://zbmath.org/authors/?q=ai:wu.tongsuoSummary: In this paper, we bring a new view about closed neighbourhood to show the vertex decomposability of graphs. Making use of the characterization of hereditary vertex decomposable graphs, we introduce a class of vertex decomposable graphs, which include some well-known classic vertex decomposable graphs such as clique-whiskered graphs and Cameron-Walker graphs.Vanishing of cohomology groups of random simplicial complexeshttps://zbmath.org/1491.052062022-09-13T20:28:31.338867Z"Cooley, Oliver"https://zbmath.org/authors/?q=ai:cooley.oliver"Del Giudice, Nicola"https://zbmath.org/authors/?q=ai:del-giudice.nicola"Kang, Mihyun"https://zbmath.org/authors/?q=ai:kang.mihyun"Sprüssel, Philipp"https://zbmath.org/authors/?q=ai:sprussel.philippSummary: We consider \(k\)-dimensional random simplicial complexes that are generated from the binomial random \((k+1)\)-uniform hypergraph by taking the downward-closure, where \(k\geq 2\). For each \(1\leq j\leq k-1\), we determine when all cohomology groups with coefficients in \(\mathbb{F}_2\) from dimension one up to \(j\) vanish and the zeroth cohomology group is isomorphic to \(\mathbb{F}_2\). This property is not monotone, but nevertheless we show that it has a single sharp threshold. Moreover, we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. Furthermore, we study the asymptotic distribution of the dimension of the \(j\)th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced by \textit{N. Linial} and \textit{R. Meshulam} [Combinatorica 26, No. 4, 475--487 (2006; Zbl 1121.55013)], a result which has only been known for dimension two [\textit{M. Kahle} and \textit{B. Pittel}, Random Struct. Algorithms 48, No. 1, 102--124 (2016; Zbl 1333.05272)].
For the entire collection see [Zbl 1390.68020].Directed graphs from exact covering systemshttps://zbmath.org/1491.110082022-09-13T20:28:31.338867Z"Neidmann, Dana"https://zbmath.org/authors/?q=ai:neidmann.danaThe paper introduces a family of directed graphs on the set of integers associated with the covering system: Given an exact covering system \(S=\{x\equiv a_i \pmod {d_i} : 1 \le i \le r\}\), in which each integer \(n\) satisfies \(n \equiv a_i \pmod {d_i}\) for exactly one value of \(i\), create the corresponding exact covering system digraph \(G_S=G(d_1n+a_1,\ldots, d_rn+a_r):=(V,E) \), where \(V(G_S)=\mathbb{Z} \) and \(E(G_S)=\{(n, d_in+a_i) : 1 \le i \le r\} \); that is, the vertices of \(G_S\) are the integers and the edges are \( (n, d_in+a_i)\) for each \(n\in\mathbb{Z}\) and for each congruence in the covering system. The author studies the structural properties of the exact covering system digraphs which have finitely many components, one cycle per component, indegree \(1\) and outdegree \(r\) at each vertex. Special attention is paid to the structure of digraphs of degree \(1\) and of degree at least \(2\). The author also finds graph isomorphisms between different exact covering system digraphs. The paper explores the link between digraphs that have a single component and non-standard digital representation of integers.
Reviewer: Armen Bagdasaryan (Madīnat al-Kuwait)The exact annihilating-ideal graph of a commutative ringhttps://zbmath.org/1491.130082022-09-13T20:28:31.338867Z"Visweswaran, Subramanian"https://zbmath.org/authors/?q=ai:visweswaran.subramanian"Lalchandani, Premkumar T."https://zbmath.org/authors/?q=ai:lalchandani.premkumar-tGiven a commutative ring \(R\) with identity, an ideal \(I\) of \(R\) is said to be an exact annihilating ideal if there exists a non-zero ideal \(J\) such that \(\mathrm{Ann}(I) = J\) and \(\mathrm{Ann}(J) = I\). Here \(\mathrm{Ann}(I)\) denotes the annihilator of \(I\) in \(R\), and similarly for \(\mathrm{Ann}(J)\). Let \(\mathbb{EA}(R)^*\) denote the set of all nonzero exact annihilating ideals of \(R\). \textit{P. T. Lalchandani} [J. Algebra Relat. Top. 5, No. 1, 27--33 (2017; Zbl 1390.13009)] introduced the exact annihilating-ideal graph of \(R\), denoted by \(\mathbb{EAG}(R)\), whose vertex set is \(\mathbb{EA}(R)^*\) and distinct vertices \(I\) and \(J\) are adjacent if and only if \(\mathrm{Ann}(I) = J\) and \(\mathrm{Ann}(J) = I\).
The paper under review is devoted to the study of the exact annihilating-ideal graphs of commutative rings. The authors first discuss some basic properties of exact annihilating ideals for special rings, such as special principal ideal rings, principal ideal domains and von Neumann regular rings which are not fields. Then the authors investigate the graph structures of \(\mathbb{EAG}(R)\) for special principal ideal rings and reduced rings which admit only a finite number of minimal prime ideals.
Reviewer: Houyi Yu (Chongqing)Correction to: ``Classification of non-local rings with genus two zero-divisor graphs''https://zbmath.org/1491.130132022-09-13T20:28:31.338867Z"Asir, T."https://zbmath.org/authors/?q=ai:asir.t"Mano, K."https://zbmath.org/authors/?q=ai:mano.karuppiah"Tamizh Chelvam, T."https://zbmath.org/authors/?q=ai:tamizh-chelvam.thirugnanamCorrection of some errors in the statement and proof of Theorem 4 in the first two authors' paper [ibid. 24, No. 1, 237--245 (2020; Zbl 1436.13016)].Matchings and squarefree powers of edge idealshttps://zbmath.org/1491.130292022-09-13T20:28:31.338867Z"Erey, Nursel"https://zbmath.org/authors/?q=ai:erey.nursel"Herzog, Jürgen"https://zbmath.org/authors/?q=ai:herzog.jurgen"Hibi, Takayuki"https://zbmath.org/authors/?q=ai:hibi.takayuki"Saeedi Madani, Sara"https://zbmath.org/authors/?q=ai:madani.sara-saeediLet \(G=(V,E)\) be a simple graph on a vertex set \(V\). The edge ideal of \(G\) is the squarefree monomial ideal
\[
I(G)=(\textbf{x}_e \colon \; e \in E),
\]
where \(\textbf{x}_e=x_i x_j\) for \(e=\{i,j\}\). The \(k\)th squarefree power of \(G\), denoted by \(I(G)^{[k]}\), is the squarefree monomial ideal generated by all squarefree monomials in \(I(G)^k\), the \(k\)th ordinary power of \(I(G)\). The paper under review gives an upper bound for the regularity of the squarefree powers of edge ideal of a graph \(G\) and investigates when such powers are linearly related or have linear resolution.
A finite set of edges \(M = \{e_1,\ldots, e_k\} \subseteq E\) is called a matching of \(G\) if \(e_i \cap e_j = \varnothing\) for \(1 \leq i < j \leq k\). Given a matching \(M\) of \(G\), let \(u_M=\prod_{e \in M} \textbf{x}_e\). It turns out that
\[
I(G)^{[k]}=\left(u_M \colon \; M \text{ is a matching in } G \text{ and } |M|=k \right).
\]
In the study of squarefree powers of edge ideals, there are three important invariants of a graph \(G\) which are introduced as follows:
\begin{itemize}
\item \textbf{Matching number.} The matching number of \(G\), denoted by \(\nu(G)\), is the maximum cardinality of a matching of \(G\). Clearly, \(I(G)=I(G)^{[1]}\) and \(I(G)^{[k]}=0\) for \(k>\nu(G)\). It is shown in [\textit{M. Bigdeli} et al., Commun. Algebra 46, No. 3, 1080--1095 (2018; Zbl 1428.13032), Theorem 5.1] that \(I(G)^{[\nu(G)]}\) has linear quotients.
\item \textbf{Induced matching number.} An induced matching of \(G\) is a matching \(M = \{e_1,\ldots, e_k\}\) of \(G\) such that the induced subgraph of \(G\) on \(\cup_{i=1}^k e_i\) has exactly \(k\) edges. the number \(\nu_1(G)\) stands for the induced matching number of \(G\) which is the maximum size of an induced matching in \(G\).
\item \textbf{Restricted matching number.} A restricted matching of \(G\) is a matching in which there exists an edge which provides a gap in \(G\) with any other edge in the matching. The maximum size of a restricted matching in \(G\) is denoted by \(\nu_0(G)\).
\end{itemize}
One may observe that
\[
\nu_1(G) \leq \nu_0(G) \leq \nu(G).
\]
One of the main results of the paper under review is that for a graph \(G\), and for all \(1 \leq k \leq \nu_1(G)\) one has the inequality
\[
\mathrm{reg}(I(G)^{[k]}) \geq k+\nu_1(G).
\]
On the other hand, the authors show that \(\mathrm{reg}(I(G)^{[k]}) \leq k+\nu(G)\) for \(k=2\). This inequality is already known for \(k=1\) [\textit{H. T. Hà} and \textit{A. Van Tuyl}, J. Algebr. Comb. 27, No. 2, 215--245 (2008; Zbl 1147.05051), Theorem 1.5] and \(k=\nu(G)\) [\textit{M. Bigdeli} et al., Commun. Algebra 46, No. 3, 1080--1095 (2018; Zbl 1428.13032), Theorem 5.1].
A homogeneous ideal \(I\) in the polynomial ring \(S=\mathbb{K}[x_1, \ldots, x_n]\) is said to be linearly related, if the first syzygy module of \(I\) is generated by linear relations. The other main result of this paper states that if \(G\) is a graph and \(I(G)^{[k]}\) is linearly related then so is \(I(G)^{[k+1]}\). It follows that there exists a smallest integer \(\lambda(I(G))\) for which \(I(G)^{[k]}\) is linearly related for all \(k \geq \lambda(I(G))\). It is known [\textit{M. Bigdeli} et al., Commun. Algebra 46, No. 3, 1080--1095 (2018; Zbl 1428.13032), Lemma 5.2] that \(\lambda(I(G)) \geq \nu_0(G)\) and there are some examples with strict inequality. The authors show that \(I(G)^{[\nu_0(G)]}\) is linearly related if \(\nu_0(G) \leq 2\).
A squarefree monomial ideal \(I\) is said to satisfy the squarefree Ratliff property, if \(I^{[k]} \colon I = I^{[k]}\) for all \(k \geq 2\). The last main result of the paper under review states that any nonzero squarefree monomial ideal satisfies the squarefree Ratliff property.
Reviewer: Ali Akbar Yazdan Pour (Zanjan)Very well-covered graphs and local cohomology of their residue rings by the edge idealshttps://zbmath.org/1491.130302022-09-13T20:28:31.338867Z"Kimura, K."https://zbmath.org/authors/?q=ai:kimura.kyouko"Pournaki, M. R."https://zbmath.org/authors/?q=ai:pournaki.mohammad-reza"Terai, N."https://zbmath.org/authors/?q=ai:terai.naoki"Yassemi, S."https://zbmath.org/authors/?q=ai:yassemi.siamakLet \(G\) be a simple graph without isolated vertices and let \(I(G)\) denote its edge ideal. Recall that \(G\) is called very well-covered if \(I(G)\) is unmixed and the number of vertices of \(G\) is equal to \(2\operatorname{ht} I(G)\).
The main result of this article is a structure theorem on very well-covered graphs, based on Cohen-Macaulay very well-covered graphs. The latter were characterized in [\textit{M. Crupi} et al., Nagoya Math. J. 201, 117--131 (2011; Zbl 1227.05218)]. In the present article, the authors show that if \(G\) is very well-covered, then there exists a very well-covered Cohen-Macaulay graph \(H\), such that \(G\) can be obtained from \(H\) by replacing the edges in a certain subset of edges of \(H\), \(\{e_1,\dots,e_{d}\}\), with complete bipartite graphs \(K_{n_1,n_1},\dots, K_{n_d,n_d}\) (Theorem 3.5). The authors then use this result to obtain formulas for the Hilbert series of the local cohomology modules of the residue ring of the edge ideal (Theorem 4.4), and also for the regularity (Theorem 5.1) and depth (Theorem 5.3) of this ring. The two last results compare to Theorem 4.12 in [\textit{M. Mahmoudi} et al., J. Pure Appl. Algebra 215, No. 10, 2473--2480 (2011; Zbl 1227.13017)] and Theorem 1.1 in [\textit{K. Kimura} et al., Nagoya Math. J. 230, 160--179 (2018; Zbl 1411.13018)], respectively.
Reviewer: Jorge Neves (Coimbra)Pairs of maps preserving singularity on subsets of matrix algebrashttps://zbmath.org/1491.150042022-09-13T20:28:31.338867Z"Guterman, A. E."https://zbmath.org/authors/?q=ai:guterman.alexander-e"Maksaev, A. M."https://zbmath.org/authors/?q=ai:maksaev.artem-m"Promyslov, V. V."https://zbmath.org/authors/?q=ai:promyslov.valentin-vLet \(\mathbb{M}_{n}\) be the set of all \(n\times n\) matrices over a field \( \mathbb{F}\), and \(\mathcal{Y\subseteq }\mathbb{M}_{n}\). A pair of maps \( T_{1},T_{2}\) from \(\mathcal{Y}\) into \(\mathbb{M}_{n}\) is said to satisfy the pencil condition for singularity on \(\mathcal{Y}\) if for all \(A,B\in \mathcal{Y}\) and nonzero \(\lambda \in \mathbb{F}\) we have (\(A_{1}+\lambda B_{1}\) is singular) \(\iff \) (\(T_{1}(A_{1})+\lambda T_{2}(B_{2})\) is singular). The one-sided pencil condition for singularity on \(\mathcal{Y}\) is obtained if we replace \(\iff \) by \(\implies\). The main theorem of the paper is that the following conditions are equivalent:
(1) \(T_{1},T_{2}\) satisfies the pencil condition for singularity on \(\mathbb{M}_{n}\);
(2) \( T_{1},T_{2}\) satisfy the one-sided pencil condition for singularity on \( \mathbb{M}_{n}\) and there exists a matrix \(D\) such that both \(D\) and \( T_{2}(D)\) are nonsingular;
(3) \(T_{1}=T_{2}\) and there exist nonsingular matrices \(P\) and \(Q\) such that either \(T_{1}(A)=PAQ\) for all \(A\in \mathbb{M} _{n}\) or \(T_{1}(A)=PA^{t}Q\) for all \(A\in \mathbb{M}_{n}\) (\(t\) denotes the transpose).
The paper also includes many variations of this theme.
Reviewer: John D. Dixon (Ottawa)Singularity of discrete random matriceshttps://zbmath.org/1491.150402022-09-13T20:28:31.338867Z"Jain, Vishesh"https://zbmath.org/authors/?q=ai:jain.vishesh"Sah, Ashwin"https://zbmath.org/authors/?q=ai:sah.ashwin"Sawhney, Mehtaab"https://zbmath.org/authors/?q=ai:sawhney.mehtaab-sAuthors' abstract: Let \(\xi\) be a non-constant real-valued random variable with finite support and let \(M_n(\xi )\) denote an \(n\times n\) random matrix with entries that are independent copies of \(\xi \). For \(\xi\) which is not uniform on its support, we show that
\begin{align*}
{\mathbb{P}}[M_n(\xi )\text{ is singular}] &= {\mathbb{P}}[\text{zero row or column}] \\
&\quad +(1+o_n(1)){\mathbb{P}}[\text{two equal (up to sign) rows or columns}],
\end{align*}
thereby confirming a folklore conjecture. As special cases, we obtain:
\begin{itemize}
\item For \(\xi = {\text{Bernoulli}}(p)\) with fixed \(p \in (0,1/2)\),
\[
{\mathbb{P}}[M_n(\xi )\text{ is singular}] = 2n(1-p)^n + (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^n,
\] which determines the singularity probability to \textit{two} asymptotic terms. Previously, no result of such precision was available in the study of the singularity of random matrices. The first asymptotic term confirms a conjecture of Litvak and Tikhomirov.
\item For \(\xi = {\text{Bernoulli}}(p)\) with fixed \(p \in (1/2,1)\),
\[
{\mathbb{P}}[M_n(\xi )\text{ is singular}] = (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^n.
\] Previously, only the much weaker upper bound of \((\sqrt{p} + o_n(1))^n\) was known due to the work of Bourgain-Vu-Wood.
\end{itemize}
For \(\xi\) which is uniform on its support:
\begin{itemize}
\item We show that
\[
{\mathbb{P}}[M_n(\xi )\text{ is singular}]\&= (1+o_n(1))^n{\mathbb{P}}[\text{two rows or columns are equal}].
\]
\item Perhaps more importantly, we provide a sharp analysis of the contribution of the `compressible' part of the unit sphere to the lower tail of the smallest singular value of \(M_n(\xi )\).
\end{itemize}
Reviewer: Sho Matsumoto (Kagoshima)Heptavalent arc-transitive Cayley graphs of Frobenius groups with soluble vertex stabilizerhttps://zbmath.org/1491.200072022-09-13T20:28:31.338867Z"Liu, Harlin"https://zbmath.org/authors/?q=ai:liu.harlinSummary: A Cayley graph \(\Gamma\) is said to be arc-transitive if its full automorphism group \(\Aut\Gamma\) is transitive on the arc set of \(\Gamma\). In this paper, we give a characterization of heptavalent arc-transitive Cayiey graphs on a class of Frobenius groups with soluble vertex stabilizer.Recognition of Janko groups and some simple \(K_4\)-groups by the order and one irreducible character degree or character degree graphhttps://zbmath.org/1491.200132022-09-13T20:28:31.338867Z"Behravesh, Hoshang"https://zbmath.org/authors/?q=ai:behravesh.hoshang"Ghaffarzadeh, Mehdi"https://zbmath.org/authors/?q=ai:ghaffarzadeh.mehdi"Ghasemi, Mohsen"https://zbmath.org/authors/?q=ai:ghasemi.mohsen"Hekmatara, Somayeh"https://zbmath.org/authors/?q=ai:hekmatara.somayehSummary: In this paper we prove that some Janko groups are uniquely determined by their orders and one irreducible character degree. Also we prove that some finite simple \(K_4\)-groups are uniquely determined by their character degree graphs and their orders.Subgroups of arbitrary even ordinary depthhttps://zbmath.org/1491.200162022-09-13T20:28:31.338867Z"Janabi, Hayder"https://zbmath.org/authors/?q=ai:janabi.hayder-abbas"Breuer, Thomas"https://zbmath.org/authors/?q=ai:breuer.thomas"Horváth, Erzsébet"https://zbmath.org/authors/?q=ai:horvath.erzsebetSummary: We show that for each positive integer \(n\), there exist a group \(G\) and a subgroup \(H\) such that the ordinary depth \(d(H,G)\) is \(2n\). This solves the open problem posed by Lars Kadison whether even ordinary depth larger than \(6\) can occur.Some results on the main supergraph of finite groupshttps://zbmath.org/1491.200292022-09-13T20:28:31.338867Z"Asboei, A. K."https://zbmath.org/authors/?q=ai:khalili-asboei.alireza"Salehi, S. S."https://zbmath.org/authors/?q=ai:salehi.s-sSummary: Let \(G\) be a finite group. The main supergraph \(\mathcal{S}(G)\) is a graph with vertex set \(G\) in which two vertices \(x\) and \(y\) are adjacent if and only if \(o(x)|o(y)\) or \(o(y)| o(x)\). In this paper, we will show that \(G\cong \mathrm{PSL}(2, p)\) or \(\mathrm{PGL}(2, p)\) if and only if \(\mathcal{S}(G)\cong \mathcal{S}(\mathrm{PSL}(2, p))\) or \(\mathcal{S}(\mathrm{PGL}(2, p))\), respectively. Also, we will show that if \(M\) is a sporadic simple group, then \(G\cong M\) if only if \(\mathcal{S}(G)\cong \mathcal{S}(M)\).OD-characterization of some simple unitary groupshttps://zbmath.org/1491.200572022-09-13T20:28:31.338867Z"Akbari, Majid"https://zbmath.org/authors/?q=ai:akbari.majid"Chen, Xiaoyou"https://zbmath.org/authors/?q=ai:chen.xiaoyou"Moghaddamfar, Alireza"https://zbmath.org/authors/?q=ai:moghaddamfar.ali-rezaSummary: We show that the simple unitary groups \(U_3(q)\) and \(U_4(q)\), with \(2< q < 10^2\) a prime power, are characterized among all groups by their order and the degrees of the vertices of their prime graph.Some results on the join graph of finite groupshttps://zbmath.org/1491.200592022-09-13T20:28:31.338867Z"Bahrami, Zahara"https://zbmath.org/authors/?q=ai:bahrami.zahara"Taeri, Bijan"https://zbmath.org/authors/?q=ai:taeri.bijanSummary: Let \(G\) be a finite group which is not cyclic of prime power order. The join graph \(\Delta (G)\) of \(G\) is a graph whose vertex set is the set of all proper subgroups of \(G\), which are not contained in the Frattini subgroup \(G\) and two distinct vertices \(H\) and \(K\) are adjacent if and only if \(G=\langle H, K\rangle\). Among other results, we show that if \(G\) is a finite cyclic group and \(H\) is a finite group such that \(\Delta (G)\cong \Delta(H)\), then \(H\) is cyclic. Also we prove that \(\Delta (G) \cong\Delta (A_5)\) if and only if \(G\cong A_5\).A graph associated to centralizer of elements of a grouphttps://zbmath.org/1491.200632022-09-13T20:28:31.338867Z"Johari, Farangis"https://zbmath.org/authors/?q=ai:johari.farangis"Khashyarmanesh, Kazem"https://zbmath.org/authors/?q=ai:khashyarmanesh.kazemOn joins and intersections of subgroups in free groupshttps://zbmath.org/1491.200672022-09-13T20:28:31.338867Z"Ivanov, Sergei V."https://zbmath.org/authors/?q=ai:ivanov.sergei-vladimirovich.1Summary: We study graphs of (generalized) joins and intersections of finitely generated subgroups of a free group. We show how to disprove a lemma of Imrich and Müller on these graphs, how to repair the lemma and how to utilize it.Group-theoretical graph categorieshttps://zbmath.org/1491.200992022-09-13T20:28:31.338867Z"Gromada, Daniel"https://zbmath.org/authors/?q=ai:gromada.danielThe paper under review is concerned with certain diagrammatic categories of partitions and graphs and with their relations with compact matrix quantum groups and their representation categories, as considered in [\textit{S.L.\ Woronowicz}, Invent.\ Math.\ 93, No.\ 1, 35--76 (1988; Zbl 0664.58044)]. Categories of partitions were classified in [\textit{S. Raum} and \textit{M. Weber}, Commun. Math. Phys. 341, No. 3, 751--779 (2016; Zbl 1356.46061)], and an important class of such categories is formed by the group theoretical categories of partitions. The compact matrix quantum groups corresponding to group theoretical categories of partitions were described in [\textit{S.\ Raum} and \textit{M.\ Weber}, J.\ Noncommut.\ Geom.\ 9, No.\ 4, 1261--1293 (2015; Zbl 1350.46047)], and a more general class of skew categories of partitions was studied in [\textit{L. Maaßen}, J. Noncommut. Geom. 14, No. 3, 987--1017 (2020; Zbl 07358364)]. The present paper generalizes these concepts into the context of graph categories. The author defines a class of \emph{group theoretical graph categories} and introduces the more general concept of \emph{skew graph categories}. He also defines \emph{graph fibrations}, shows that they are in one-to-one correspondence with skew graph categories and uses them to describe the compact matrix quantum group corresponding to such a category. In the final section, the opposite question of describing graph categories corresponding to a given compact matrix quantum group is considered.
Reviewer: Jonathan Gruber (Lausanne)\(\mathscr{L}\)-, \(\mathscr{R}\)- and \(\mathscr{H}\)-cross-sections in the strong endomorphism semigroup of the undirected graphshttps://zbmath.org/1491.201262022-09-13T20:28:31.338867Z"Bondar, E. A."https://zbmath.org/authors/?q=ai:bondar.eugenija-aSummary: In the present paper we show that the strong endomorphism monoid of a finite undirected graph without multiply edges contains a unique \(\mathscr{R}\)-cross-section up to an isomorphism. We find necessary and sufficient conditions of an existence of \(\mathscr{H}\)-cross-sections and construct examples of \(\mathscr{L}\)-cross-sections. Also we prove that any \(\mathscr{L}\)-, \(\mathscr{R}\)- and \(\mathscr{H}\)-cross-section of the strong endomorphism semigroup is isomorphic to the direct product of the corresponding cross-sections in symmetric semigroups.Green's relations in finite transformation semigroupshttps://zbmath.org/1491.201292022-09-13T20:28:31.338867Z"Fleischer, Lukas"https://zbmath.org/authors/?q=ai:fleischer.lukas"Kufleitner, Manfred"https://zbmath.org/authors/?q=ai:kufleitner.manfredSummary: We consider the complexity of Green's relations when the semigroup is given by transformations on a finite set. Green's relations can be defined by reachability in the (right/left/two-sided) Cayley graph. The equivalence classes then correspond to the strongly connected components. It is not difficult to show that, in the worst case, the number of equivalence classes is in the same order of magnitude as the number of elements. Another important parameter is the maximal length of a chain of components. Our main contribution is an exponential lower bound for this parameter. There is a simple construction for an arbitrary set of generators. However, the proof for constant alphabet is rather involved. Our results also apply to automata and their syntactic semigroups.
For the entire collection see [Zbl 1362.68016].Non-commuting graphs and some bounds for commutativity degree of finite Moufang loopshttps://zbmath.org/1491.201602022-09-13T20:28:31.338867Z"Rezaie, Elhameh"https://zbmath.org/authors/?q=ai:rezaie.elhameh"Ahmadidelir, Karim"https://zbmath.org/authors/?q=ai:ahmadidelir.karim"Tehranian, Abolfazl"https://zbmath.org/authors/?q=ai:tehranian.abolfazl"Rasouli, Hamid"https://zbmath.org/authors/?q=ai:rasouli.hamidSummary: In this paper, we study some properties of the non-commuting graph \(\varGamma_M\) of a finite Moufang loop \(M\), a graph obtained by setting all non-central elements of \(M\) as the vertex set and defining two distinct vertices to be adjacent if and only if their commutator is non-identity. In particular, Hamiltonian as well as (weak) perfectness of non-commuting graphs of Chein loops are considered. We find several upper and lower bounds for commutativity degree of some classes of finite Moufang loops by means of edge number of their non-commuting graphs and algebraic properties.Hypergroups associated with hypergraphshttps://zbmath.org/1491.201722022-09-13T20:28:31.338867Z"Nikkhah, A."https://zbmath.org/authors/?q=ai:nikkhah.abolfazl"Davvaz, B."https://zbmath.org/authors/?q=ai:davvaz.bijanDynamic coupling in small-world outer synchronization of chaotic networkshttps://zbmath.org/1491.370832022-09-13T20:28:31.338867Z"Arellano-Delgado, A."https://zbmath.org/authors/?q=ai:arellano-delgado.adrian"López-Gutiérrez, R. M."https://zbmath.org/authors/?q=ai:lopez-gutierrez.r-m"Méndez-Ramírez, R."https://zbmath.org/authors/?q=ai:mendez-ramirez.rodrigo"Cardoza-Avendaño, L."https://zbmath.org/authors/?q=ai:cardoza-avendano.l"Cruz-Hernández, C."https://zbmath.org/authors/?q=ai:cruz-hernandez.cesarSummary: In this work, the problem of small-world outer synchronization of chaotic networks using a dynamic intermediary system is studied. The proposed dynamic coupling is applied to the small-world model of \textit{M. Newman} and \textit{D. J. Watts} [in \textit{M. Newman} (ed.) et al., The structure and dynamics of networks. Princeton, NJ: Princeton University Press (2006; Zbl 1362.00042)], where the Chua's chaotic circuit is used like node. Some scenarios are presented where comparative analyses are performed to determine the inner and outer coupling strengths necessary to achieve networks synchronization of both a static diffusive (direct) coupling and the proposed dynamic (indirect) coupling. The comparative analysis between the conventional coupling and the proposed dynamic coupling, which is applied to both the inner and outer synchronization of the studied networks, is carried out through the analysis of the maximum Lyapunov exponent of the generic variational equations.The mathematics of Ferran Hurtado: a brief surveyhttps://zbmath.org/1491.520012022-09-13T20:28:31.338867Z"Urrutia, Jorge"https://zbmath.org/authors/?q=ai:urrutia.jorge-lThis is a short survey article on the scientific work of Ferran Hurtado, based on his selected papers. The author briefly discusses Hurtado's research, recalling his results as well as questions posed by him, related to polygonizations, triangulations (topics: flipping edges in triangulations; compatible triangulations); point sets in the plane (topics: Erdős-Szekeres type problems; measures of convexity; \(k\)-convex point sets); as well as planar graphs and related issues (topics: coloring arrangements of lines; packing trees in complete geometric graphs; witnesses in Delaunay and Gabriel graphs; alternating paths; augmenting the connectivity of geometric graphs).
For the entire collection see [Zbl 1351.68008].
Reviewer: Piotr Niemiec (Kraków)Generalised rigid body motions in non-Euclidean planes with applications to global rigidityhttps://zbmath.org/1491.520192022-09-13T20:28:31.338867Z"Dewar, Sean"https://zbmath.org/authors/?q=ai:dewar.sean"Nixon, Anthony"https://zbmath.org/authors/?q=ai:nixon.anthonySummary: A bar-joint framework \((G, p)\) in a (non-Euclidean) real normed plane \(X\) is the combination of a finite, simple graph \(G\) and a placement \(p\) of the vertices in \(X\). A framework \((G, p)\) is globally rigid in \(X\) if every other framework \((G, q)\) in \(X\) with the same edge lengths as \((G, p)\) arises from an isometry of \(X\). The weaker property of local rigidity in normed planes (where only \((G, q)\) within a neighbourhood of \((G, p)\) are considered) has been studied by several researchers over the last 5 years after being introduced by Kitson and Power for \(\ell_p\)-norms. However global rigidity is an unexplored area for general normed spaces, despite being intensely studied in the Euclidean context by many groups over the last 40 years. In order to understand global rigidity in \(X\), we introduce new generalised rigid body motions in normed planes where the norm is determined by an analytic function. This theory allows us to deduce several geometric and combinatorial results concerning the global rigidity of bar-joint frameworks in \(X\).\(b\)-metric spaces with a graph and best proximity points for some contractionshttps://zbmath.org/1491.540782022-09-13T20:28:31.338867Z"Fallahi, K."https://zbmath.org/authors/?q=ai:fallahi.kamal|fallahi.kia"Ayobian, M."https://zbmath.org/authors/?q=ai:ayobian.mSummary: In this paper, we introduce a new type of graph contraction using a special class of functions and give a best proximity point theorem for this contraction in complete metric spaces endowed with a graph. Then we support our main theorem by a non-trivial example and give some consequences of it for usual graphs.First-passage percolation in random planar maps and Tutte's bijectionhttps://zbmath.org/1491.600202022-09-13T20:28:31.338867Z"Lehéricy, Thomas"https://zbmath.org/authors/?q=ai:lehericy.thomasA rooted planar map \(M\) is a finite planar graph embedded in the 2-sphere, with one oriented edge marked as root edge. For a wide range of models of random maps it is known that the vertex set \(V(M)\), when viewed as a metric space for the graph distance, converges in distribution towards a random compact metric space called the Brownian map. The author asks what can be said when the graph distance is replaced by other distances? Such distances can be obtained by assigning weights to the edges of the graph. Of particular interest is the so-called first-passage percolation distance for which i.i.d. weights are chosen for the edges. The first main goal of the paper is to extend the results of [\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)] in which the first-passage percolation distance was studied in large triangulations. In Theorem 1.1, the author shows that the first-passage percolation distance in quadrangulations as well as in general planar maps behaves like a constant times the graph distance. In Theorem 1.2, the author relates his findings to Tutte transformations of rooted quandrangulations. Furthermore, he gives versions of his results for the infinite random lattices that arise as local limits of large quadrangulations or general planar maps.
Reviewer: Florian Pausinger (Belfast)Random connection models in the thermodynamic regime: central limit theorems for add-one cost stabilizing functionalshttps://zbmath.org/1491.600402022-09-13T20:28:31.338867Z"Can, Van Hao"https://zbmath.org/authors/?q=ai:can.van-hao"Trinh, Khanh Duy"https://zbmath.org/authors/?q=ai:trinh-khanh-duy.A random connection model (RCM) is a random graph whose vertices are given by a homogenous Poisson point process with density \(\lambda>0\) and in which the edges are independently drawn with probability \(\varphi\) depending on the locations of the two end points. The main goal of the paper is to study the asymptotic behavior of general functionals on the RCM for fixed parameters \(\lambda, \varphi\). In Theorem 1.1, the authors derive a central limit theorem for functionals \(f\) which are weakly stabilizing and which satisfy a particular moment condition. Importantly, this result implies central limit theorems for various interesting functionals such as subgraph counts, isomorphic component counts or the number of connected components. Furthermore, the authors derive central limit theorems for Betti numbers as well as for the size of the largest component.
Reviewer: Florian Pausinger (Belfast)Rare events in random geometric graphshttps://zbmath.org/1491.600432022-09-13T20:28:31.338867Z"Hirsch, Christian"https://zbmath.org/authors/?q=ai:hirsch.christian"Moka, Sarat B."https://zbmath.org/authors/?q=ai:moka.sarat-babu"Taimre, Thomas"https://zbmath.org/authors/?q=ai:taimre.thomas"Kroese, Dirk P."https://zbmath.org/authors/?q=ai:kroese.dirk-pSummary: This work introduces and compares approaches for estimating rare-event probabilities related to the number of edges in the random geometric graph on a Poisson point process. In the one-dimensional setting, we derive closed-form expressions for a variety of conditional probabilities related to the number of edges in the random geometric graph and develop conditional Monte Carlo algorithms for estimating rare-event probabilities on this basis. We prove rigorously a reduction in variance when compared to the crude Monte Carlo estimators and illustrate the magnitude of the improvements in a simulation study. In higher dimensions, we use conditional Monte Carlo to remove the fluctuations in the estimator coming from the randomness in the Poisson number of nodes. Finally, building on conceptual insights from large-deviations theory, we illustrate that importance sampling using a Gibbsian point process can further substantially reduce the estimation variance.Local-density dependent Markov processes on graphons with epidemiological applicationshttps://zbmath.org/1491.601302022-09-13T20:28:31.338867Z"Keliger, Dániel"https://zbmath.org/authors/?q=ai:keliger.daniel"Horváth, Illés"https://zbmath.org/authors/?q=ai:horvath.illes"Takács, Bálint"https://zbmath.org/authors/?q=ai:takacs.balint-mSummary: We investigate local-density dependent Markov processes on a class of large graphs sampled from a graphon, where the transition rates of the vertices are influenced by the states of their neighbors. We show that as the average degree converges to infinity (faster than a given threshold), the evolution of the process in the transient regime converges to the solution of a set of non-local integro-partial differential equations depending on the limit graphon. We also provide rigorous derivation for the epidemic threshold in the case of the Susceptible-Infected-Susceptible (SIS) process on such graphons.Age evolution in the mean field forest fire model via multitype branching processeshttps://zbmath.org/1491.601732022-09-13T20:28:31.338867Z"Crane, Edward"https://zbmath.org/authors/?q=ai:crane.edward"Ráth, Balázs"https://zbmath.org/authors/?q=ai:rath.balazs"Yeo, Dominic"https://zbmath.org/authors/?q=ai:yeo.dominicSummary: We study the distribution of ages in the mean field forest fire model introduced by \textit{B. Rath} and \textit{B. Toth} [Electron. J. Probab. 14, 1290--1327 (2009; Zbl 1197.60093)]. This model is an evolving random graph whose dynamics combine Erdős-Rényi edge-addition with a Poisson rain of \textit{lightning strikes}. All edges in a connected component are deleted when any of its vertices is struck by lightning. We consider the asymptotic regime of lightning rates for which the model displays self-organized criticality. The \textit{age} of a vertex increases at unit rate, but it is reset to zero at each burning time. We show that the empirical age distribution converges as a process to a deterministic solution of an autonomous measure-valued differential equation. The main technique is to observe that, conditioned on the vertex ages, the graph is an inhomogeneous random graph in the sense of \textit{B. Bollobàs} et al. [Random Struct. Algorithms 31, No. 1, 3--122 (2007; Zbl 1123.05083)]. We then study the evolution of the ages via the multitype Galton-Watson trees that arise as the limit in law of the component of an identified vertex at any fixed time. These trees are critical from the gelation time onwards.The wired arboreal gas on regular treeshttps://zbmath.org/1491.601742022-09-13T20:28:31.338867Z"Easo, Philip"https://zbmath.org/authors/?q=ai:easo.philipSummary: We study the weak limit of the arboreal gas along any exhaustion of a regular tree with wired boundary conditions. We prove that this limit exists, does not depend on the choice of exhaustion, and undergoes a phase transition. Below and at criticality, we prove the model is equivalent to bond percolation. Above criticality, we characterise the model as the superposition of critical bond percolation and a random collection of infinite one-ended paths. This provides a simple example of an arboreal gas model that continues to exhibit critical-like behaviour throughout its supercritical phase.On the computational tractability of statistical estimation on amenable graphshttps://zbmath.org/1491.620432022-09-13T20:28:31.338867Z"El Alaoui, Ahmed"https://zbmath.org/authors/?q=ai:el-alaoui.ahmed"Montanari, Andrea"https://zbmath.org/authors/?q=ai:montanari.andrea|montanari.andrea.1Summary: We consider the problem of estimating a vector of discrete variables \(\theta=(\theta_1,\dots ,\theta_n)\), based on noisy observations \(Y_{uv}\) of the pairs \((\theta_u,\theta_v)\) on the edges of a graph \(G=([n],E)\). This setting comprises a broad family of statistical estimation problems, including group synchronization on graphs, community detection, and low-rank matrix estimation. A large body of theoretical work has established sharp thresholds for weak and exact recovery, and sharp characterizations of the optimal reconstruction accuracy in such models, focusing however on the special case of Erdös-Rényi-type random graphs. An important finding of this line of work is the ubiquity of an information-computation gap. Namely, for many models of interest, a large gap is found between the optimal accuracy achievable by any statistical method, and the optimal accuracy achieved by known polynomial-time algorithms. Moreover, it is expected in many situations that this gap is robust to small amounts of additional side information revealed about the \(\theta_i\)'s. How does the structure of the graph \(G\) affect this picture? Is the information-computation gap a general phenomenon or does it only apply to specific families of graphs? We prove that the picture is dramatically different for graph sequences converging to amenable graphs (including, for instance, \(d\)-dimensional grids). We consider a model in which an arbitrarily small fraction of the vertex labels is revealed, and show that a linear-time local algorithm can achieve reconstruction accuracy that is arbitrarily close to the information-theoretic optimum. We contrast this to the case of random graphs. Indeed, focusing on group synchronization on random regular graphs, we prove that local algorithms are unable to have non-trivial performance below the so-called Kesten-Stigum threshold, even when a small amount of side information is revealed.Decay bounds for Bernstein functions of Hermitian matrices with applications to the fractional graph Laplacianhttps://zbmath.org/1491.650332022-09-13T20:28:31.338867Z"Schweitzer, Marcel"https://zbmath.org/authors/?q=ai:schweitzer.marcelSummary: For many functions of matrices \(f(A)\), it is known that their entries exhibit a rapid -- often exponential or even superexponential -- decay away from the sparsity pattern of the matrix \(A\). In this paper, we specifically focus on the class of Bernstein functions, which contains the fractional powers \(A^\alpha\), \(\alpha \in (0,1)\), as an important special case, and derive new decay bounds by exploiting known results for the matrix exponential in conjunction with the Lévy-Khintchine integral representation. As a particular special case, we find a result concerning the power law decay of the strength of connection in nonlocal network dynamics described by the fractional graph Laplacian, which improves upon known results from the literature by doubling the exponent in the power law.NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphshttps://zbmath.org/1491.680802022-09-13T20:28:31.338867Z"Loverov, Yaroslav Anatol'evich"https://zbmath.org/authors/?q=ai:loverov.yaroslav-anatolevich"Orlovich, Yuriĭ Leonidovich"https://zbmath.org/authors/?q=ai:orlovich.yurii-leonidovichSummary: It is known that the independent dominating set problem is NP-complete both in the class of cubic planar graphs and in the class of cubic bipartite graphs. The question about the computational complexity of the problem in the intersection of these graph classes has remained open. In this article, we prove that the independent dominating set problem is NP-complete in the class of cubic planar bipartite graphs.Vertex deletion problems on chordal graphshttps://zbmath.org/1491.680842022-09-13T20:28:31.338867Z"Cao, Yixin"https://zbmath.org/authors/?q=ai:cao.yixin"Ke, Yuping"https://zbmath.org/authors/?q=ai:ke.yuping"Otachi, Yota"https://zbmath.org/authors/?q=ai:otachi.yota"You, Jie"https://zbmath.org/authors/?q=ai:you.jieSummary: Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.
For the entire collection see [Zbl 1388.68010].Planar graph perfect matching is in NChttps://zbmath.org/1491.681312022-09-13T20:28:31.338867Z"Anari, Nima"https://zbmath.org/authors/?q=ai:anari.nima"Vazirani, Vijay V."https://zbmath.org/authors/?q=ai:vazirani.vijay-vObedient plane drawings for disk intersection graphshttps://zbmath.org/1491.681322022-09-13T20:28:31.338867Z"Banyassady, Bahareh"https://zbmath.org/authors/?q=ai:banyassady.bahareh"Hoffmann, Michael"https://zbmath.org/authors/?q=ai:hoffmann.michael-h-w|hoffmann.michael-j|hoffmann.michael-h-g"Klemz, Boris"https://zbmath.org/authors/?q=ai:klemz.boris"Löffler, Maarten"https://zbmath.org/authors/?q=ai:loffler.maarten"Miltzow, Tillmann"https://zbmath.org/authors/?q=ai:miltzow.tillmannSummary: Let \(\mathcal D\) be a set of disks and \(G\) be the intersection graph of \(\mathcal D\). A drawing of \(G\) is obedient to \(\mathcal D\) if every vertex is placed in its corresponding disk. We show that deciding whether a set of unit disks \(\mathcal D\) has an obedient plane straight-line drawing is \(\mathcal {NP}\)-hard regardless of whether a combinatorial embedding is prescribed or an arbitrary embedding is allowed. We thereby strengthen a result by Evans et al., who show \(\mathcal {NP}\)-hardness for disks with arbitrary radii in the arbitrary embedding case. Our result for the arbitrary embedding case holds true even if \(G\) is thinnish, that is, removing all triangles from \(G\) leaves only disjoint paths. This contrasts another result by Evans et al. stating that the decision problem can be solved in linear time if \(\mathcal D\) is a set of unit disks and \(G\) is thin, that is, (1) the (graph) distance between any two triangles is larger than 48 and (2) removal of all disks within (graph) distance 8 of a triangle leaves only isolated paths. A path in a disk intersection graph is isolated if for every pair \(A,B\) of disks that are adjacent along the path, the convex hull of \(A\cup B\) is intersected only by disks adjacent to \(A\) or \(B\). Our reduction can also guarantee the triangle separation property (1). This leaves only a small gap between tractability and \(\mathcal {NP}\)-hardness, tied to the path isolation property (2) in the neighborhood of triangles. It is therefore natural to study the impact of different restrictions on the structure of triangles. As a positive result, we show that an obedient plane straight-line drawing is always possible if all triangles in \(G\) are light and the disks are in general position (no three centers collinear). A triangle in a disk intersection graph is light if all its vertices have degree at most three or the common intersection of the three corresponding disks is empty. We also provide an efficient drawing algorithm for that scenario.
For the entire collection see [Zbl 1369.68023].Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphshttps://zbmath.org/1491.681352022-09-13T20:28:31.338867Z"Biedl, Therese"https://zbmath.org/authors/?q=ai:biedl.therese-c"Derka, Martin"https://zbmath.org/authors/?q=ai:derka.martinSummary: A \(B_2\)-VPG representation of a graph is an intersection representation that consists of orthogonal curves with at most 2 bends. In this paper, we show that the curves of such a representation can be partitioned into \(O(\log n)\) groups that represent outer-string graphs or \(O(\log ^3 n)\) groups that represent permutation graphs. This leads to better approximation algorithms for hereditary graph problems, such as independent set, clique and clique cover, on \(B_2\)-VPG graphs.
For the entire collection see [Zbl 1369.68023].Detecting an odd holehttps://zbmath.org/1491.681412022-09-13T20:28:31.338867Z"Chudnovsky, Maria"https://zbmath.org/authors/?q=ai:chudnovsky.maria"Scott, Alex"https://zbmath.org/authors/?q=ai:scott.alexander-d"Seymour, Paul"https://zbmath.org/authors/?q=ai:seymour.paul-d"Spirkl, Sophie"https://zbmath.org/authors/?q=ai:spirkl.sophie-theresaHardness of rainbow coloring hypergraphshttps://zbmath.org/1491.681442022-09-13T20:28:31.338867Z"Guruswami, Venkatesan"https://zbmath.org/authors/?q=ai:guruswami.venkatesan"Saket, Rishi"https://zbmath.org/authors/?q=ai:saket.rishiSummary: A hypergraph is \(k\)-rainbow colorable if there exists a vertex coloring using \(k\) colors such that each hyperedge has all the \(k\) colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be nearly balanced rainbow colorable. Specifically, we show that for any \(Q\), \(k\ge 2\) and \(\ell\le k/2\), given a \(Qk\)-uniform hypergraph which admits a \(k\)-rainbow coloring satisfying: \par in each hyperedge \(e\), for some \(\ell_e\le\ell\) all but \(2\ell_e\) colors occur exactly \(Q\) times and the rest \((Q\pm-1)\) times, \par it is NP-hard to compute an independent set of \((1-\frac{\ell+1}{k}+\varepsilon)\)-fraction of vertices, for any constant \(\varepsilon>0\). In particular, this implies the hardness of even \((k/\ell)\)-rainbow coloring such hypergraphs. \par The result is based on a novel long code PCP test that ensures the strong balancedness property desired of the \(k\)-rainbow coloring in the completeness case. The soundness analysis relies on a mixing bound based on uniform reverse hypercontractivity due to Mossel, Oleszkiewicz, and Sen, which was also used in earlier proofs of the hardness of \(\omega(1)\)-coloring 2-colorable 4-uniform hypergraphs due to Saket, and \(k\)-rainbow colorable \(2k\)-uniform hypergraphs due to Guruswami and Lee.
For the entire collection see [Zbl 1388.68010].Network construction with ordered constraintshttps://zbmath.org/1491.681452022-09-13T20:28:31.338867Z"Huang, Yi"https://zbmath.org/authors/?q=ai:huang.yi.5|huang.yi.2|huang.yi.6|huang.yi.7|huang.yi.9|huang.yi.4|huang.yi.3|huang.yi.8"Janardhanan, Mano Vikash"https://zbmath.org/authors/?q=ai:janardhanan.mano-vikash"Reyzin, Lev"https://zbmath.org/authors/?q=ai:reyzin.levSummary: In this paper, we study the problem of constructing a network by observing ordered connectivity constraints, which we define herein. These ordered constraints are made to capture realistic properties of real-world problems that are not reflected in previous, more general models. We give hardness of approximation results and nearly-matching upper bounds for the offline problem, and we study the online problem in both general graphs and restricted sub-classes. In the online problem, for general graphs, we give exponentially better upper bounds than exist for algorithms for general connectivity problems. For the restricted classes of stars and paths we are able to find algorithms with optimal competitive ratios, the latter of which involve analysis using a potential function defined over PQ-trees.
For the entire collection see [Zbl 1388.68010].Estimating latent feature-feature interactions in large feature-rich graphshttps://zbmath.org/1491.681672022-09-13T20:28:31.338867Z"Monti, Corrado"https://zbmath.org/authors/?q=ai:monti.corrado"Boldi, Paolo"https://zbmath.org/authors/?q=ai:boldi.paoloSummary: Real-world complex networks describe connections between objects; in reality, those objects are often endowed with some kind of features. How does the presence or absence of such features interplay with the network link structure? Although the situation here described is truly ubiquitous, there is a limited body of research dealing with large graphs of this kind. Many previous works considered homophily as the only possible transmission mechanism translating node features into links. Other authors, instead, developed more sophisticated models, that are able to handle complex feature interactions, but are unfit to scale to very large networks. We expand on the MGJ model, where interactions between pairs of features can foster or discourage link formation. In this work, we will investigate how to estimate the latent feature-feature interactions in this model. We shall propose two solutions: the first one assumes feature independence and it is essentially based on Naive Bayes; the second one, which relaxes the independence assumption assumption, is based on perceptrons. In fact, we show it is possible to cast the model equation in order to see it as the prediction rule of a perceptron. We analyze how classical results for the perceptrons can be interpreted in this context; then, we define a fast and simple perceptron-like algorithm for this task, which can process \(10^8\) links in minutes. We then compare these two techniques, first with synthetic datasets that follows our model, gaining evidence that the Naive independence assumptions are detrimental in practice. Secondly, we consider a real, large-scale citation network where each node (i.e., paper) can be described by different types of characteristics; there, our algorithm can assess how well each set of features can explain the links, and thus finding meaningful latent feature-feature interactions.Nonlinear weighted directed acyclic graph and a priori estimates for neural networkshttps://zbmath.org/1491.681842022-09-13T20:28:31.338867Z"Li, Yuqing"https://zbmath.org/authors/?q=ai:li.yuqing"Luo, Tao"https://zbmath.org/authors/?q=ai:luo.tao"Ma, Chao"https://zbmath.org/authors/?q=ai:ma.chaoOn colourability of polygon visibility graphshttps://zbmath.org/1491.682562022-09-13T20:28:31.338867Z"Çağirici, Onur"https://zbmath.org/authors/?q=ai:cagirici.onur"Hliněný, Petr"https://zbmath.org/authors/?q=ai:hlineny.petr"Roy, Bodhayan"https://zbmath.org/authors/?q=ai:roy.bodhayanSummary: We study the problem of colouring the visibility graphs of polygons. In particular, we provide a polynomial algorithm for 4-colouring of the polygon visibility graphs, and prove that the 6-colourability question is already NP-complete for them.
For the entire collection see [Zbl 1388.68010].Balanced line separators of unit disk graphshttps://zbmath.org/1491.682572022-09-13T20:28:31.338867Z"Carmi, Paz"https://zbmath.org/authors/?q=ai:carmi.paz"Chiu, Man Kwun"https://zbmath.org/authors/?q=ai:chiu.man-kwun"Katz, Matthew J."https://zbmath.org/authors/?q=ai:katz.matthew-j"Korman, Matias"https://zbmath.org/authors/?q=ai:korman.matias"Okamoto, Yoshio"https://zbmath.org/authors/?q=ai:okamoto.yoshio"van Renssen, André"https://zbmath.org/authors/?q=ai:van-renssen.andre"Roeloffzen, Marcel"https://zbmath.org/authors/?q=ai:roeloffzen.marcel"Shiitada, Taichi"https://zbmath.org/authors/?q=ai:shiitada.taichi"Smorodinsky, Shakhar"https://zbmath.org/authors/?q=ai:smorodinsky.shakharSummary: We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of \(n\) unit disks in the plane there exists a line \(\ell\) such that \(\ell\) intersects at most \(O(\sqrt{(m+n)\log {n}})\) disks and each of the halfplanes determined by \(\ell\) contains at most \(2\mathrm {n}/3\) unit disks from the set, where \(m\) is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting \(O(\sqrt{m+n})\) disks exists, but each halfplane may contain up to \(4\mathrm {n}/5\) disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in \(n\) exists when we look at disks of arbitrary radii, even when \(m=0\). Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size \(O(\sqrt{m})\)).
For the entire collection see [Zbl 1369.68023].Near-optimal approximate shortest paths and transshipment in distributed and streaming modelshttps://zbmath.org/1491.682642022-09-13T20:28:31.338867Z"Becker, Ruben"https://zbmath.org/authors/?q=ai:becker.ruben"Forster, Sebastian"https://zbmath.org/authors/?q=ai:forster.sebastian"Karrenbauer, Andreas"https://zbmath.org/authors/?q=ai:karrenbauer.andreas"Lenzen, Christoph"https://zbmath.org/authors/?q=ai:lenzen.christophApproximation algorithms for maximum weight \(k\)-coverings of graphs by packingshttps://zbmath.org/1491.682692022-09-13T20:28:31.338867Z"Gavril, Fanica"https://zbmath.org/authors/?q=ai:gavril.fanica"Shalom, Mordechai"https://zbmath.org/authors/?q=ai:shalom.mordechai"Zaks, Shmuel"https://zbmath.org/authors/?q=ai:zaks.shmuelThis paper is concerned with the design and analysis of approximation algorithms for a specialized maximum-weight covering by vertex packings.
Let \(\mathbf{GA}\) be a family of graphs and let \(\mathbf{J}\) be a set of connected graphs, each with at most \(r\) vertices, \(r\) fixed. A \(\mathbf{J}\)-packing of a graph \(G\) from \(\mathbf{GA}\) is a vertex-induced subgraph of \(G\) with every connected component isomorphic to a member of \(\mathbf{J}\). A maximum-weight \(k\)-covering of a graph \(G\) by \(\mathbf{J}\)-packings is a maximum-weight subgraph of \(G\) exactly covered by \(k\) vertex-disjoint \(\mathbf{J}\)-packings.
The main result of the paper is a \(1.582\) approximation algorithm for these coverings by packings. The algorithm is very general and can be applied in a whole host of settings.
The current algorithm is based on the greedy approach which has been discussed in the literature (for instance, see [\textit{D. S. Hochbaum} and \textit{A. Pathria}, Nav. Res. Logist. 45, No. 6, 615--627 (1998; Zbl 0938.90026)]). The strength of the algorithm is that it simultaneously solves a whole host of related maximum-weighted \(k\)-coveragings by packing problems.
The paper is well written and lucid. The arguments are clear and convincing. The authors have done a nice job of describing their work in the context of previous work.
Reviewer: K. Subramani (Morgantown)A near-linear time \(\varepsilon\)-approximation algorithm for geometric bipartite matchinghttps://zbmath.org/1491.682702022-09-13T20:28:31.338867Z"Raghvendra, Sharath"https://zbmath.org/authors/?q=ai:raghvendra.sharath"Agarwal, Pankaj K."https://zbmath.org/authors/?q=ai:agarwal.pankaj-kumarFully online matchinghttps://zbmath.org/1491.682712022-09-13T20:28:31.338867Z"Huang, Zhiyi"https://zbmath.org/authors/?q=ai:huang.zhiyi"Kang, Ning"https://zbmath.org/authors/?q=ai:kang.ning"Tang, Zhihao Gavin"https://zbmath.org/authors/?q=ai:tang.zhihao-gavin"Wu, Xiaowei"https://zbmath.org/authors/?q=ai:wu.xiaowei"Zhang, Yuhao"https://zbmath.org/authors/?q=ai:zhang.yuhao"Zhu, Xue"https://zbmath.org/authors/?q=ai:zhu.xueLee-Yang zeros of the antiferromagnetic Ising modelhttps://zbmath.org/1491.820042022-09-13T20:28:31.338867Z"Bencs, Ferenc"https://zbmath.org/authors/?q=ai:bencs.ferenc"Buys, Pjotr"https://zbmath.org/authors/?q=ai:buys.pjotr"Guerini, Lorenzo"https://zbmath.org/authors/?q=ai:guerini.lorenzo"Peters, Han"https://zbmath.org/authors/?q=ai:peters.hanSummary: We investigate the location of zeros for the partition function of the anti-ferromagnetic Ising model, focusing on the zeros lying on the unit circle. We give a precise characterization for the class of rooted Cayley trees, showing that the zeros are nowhere dense on the most interesting circular arcs. In contrast, we prove that when considering all graphs with a given degree bound, the zeros are dense in a circular sub-arc, implying that Cayley trees are in this sense not extremal. The proofs rely on describing the rational dynamical systems arising when considering ratios of partition functions on recursively defined trees.Uncovering the impact of delay phenomenon on random walks in a family of weighted \(m\)-triangulation networkshttps://zbmath.org/1491.820182022-09-13T20:28:31.338867Z"Guo, Junhao"https://zbmath.org/authors/?q=ai:guo.junhao"Wu, Zikai"https://zbmath.org/authors/?q=ai:wu.zikaiMathematics and network sciencehttps://zbmath.org/1491.900042022-09-13T20:28:31.338867Z"Sun, Jie"https://zbmath.org/authors/?q=ai:sun.jie|sun.jie.1|sun.jie.2For the entire collection see [Zbl 1483.68008].Computation of dynamic equilibria in series-parallel networkshttps://zbmath.org/1491.900262022-09-13T20:28:31.338867Z"Kaiser, Marcus"https://zbmath.org/authors/?q=ai:kaiser.marcusSummary: We consider dynamic equilibria for flows over time under the fluid queuing model. In this model, queues on the links of a network take care of flow propagation. Flow enters the network at a single source and leaves at a single sink. In a dynamic equilibrium, every infinitesimally small flow particle reaches the sink as early as possible given the pattern of the rest of the flow. Although this model has been examined for many decades, progress has been relatively recent. In particular, the derivatives of dynamic equilibria have been characterized as thin flows with resetting, which allows for more structural results. Our two main results are based on the formulation of thin flows with resetting as a linear complementarity problem and its analysis. We present a constructive proof of existence for dynamic equilibria if the inflow rate is right-monotone. The complexity of computing thin flows with resetting, which occurs as a subproblem in this method, is still open. We settle it for the class of two-terminal, series-parallel networks by giving a recursive algorithm that solves the problem for all flow values simultaneously in polynomial time.A value for cooperative games with coalition and probabilistic graph structureshttps://zbmath.org/1491.910132022-09-13T20:28:31.338867Z"Shi, Jilei"https://zbmath.org/authors/?q=ai:shi.jilei"Cai, Lei"https://zbmath.org/authors/?q=ai:cai.lei"Shan, Erfang"https://zbmath.org/authors/?q=ai:shan.erfang"Lyu, Wenrong"https://zbmath.org/authors/?q=ai:lyu.wenrongSummary: In this paper we generalize TU-games with coalition and graph structures to TU-games with coalition and probabilistic graph structures. We introduce the probabilistic graph-partition value and we show that the value is uniquely determined by the axioms of probabilistic graph efficiency, probabilistic balanced contributions and probabilistic collective balanced contributions and the axioms of probabilistic graph efficiency, probabilistic balanced contributions, probabilistic balanced per capita contributions and either probabilistic fairness for joining the grand coalition or probabilistic population solidarity within unions, respectively. Also, we apply this value to China's railway network and compare it with other values.The spread of cooperative strategies on grids with random asynchronous updatinghttps://zbmath.org/1491.910342022-09-13T20:28:31.338867Z"Duffy, Christopher"https://zbmath.org/authors/?q=ai:duffy.christopher"Janssen, Jeannette"https://zbmath.org/authors/?q=ai:janssen.jeannette-c-mSummary: The Prisoner's Dilemma Process on a graph \(G\) is an iterative process where each vertex, with a fixed strategy (\textit{cooperate} or \textit{defect}), plays the game with each of its neighbours. At the end of a round each vertex may change its strategy to that of its neighbour with the highest pay-off. Here we study the spread of cooperative and selfish behaviours on a toroidal grid, where each vertex is initially a cooperator with probability \(p\). When vertices are permitted to change their strategies via a randomized asynchronous update scheme, we find that for some values of \(p\) the limiting density of cooperators may be modelled as a polynomial in \(p\). Theoretical bounds for this density are confirmed via simulation.Linear quadratic graphon field gameshttps://zbmath.org/1491.910352022-09-13T20:28:31.338867Z"Gao, Shuang"https://zbmath.org/authors/?q=ai:gao.shuang"Tchuendom, Rinel Foguen"https://zbmath.org/authors/?q=ai:tchuendom.rinel-foguen"Caines, Peter E."https://zbmath.org/authors/?q=ai:caines.peter-eSummary: Linear quadratic graphon field games (LQ-GFGs) are defined to be linear quadratic games which involve a large number of agents that are weakly coupled via a weighted undirected graph on which each node represents an agent. The links of the graph correspond to couplings between the agents' dynamics, as well as between the individual cost functions, which each agent attempts to minimize. We formulate limit LQ-GFG problems based on the assumption that these graphs lie in a sequence which converges to a limit graphon. First, under a finite-rank assumption on the limit graphon, the existence and uniqueness of solutions to the formulated limit LQ-GFG problem is established. Second, based upon the solutions to the limit LQ-GFG problem, \(\varepsilon\)-Nash equilibria are constructed for the corresponding game problems with a very large but finite number of players. This result is then generalized to the case with random initial conditions. It is to be noted that LQ-GFG problems are distinct from the class of graphon mean field game (GMFG) problems where a population is hypothesized to be associated with each node of the graph [\textit{P. E. Caines} and \textit{M. Huang}, ``Graphon mean field games and the GMFG equations'', in: Proceedings of the 57th IEEE Conference on Decision and Control (CDC). Los Alamitos: IEEE Computer Society. 4129--4134 (2018); ``Graphon mean field games and the GMFG equations: \(\varepsilon\)-Nash equilibria'', in: Proceedings of the 58th IEEE Conference on Decision and Control (CDC). Los Alamitos: IEEE Computer Society. 286--292 (2019)].Capture times in the bridge-burning cops and robbers gamehttps://zbmath.org/1491.910362022-09-13T20:28:31.338867Z"Herrman, Rebekah"https://zbmath.org/authors/?q=ai:herrman.rebekah"van Hintum, Peter"https://zbmath.org/authors/?q=ai:van-hintum.peter"Smith, Stephen G. Z."https://zbmath.org/authors/?q=ai:smith.stephen-g-zSummary: In this paper, we consider a variant of the cops and robbers game on a graph, introduced by Kinnersley and Peterson, in which every time the robber uses an edge, it is removed from the graph, known as bridge-burning cops and robbers. In particular, we study the maximum time it takes the cops to capture the robber.Flow gameshttps://zbmath.org/1491.910372022-09-13T20:28:31.338867Z"Kupferman, Orna"https://zbmath.org/authors/?q=ai:kupferman.orna"Vardi, Gal"https://zbmath.org/authors/?q=ai:vardi.gal"Vardi, Moshe Y."https://zbmath.org/authors/?q=ai:vardi.moshe-ySummary: In the traditional maximal-flow problem, the goal is to transfer maximum flow in a network by directing, in each vertex in the network, incoming flow into outgoing edges. While the problem has been extensively used in order to optimize the performance of networks in numerous application areas, it corresponds to a setting in which the authority has control on all vertices of the network. Today's computing environment involves parties that should be considered adversarial. We introduce and study flow games, which capture settings in which the authority can control only part of the vertices. In these games, the vertices are partitioned between two players: the authority and the environment. While the authority aims at maximizing the flow, the environment need not cooperate. We argue that flow games capture many modern settings, such as partially-controlled pipe or road systems or hybrid software-defined communication networks. We show that the problem of finding the maximal flow as well as an optimal strategy for the authority in an acyclic flow game is \(\Sigma_2^P\)-complete, and is already \(\Sigma_2^P\)-hard to approximate. We study variants of the game: a restriction to strategies that ensure no loss of flow, an extension to strategies that allow non-integral flows, which we prove to be stronger, and a dynamic setting in which a strategy for a vertex is chosen only once flow reaches the vertex. We discuss additional variants and their applications, and point to several interesting open problems.
For the entire collection see [Zbl 1388.68010].The Hats game. On maximum degree and diameterhttps://zbmath.org/1491.910382022-09-13T20:28:31.338867Z"Latyshev, Aleksei"https://zbmath.org/authors/?q=ai:latyshev.aleksei"Kokhas, Konstantin"https://zbmath.org/authors/?q=ai:kokhas.konstantinSummary: We analyze the following version of the deterministic \textsc{Hats} game. We have a graph \(G\), and a sage resides at each vertex of \(G\). When the game starts, an adversary puts on the head of each sage a hat of a color arbitrarily chosen from a set of \(k\) possible colors. Each sage can see the hat colors of his neighbors but not his own hat color. All of sages are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. Given a graph \(G\), its hat guessing number \(\text{HG}(G)\) is the maximal number \(k\) such that there exists a winning strategy.
We disprove the hypothesis that \(\text{HG}(G) \leq \Delta + 1\) and demonstrate that diameter of graph and \(\text{HG}(G)\) are independent.Erratum to: ``A bounded-confidence model of opinion dynamics on hypergraphs''https://zbmath.org/1491.910962022-09-13T20:28:31.338867Z"Hickok, Abigail"https://zbmath.org/authors/?q=ai:hickok.abigail"Kureh, Yacoub"https://zbmath.org/authors/?q=ai:kureh.yacoub"Brooks, Heather Zinn"https://zbmath.org/authors/?q=ai:brooks.heather-zinn"Feng, Michelle"https://zbmath.org/authors/?q=ai:feng.michelle"Porter, Mason A."https://zbmath.org/authors/?q=ai:porter.mason-aErratum concerning the continuum model in Appendix A to the authors' paper [ibid. 21, No. 1, 1--32 (2022; Zbl 1482.91163)].Analysis of social networks and Wi-Fi networks by using the concept of picture fuzzy graphshttps://zbmath.org/1491.910972022-09-13T20:28:31.338867Z"Koczy, Laszlo T."https://zbmath.org/authors/?q=ai:koczy.laszlo-t"Jan, Naeem"https://zbmath.org/authors/?q=ai:jan.naeem"Mahmood, Tahir"https://zbmath.org/authors/?q=ai:mahmood.tahir"Ullah, Kifayat"https://zbmath.org/authors/?q=ai:ullah.kifayatSummary: Atanassov's intuitionistic fuzzy set described the uncertainty of real-life events with the help of a membership and a non-membership degree. However, human opinion cannot be restricted to yes or no, but there is some abstinence and refusal degree as well. In such cases, picture fuzzy set is a suitable solution which described the abstinence and refusal grade of human opinion along with membership and non-membership grades. The aim of this paper is to analyse a social network and a wife network using the concept of picture fuzzy graph (PFG). For this purpose, the concept of PFG is proposed and some basic terms are demonstrated including complement, degree and bridges. The main advantage of the proposed PFG is that it describes the uncertainty in any real-life event with the help of four membership degrees where the traditional FG and IFG fail to be applied. The viability of PFG is shown by utilizing the concept in demonstrating two real-life problems including a social network and a Wi-Fi-network. A comparison of PFG with existing notions is established showing its superiority over the existing frameworks.LNetReduce: tool for reducing linear dynamic networks with separated timescaleshttps://zbmath.org/1491.920602022-09-13T20:28:31.338867Z"Buffard, Marion"https://zbmath.org/authors/?q=ai:buffard.marion"Desoeuvres, Aurélien"https://zbmath.org/authors/?q=ai:desoeuvres.aurelien"Naldi, Aurélien"https://zbmath.org/authors/?q=ai:naldi.aurelien"Requilé, Clément"https://zbmath.org/authors/?q=ai:requile.clement"Zinovyev, Andrei"https://zbmath.org/authors/?q=ai:zinovyev.andrei"Radulescu, Ovidiu"https://zbmath.org/authors/?q=ai:radulescu.ovidiuSummary: We introduce LNetReduce, a tool that simplifies linear dynamic networks. Dynamic networks are represented as digraphs labeled by integer timescale orders. Such models describe deterministic or stochastic monomolecular chemical reaction networks, but also random walks on weighted protein-protein interaction networks, spreading of infectious diseases and opinion in social networks, communication in computer networks. The reduced network is obtained by graph and label rewriting rules and reproduces the full network dynamics with good approximation at all timescales. The tool is implemented in Python with a graphical user interface. We discuss applications of LNetReduce to network design and to the study of the fundamental relation between timescales and topology in complex dynamic networks.
\textit{Availability}: the code, documentation and application examples are available at \url{https://github.com/oradules/LNetReduce}.
For the entire collection see [Zbl 1486.92002].