Recent zbMATH articles in MSC 05Chttps://www.zbmath.org/atom/cc/05C2021-02-12T15:23:00+00:00WerkzeugEquilateral spherical drawings of planar Cayley graphs.https://www.zbmath.org/1452.051782021-02-12T15:23:00+00:00"Kang, Ming-Hsuan"https://www.zbmath.org/authors/?q=ai:kang.ming-hsuan"Lin, Wu-Hsiung"https://www.zbmath.org/authors/?q=ai:lin.wu-hsiungSummary: In this paper, we study equilateral spherical drawings of planar Cayley graphs. We focus on the case when the underlying group is generated by two rotations. In this case, the set of equilateral drawings can be parameterized by spherical ellipses on the unit sphere. Besides, we give an explicit formula to describe the shortest equilateral spherical drawing and the longest spherical equilateral drawing. Furthermore, we studied the drawing of Schreier coset graphs arising from these equilateral drawings.Minimal embedding dimensions of rectangle \(k\)-visibility graphs.https://www.zbmath.org/1452.051812021-02-12T15:23:00+00:00"Slettnes, Espen"https://www.zbmath.org/authors/?q=ai:slettnes.espenSummary: Bar visibility graphs were adopted in the 1980s as a model to represent traces, e.g., on circuit boards and in VLSI chip designs. Two generalizations of bar visibility graphs, rectangle visibility graphs and bar \(k\)-visibility graphs, were subsequently introduced.
Here, we combine bar \(k\)- and rectangle visibility graphs to form rectangle \(k\)-visibility graphs (R \(k\) VGs), and further generalize these to higher dimensions. A graph is a \(d\)-dimensional R \(k\) VG if and only if it can be represented with vertices as disjoint axis-aligned hyperrectangles in \(d\)-space, such that there is an axis-parallel line of sight between two hyperrectangles that intersects at most \(k\) other hyperrectangles if and only if there is an edge between the two corresponding vertices.
For any graph \(G\) and a fixed \(k\), we prove that given enough spatial dimensions, \(G\) has a rectangle \(k\)-visibility representation, and thus we define the minimal embedding dimension (MED) with \(k\)-visibility of \(G\) to be the smallest \(d\) such that \(G\) is a \(d\)-dimensional R \(k\) VG. We study the properties of MEDs and find upper bounds on the MEDs of various types of graphs. In particular, we find that the \(k\)-visibility MED of the complete graph on \(m\) vertices \(K_m\) is at most \(\lceil{m/(2(k+1))}\rceil,\) of complete \(r\)-partite graphs is at most \(r+1,\) and of the \(m^{\mathrm{th}}\) hypercube graph \(Q_m\) is at most \(\lceil{2m/3}\rceil\) in general, and at most \(\lfloor \sqrt{m} \rceil\) for \(k=0, m \neq 2\).Two results on layered pathwidth and linear layouts.https://www.zbmath.org/1452.051772021-02-12T15:23:00+00:00"Dujmović, Vida"https://www.zbmath.org/authors/?q=ai:dujmovic.vida"Morin, Pat"https://www.zbmath.org/authors/?q=ai:morin.pat"Yelle, Céline"https://www.zbmath.org/authors/?q=ai:yelle.celineSummary: Layered pathwidth is a new graph parameter studied by \textit{M. J. Bannister} et al. [Lect. Notes Comput. Sci. 9801, 499--510 (2016; Zbl 06687319)]. In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph \(G\), the stack number of \(G\) is at most four times the layered pathwidth of \(G\). Our second result shows that any graph \(G\) with track number at most three has layered pathwidth at most four. The first result complements a result of \textit{V. Dujmović} and \textit{F. Frati} [J. Graph Algorithms Appl. 22, No. 1, 89--99 (2018; Zbl 1377.05182)] relating layered treewidth and stack number. The second result solves an open problem posed by Bannister et al. [loc. cit.].Complexity of geometric \(k\)-planarity for fixed \(k\).https://www.zbmath.org/1452.051802021-02-12T15:23:00+00:00"Schaefer, Marcus"https://www.zbmath.org/authors/?q=ai:schafer.marcusSummary: The \textit{rectilinear local crossing number}, \(\overline{\mathrm{lcr}}(G)\), of a graph \(G\) is the smallest \(k\) so that \(G\) has a straight-line drawing with at most \(k\) crossings along each edge. We show that deciding whether \(\overline{\mathrm{lcr}}(G)\leq k\) for a fixed \(k\) is complete for the existential theory of the reals, \(\exists \mathbb{R}\).Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles.https://www.zbmath.org/1452.051792021-02-12T15:23:00+00:00"Kindermann, Philipp"https://www.zbmath.org/authors/?q=ai:kindermann.philipp"Montecchiani, Fabrizio"https://www.zbmath.org/authors/?q=ai:montecchiani.fabrizio"Schlipf, Lena"https://www.zbmath.org/authors/?q=ai:schlipf.lena"Schulz, André"https://www.zbmath.org/authors/?q=ai:schulz.andreSummary: We show that the \(1\)-planar slope number of \(3\)-connected cubic \(1\)-planar graphs is at most four when edges are drawn as polygonal curves with at most one bend each, that is, any such graph admits a drawing with at most one bend per edge and such that the number of distinct slopes used by the edge segments is at most four. This bound is obtained by drawings whose angular and crossing resolution is at least \(\pi/4\). On the other hand, if the embedding is fixed, then there is a \(3\)-connected cubic \(1\)-planar graph that needs three slopes when drawn with at most one bend per edge. We also show that two slopes always suffice for \(1\)-planar drawings of subcubic \(1\)-planar graphs with at most two bends per edge. This bound is obtained with angular resolution \(\pi/2\) and the drawing has crossing resolution \(\pi/2\) (i.e., it is a RAC drawing). Finally, we prove lower bounds for the slope number of straight-line \(1\)-planar drawings in terms of number of vertices and maximum degree.Pendant domination in graphs.https://www.zbmath.org/1452.051282021-02-12T15:23:00+00:00"Puttaswamy, Nayaka S. R."https://www.zbmath.org/authors/?q=ai:puttaswamy.nayaka-s-r"Purushothama, S."https://www.zbmath.org/authors/?q=ai:purushothama.sSummary: Let \(G\) be any graph. The concept of paired domination was introduced having guard backup concept in mind. We introduce pendant domination concept, for which at least one guard is assigned a backup. A dominating set \(S\) in \(G\) is called a pendant dominating set if \(\langle S\rangle\) contains at least one pendant vertex. The least cardinality of a pendant dominating set is called the pendant domination number of \(G\) denoted by \(\gamma_{pe}(G)\). In this article, we initiate the study of this parameter. The exact value of \(\gamma_{gd}(G)\) for some families of standard graphs are obtained and some bounds are estimated. We also study the properties of the parameter and interrelation with other invariants.The steerable graph Laplacian and its application to filtering image datasets.https://www.zbmath.org/1452.682532021-02-12T15:23:00+00:00"Landa, Boris"https://www.zbmath.org/authors/?q=ai:landa.boris"Shkolnisky, Yoel"https://www.zbmath.org/authors/?q=ai:shkolnisky.yoel\(P_3\)-forcing in honeycomb networks.https://www.zbmath.org/1452.051752021-02-12T15:23:00+00:00"Sujana, Jessy"https://www.zbmath.org/authors/?q=ai:sujana.jessy"Rajalaxmi, T. M."https://www.zbmath.org/authors/?q=ai:rajalaxmi.t-mSummary: In this paper we compute the \(P_3\)-forcing number of honeycomb network. A dynamic coloring of the vertices of a graph \(G\) starts with an initial subset \(S\) of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set \(S\) is called a forcing set of \(G\) if, by iteratively applying the forcing process, every vertex in \(G\) becomes colored. If the initial set \(S\) has the added property that it induces a subgraph of \(G\) whose components are all paths of length 3, then \(S\) is called a \(P_3\)-forcing set of \(G\). A \(P_3\)-forcing set of \(G\) of minimum cardinality is called the \(P_3\)-forcing number of \(G\) denoted by \(ZP_3(G)\).\(k\)-frugal list coloring of planar graphs without small cycles.https://www.zbmath.org/1452.050572021-02-12T15:23:00+00:00"Fang, Qiming"https://www.zbmath.org/authors/?q=ai:fang.qiming"Zhang, Li"https://www.zbmath.org/authors/?q=ai:zhang.li.9|zhang.li.2|zhang.li.11|zhang.li.4|zhang.li.1|zhang.li.6|zhang.li.3|zhang.li|zhang.li.7|zhang.li.5|zhang.li.8|zhang.li.10|zhang.li.12"Chen, Ming"https://www.zbmath.org/authors/?q=ai:chen.mingSummary: A graph \(G\) is \(k\)-frugal colorable if there exists a proper vertex coloring of \(G\) such that every color appears at most \(k-1\) times in the neighborhood of \(v\). The \(k\)-frugal chromatic number, denoted by \(\chi_k(G)\), is the smallest integer \(l\) such that \(G\) is \(k\)-frugal colorable with \(l\) colors. A graph \(G\) is \(L\)-list colorable if there exists a coloring \(c\) of \(G\) for a given list assignment \(L=\{L(v):v\in V(G)\}\) such that \(c(v)\in L(v)\) for all \(v\in V(G)\). If \(G\) is \(k\)-frugal \(L\)-colorable for any list assignment \(L\) with \(|L(v)|\ge l\) for all \(v\in V(G)\), then \(G\) is said to be \(k\)-frugal \(l\)-list-colorable. The smallest integer \(l\) such that the graph \(G\) is \(k\)-frugal \(l\)-list-colorable is called the \(k\)-frugal list chromatic number, denoted by \(\operatorname{ch}_k(G)\). It is clear that \(\operatorname{ch}_k(G)\ge\left\lceil\frac{\Delta(G)}{k-1}\right\rceil+1\) for any graph \(G\) with maximum degree \(\Delta(G)\). In this paper, we prove that for any integer \(k\ge 4\), if \(G\) is a planar graph with maximum degree \(\Delta(G)\ge 13k-11\) and girth \(g\ge 6\), then \(\operatorname{ch}_k(G)=\left\lceil\frac{\Delta(G)}{k-1}\right\rceil+1\); and if \(G\) is a planar graph with girth \(g\ge 6\), then \(\operatorname{ch}_k(G)=\left\lceil \frac{\Delta(G)}{k-1}\right\rceil+2\).Wiener and Zagreb indices for line graphs.https://www.zbmath.org/1452.050382021-02-12T15:23:00+00:00"Senbagamalar, J."https://www.zbmath.org/authors/?q=ai:senbagamalar.jaisankar"Babujee, Baskar"https://www.zbmath.org/authors/?q=ai:babujee.baskar-jSummary: The line graph \(L(G)\) of a connected graph \(G\), has vertex set identical with the set of edges of \(G\), and two vertices of \(L(G)\) are adjacent if and only if the corresponding edges are adjacent in \(G\). Ivan Gutman et al. examined the dependency of certain physio-chemical properties of alkanes in boiling point, molar volume, and molar refraction, heat of vapourization, critical temperature, critical pressure and surface tension on the Bertz indices of \(L^i(G)\). A. A. Dobrynin and L. S. Melnikov conjectured that there exists a no nontrivial tree \(T\) and \(i\ge 3\), such that \(W(L^i(T))=W(T)\). In this paper we study Wiener and Zagreb indices for line graphs of complete graph, complete bipartite graph and wheel graph.Power domination in certain nanotori.https://www.zbmath.org/1452.051162021-02-12T15:23:00+00:00"Anitha, J."https://www.zbmath.org/authors/?q=ai:anitha.jSummary: A set \(S\) of vertices in a graph \(G\) is called a dominating set of \(G\) if every vertex in \(V(G)\setminus S\) is adjacent to some vertex in \(S\). A set \(S\) is said to be a power dominating set of \(G\) if every vertex in the system is monitored by the set \(S\) following a set of rules for power system monitoring. The power domination number of \(G\) is the minimum cardinality of a power dominating set of \(G\). In this paper, we solve the power domination number for certain nanotori such as \(H\)-naphtelanic, \(C_5C_6C_7[m,n]\) nanotori and \(C_4C_6C_8[m,n]\) nanotori.Trees and unicyclic graphs with large fair domination number.https://www.zbmath.org/1452.051212021-02-12T15:23:00+00:00"Hajian, Majid"https://www.zbmath.org/authors/?q=ai:hajian.majid"Rad, Nader Jafari"https://www.zbmath.org/authors/?q=ai:jafari-rad.naderSummary: A fair dominating set (FD-set) in a graph \(G\) is a dominating set \(S\) such that all vertices not in \(S\) are dominated by the same number of vertices from \(S\). The fair domination number of \(G\), denoted \(fd(G)\), is the minimum cardinality of an FD-set of \textit{Y. Caro} et al. [Discrete Math. 312, No. 19, 2905--2914 (2012; Zbl 1251.05121)] showed that \(fd(T)\le n/2\) for any tree \(T\) of order \(n\ge 2\), and characterized all trees \(T\) of order \(n\) with \(fd(T)=n/2\). We first characterize all trees \(T\) of order \(n\) with \(fd(T)=\lfloor n/2\rfloor\). We then prove that \(fd(G)\le(n+1)/2\) for any unicyclic graph \(G\) of order \(n\), and characterize all unicyclic graphs \(G\) of order \(n\) with \(fd(G)=(n+1)/2\).Construction of non-isomorphic families of Halin graphs with same split domination numbers.https://www.zbmath.org/1452.051272021-02-12T15:23:00+00:00"Priyadharshini, M."https://www.zbmath.org/authors/?q=ai:priyadharshini.m"Anandhababu, D."https://www.zbmath.org/authors/?q=ai:anandhababu.d"Anuradha, A."https://www.zbmath.org/authors/?q=ai:anuradha.arumugamSummary: Split domination number of a graph is the cardinality of a minimum dominating set whose removal disconnects the graph. In this paper, we define a special family of Halin graphs and determine the split domination number of those graphs. We show that the construction yield non-isomorphic families of Halin graphs but with same split domination numbers.On the nonsplit monophonic number of a graph.https://www.zbmath.org/1452.050502021-02-12T15:23:00+00:00"Mahendran, M."https://www.zbmath.org/authors/?q=ai:mahendran.m"Swathy, G."https://www.zbmath.org/authors/?q=ai:swathy.gSummary: In this paper, we introduced a new concept called nonsplit monophonic set and its relative parameter nonsplit monophonic number \(m_{ns}(G)\). Some certain properties of nonsplit monophonic sets are discussed. The nonsplit monophonic number of standard graphs are investigated. Some existence theorems on nonsplit monophonic number are established.Generalized Wiener indices of double silicate chain graph.https://www.zbmath.org/1452.050342021-02-12T15:23:00+00:00"Kaladevi, V."https://www.zbmath.org/authors/?q=ai:kaladevi.v"Anuradha, R."https://www.zbmath.org/authors/?q=ai:anuradha.rohatgi"Abinayaa, A."https://www.zbmath.org/authors/?q=ai:abinayaa.aSummary: In this paper, the distance and degree based topological indices for double silicate chain graph are obtained.Class of weighted graphs with strong anti-reciprocal eigenvalue property.https://www.zbmath.org/1452.051002021-02-12T15:23:00+00:00"Ahmad, Uzma"https://www.zbmath.org/authors/?q=ai:ahmad.uzma"Hameed, Saira"https://www.zbmath.org/authors/?q=ai:hameed.saira"Jabeen, Shaista"https://www.zbmath.org/authors/?q=ai:jabeen.shaistaSummary: Let \(G\) be a graph with a unique perfect matching and \(W(G)\) be the collection of all positive weight functions defined on the edge set of \(G\) such that each weight function assigns weight 1 to each matching edge and a positive weight to each non-matching edge of \(G\). Given \(w\in W(G)\), let \(G_w\) denote the weighted graph obtained from \(G\) corresponding to the weight function \(w\). Let \(A(G_w)\) denote the adjacency matrix of \(G_w\). We say \(G_w\) satisfies the anti-reciprocal eigenvalue property (property \((-\)R)) if for each eigenvalue \(\lambda\) of \(A(G_w)\), its anti-reciprocal \(-1/\lambda\) is also an eigenvalue of \(A(G_w)\). Furthermore, if \(\lambda\) and \(-1/\lambda\) have the same multiplicities, then we say \(G_w\) satisfies the strong anti-reciprocal eigenvalue property (property \((-\)SR)). In this paper, the graphs with property \((-\) SR) in the class of graphs with unique perfect matching are investigated and it is shown that a weighted graph \(G_w\) with a unique perfect matching satisfies property \((-\)SR) for each \(w\in W(G)\) if and only if it is a corona graph.Embedding complete bipartite graph into sibling trees with optimum wirelength.https://www.zbmath.org/1452.050492021-02-12T15:23:00+00:00"Greeni, A. Berin"https://www.zbmath.org/authors/?q=ai:greeni.a-berinSummary: In this paper, we determine the wirelength of embedding complete bipartite graphs \(K_{2^{n-1},2^{n-1}}\) into the 1-rooted sibling tree \(ST^1_n\) and the Cartesian product of 1-rooted sibling trees and paths.Dominator coloring changing and stable graphs upon vertex removal.https://www.zbmath.org/1452.051132021-02-12T15:23:00+00:00"Abid, A. Mohammed"https://www.zbmath.org/authors/?q=ai:abid.a-mohammed"Rao, T. R. Ramesh"https://www.zbmath.org/authors/?q=ai:ramesh-rao.t-rSummary: A dominator coloring is a proper vertex coloring of a graph \(G\) such that each vertex is adjacent to all the vertices of at least one color class or either alone in its color class. The minimum cardinality among all dominator coloring of \(G\) is a dominator chromatic number of \(G\), denoted by \(\chi_d(G)\). On removal of a vertex the dominator chromatic number may increase or decrease or remain unaltered. In this paper, we have characterized nontrivial trees for which dominator chromatic number is stable.Edge connectivity, packing spanning trees, and eigenvalues of graphs.https://www.zbmath.org/1452.051012021-02-12T15:23:00+00:00"Duan, Cunxiang"https://www.zbmath.org/authors/?q=ai:duan.cunxiang"Wang, Ligong"https://www.zbmath.org/authors/?q=ai:wang.ligong"Liu, Xiangxiang"https://www.zbmath.org/authors/?q=ai:liu.xiangxiangSummary: Let \(\mathcal{G}\) be the set of simple graphs (or multigraphs) \(G\) such that for each \(G\in\mathcal{G}\) there exists at least two non-empty disjoint proper subsets \(V_1, V_2\subseteq V(G)\) satisfying \(V(G)\backslash(V_1\cup V_2)\neq\emptyset\) and edge connectivity \(\kappa^\prime(G)=e(V_i, V(G)\backslash V_i)\) for \(1\leq i\leq 2\). A multigraph is a graph with possible multiple edges, but no loops. Let \(\tau(G)\) be the maximum number of edge-disjoint spanning trees of a graph \(G\). Motivated by a question of Seymour on the relationship between eigenvalues of a graph \(G\) and bounds of \(\tau(G)\), we mainly give the relationship between the third largest (signless Laplacian) eigenvalue and the bounds of \(\kappa^\prime(G)\) and \(\tau(G)\) of a simple graph or a multigraph \(G\in\mathcal{G}\), respectively.Classification of regular maps of prime characteristic revisited: avoiding the Gorenstein-Walter theorem.https://www.zbmath.org/1452.050802021-02-12T15:23:00+00:00"Conder, Marston"https://www.zbmath.org/authors/?q=ai:conder.marston-d-e"Širáň, Jozef"https://www.zbmath.org/authors/?q=ai:siran.jozefSummary: \textit{A. Breda d'Azevedo} et al. [Trans. Am. Math. Soc. 357, No. 10, 4175--4190 (2005; Zbl 1065.05033)] classified the regular maps on surfaces of Euler characteristic \(- p\) for every prime \(p\). This classification relies on three key theorems, each proved using the highly non-trivial characterisation of finite groups with dihedral Sylow 2-subgroups, due to \textit{D. Gorenstein} and \textit{J. H. Walter} [J. Algebra 2, 85--151, 218--270 (1965; Zbl 0192.11902); ibid. 2, 354--393 (1965; Zbl 0192.12001)]. Here we give new proofs of those three facts (and hence the entire classification) using somewhat more elementary group theory, without referring to the Gorenstein-Walter theorem.A panorama of positivity. II: Fixed dimension.https://www.zbmath.org/1452.150212021-02-12T15:23:00+00:00"Belton, Alexander"https://www.zbmath.org/authors/?q=ai:belton.alexander-c-r"Guillot, Dominique"https://www.zbmath.org/authors/?q=ai:guillot.dominique"Khare, Apoorva"https://www.zbmath.org/authors/?q=ai:khare.apoorva"Putinar, Mihai"https://www.zbmath.org/authors/?q=ai:putinar.mihaiThis second part of the survey on positivity presents ``a selection of topics unified by the concept of positive semidefiniteness (of matrices or kernels), reflecting natural constraints imposed on discrete data (graphs or networks) or continuous objects (probability or mass distributions).'' A special emphasis is given to operations which preserve positivity. Many techniques from harmonic analysis, function theory, operator theory, statistics, combinatorics, and group representations are used. With comments and full bibliographical references some partially forgotten classical roots in metric geometry and distance transforms are reminded. Some modern applications to high-dimensional covariance estimation and regularisation are added.
For Part I see [the authors, in: Analysis of operators on function spaces. The Serguei Shimorin memorial volume. Including extended versions of lectures of the conference in honor of the memory of Serguei Shimorin at the Mittag-Leffler Institute, Stockholm, Sweden in the summer of 2018. Cham: Springer. 117--165 (2019; Zbl 07121791)].
For the entire collection see [Zbl 1444.30001].
Reviewer: Mihail Voicu (Iaşi)Tau invariants for balanced spatial graphs.https://www.zbmath.org/1452.570212021-02-12T15:23:00+00:00"Vance, Katherine"https://www.zbmath.org/authors/?q=ai:vance.katherineOn matching integral graphs.https://www.zbmath.org/1452.050912021-02-12T15:23:00+00:00"Ghezelahmad, Somayeh Khalashi"https://www.zbmath.org/authors/?q=ai:ghezelahmad.somayeh-khalashiSummary: The matching polynomial of a graph has coefficients that give the number of matchings in the graph. In this paper, we determine all connected graphs on eight vertices whose matching polynomials have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We show that there are exactly two matching integral graphs on eight vertices.Edge graceful labeling of Paley digraph.https://www.zbmath.org/1452.051632021-02-12T15:23:00+00:00"Parameswari, R."https://www.zbmath.org/authors/?q=ai:parameswari.r"Rajeswari, R."https://www.zbmath.org/authors/?q=ai:rajeswari.raja-r|rajeswari.r-rajaSummary: A digraph \(G\) is finite and is denoted as \(G(V,E)\) with \(V\) as set of nodes and \(E\) as set of directed arcs which is exact. If \((u,v)\) is an arc in a digraph \(D\), we say vertex \(u\) dominates vertex \(v\). A special digraph arises in round robin tournaments. Tournaments with a special quality \(Q(n,k)\) have been studied by \textit{W. Ananchuen} and \textit{L. Caccetta} [Discrete Math. 306, No. 22, 2954--2961 (2006; Zbl 1107.05078)]. \textit{R. L. Graham} and \textit{J. H. Spencer} [Can. Math. Bull. 14, 45--48 (1971; Zbl 0209.55804)] defined tournament with \(q\) vertices where \(q\equiv 3 \pmod 4\) is a prime. It was named suitably as Paley digraphs in respect deceased Raymond Paley, he was the person used quadratic residues to construct Hadamard matrices more than 50 years earlier. This article is based on a special class of graph called Paley digraph which admits odd edge graceful, super edge graceful and strong edge graceful labeling.Transversal total domination in graphs.https://www.zbmath.org/1452.051252021-02-12T15:23:00+00:00"Nayaka, S. R."https://www.zbmath.org/authors/?q=ai:nayaka.s-r-nayaka-abhill-gmail-com"Alwardi, Anwar"https://www.zbmath.org/authors/?q=ai:alwardi.anwar"Puttaswamy"https://www.zbmath.org/authors/?q=ai:puttaswamy.t-k|puttaswamy.nayaka-s-rSummary: Let \(G=(V,E)\) be a graph. A total dominating set of \(G\) which intersects every minimum total dominating set in \(G\) is called a transversal total dominating set. The minimum cardinality of a transversal total dominating set is called the transversal total domination number of \(G\), denoted by \(\gamma_{tt}(G)\). In this paper, we begin to study this parameter. We calculate \(\gamma_{tt}(G)\) for some families of graphs. Further some bounds and relations with other domination parameters are obtained for \(\gamma_{tt}(G)\).On the complexity of digraph colourings and vertex arboricity.https://www.zbmath.org/1452.050612021-02-12T15:23:00+00:00"Hochstättler, Winfried"https://www.zbmath.org/authors/?q=ai:hochstattler.winfried"Schröder, Felix"https://www.zbmath.org/authors/?q=ai:schroder.felix"Steiner, Raphael"https://www.zbmath.org/authors/?q=ai:steiner.raphaelThis work is about computational complexity of several problems connected with colorings of digraphs. It is shown that the following problems are NP-complete: i) star dichromatic number, ii) fractional dichromatic number and iii) circular vertex arboricity.
The approach to the three mentioned problems differs a lot and in particular in the case of the first problem new kind of homomorphisms were used, called circular homomorphisms.
The work contains a nice introduction that guides the reader through the history of the problems and their connection to graph analogues.
Reviewer: Iztok Peterin (Maribor)Distance matrix of a class of completely positive graphs: determinant and inverse.https://www.zbmath.org/1452.050472021-02-12T15:23:00+00:00"Das, Joyentanuj"https://www.zbmath.org/authors/?q=ai:das.joyentanuj"Jayaraman, Sachindranath"https://www.zbmath.org/authors/?q=ai:jayaraman.sachindranath"Mohanty, Sumit"https://www.zbmath.org/authors/?q=ai:mohanty.sumitSummary: A real symmetric matrix \(A\) is said to be completely positive if it can be written as \(BB^t\) for some (not necessarily square) nonnegative matrix \(B\). A simple graph \(G\) is called a completely positive graph if every matrix realization of \(G\) that is both nonnegative and positive semidefinite is a completely positive matrix. Our aim in this manuscript is to compute the determinant and inverse (when it exists) of the distance matrix of a class of completely positive graphs. We compute a matrix \(\mathcal{R}\) such that the inverse of the distance matrix of a class of completely positive graphs is expressed a linear combination of the Laplacian matrix, a rank one matrix of all ones and \(\mathcal{R} \). This expression is similar to the existing result for trees. We also bring out interesting spectral properties of some of the principal submatrices of \(\mathcal{R} \).From light edges to strong edge-colouring of 1-planar graphs.https://www.zbmath.org/1452.050532021-02-12T15:23:00+00:00"Bensmail, Julien"https://www.zbmath.org/authors/?q=ai:bensmail.julien"Dross, François"https://www.zbmath.org/authors/?q=ai:dross.francois"Hocquard, Hervé"https://www.zbmath.org/authors/?q=ai:hocquard.herve"Sopena, Eric"https://www.zbmath.org/authors/?q=ai:sopena.ericLet \(G=(V,E)\) be a simple connected graph. The distance between vertices \(u, v \in V(G)\) is the length of a shortest \(u, v\)-path, i.e. the number of edges on a shortest path between \(u\) and \(v\). If \(e=ab \in E(G)\) and \(u \in V(G)\), we say that
a \(u,a\)-path and \(u,b\)-path are also \(e,u\)-paths. The distance between \(e\) and \(u\) is then defined as the minimum number of edges on a shortest \(e,u\)-path. Let \(e=ab \in E(G)\) and \(f =uv\in E(G)\). Then the distance between \(e\) and \(f\) is the minimum number of edges along a shortest \(e, u\)-path or a shortest \(e, v\)-path.
A strong edge-coloring of \(G\) is an edge-coloring of \(G\) where any two edges of \(G\) which are at a distance at most two are assigned different colors. Note that a strong edge-coloring \(c\) of a \(G\) implies that every color class of \(c\) is an induced matching. The strong chromatic index of \(G\) is the minimum number of colors in a strong edge-coloring of \(G\).
The paper considers the strong chromatic index of 1-planar graphs, i.e., graphs that can be drawn on the plane so that every edge is crossed at most once. Inspired by the Erdős-Nešetřil conjecture on the strong chromatic index of graphs with some maximum degree, the authors study the strong chromatic index of 1-planar graphs with maximum degree \(\Delta\). It is shown that the upper bound on the strong chromatic index of this class of graph is linear in \(\Delta\). This result is provided by the fact that a 1-planar graph with a minimum degree at least three admits a light edge, i.e., an edge whose end-vertices degrees are bounded by a constant.
Reviewer: Aleksander Vesel (Maribor)Zero-nonzero patterns that allow or require an inertia set related to dynamical systems.https://www.zbmath.org/1452.150192021-02-12T15:23:00+00:00"Gao, Wei"https://www.zbmath.org/authors/?q=ai:gao.wei"Shao, Yanling"https://www.zbmath.org/authors/?q=ai:shao.yanlingAuthors' abstract: The inertia of an \(n\times n\) real matrix \(B\), denoted by \(i(B)\), is the ordered triple \(i(B) = (i_+(B), i_{-}(B); i_0(B)),\)
in which \(i_+(B), i_-(B)\) and \(i_0(B)\) are the numbers of its eigenvalues (counting multiplicities) with positive, negative and zero real parts, respectively. The inertia of an \(n\times n\) zero-nonzero pattern \(A\) is the set \(i(A) = \{i(B) \mid B \in Q(A)\}\). For \(n\ge 2\), let \(S_n^* = \{(0, n, 0), (0, n -1,1), (1, n - 1, 0), (n, 0, 0), (n - 1, 0, 1), (n -1, 1, 0)\}\). An \(n\times n\) zero-nonzero pattern \(A\) allows \(S_n^*\) if \(S_n^*\subseteq i(A)\) and requires \(S_n^*= i(A)\). In this paper, it is shown that there are no zero-nonzero patterns for order \(n\ge 2\) that require \(S_n^*\). Also, a complete characterization of zero-nonzero star patterns of order \(n\ge 3\) that allow \(S_n^*\) is given.
Reviewer: Yansheng Wu (Nanjing)Perfect 2-coloring of the quartic graphs with order at most 8.https://www.zbmath.org/1452.050592021-02-12T15:23:00+00:00"Golzadeh, Yazdan"https://www.zbmath.org/authors/?q=ai:golzadeh.yazdan"Alaeiyan, Mehdi"https://www.zbmath.org/authors/?q=ai:alaeiyan.mehdi"Gilani, Alireza"https://www.zbmath.org/authors/?q=ai:gilani.alirezaSummary: In this paper, we study perfect 2-coloring of the quartic graphs with at most 8 vertices. The problem of the existence of perfect coloring is a generalization of the concept of completely regular codes, given by Delsarte.Description of the triangle-free prime graphs having at most two non critical vertices.https://www.zbmath.org/1452.051512021-02-12T15:23:00+00:00"Boudabbous, Imed"https://www.zbmath.org/authors/?q=ai:boudabbous.imed"Marweni, Walid"https://www.zbmath.org/authors/?q=ai:marweni.walidSummary: In a graph \(G=(V,E)\), a module is a vertex subset \(M\) such that every vertex outside \(M\) is adjacent to all or none of \(M\). For example, \(\emptyset\), \(\{x\}\) \((x\in V)\) and \(V\) are modules of \(G\), called trivial modules. A graph, all the modules of which are trivial, is prime; otherwise, it is decomposable. A vertex \(x\) of a prime graph \(G\) is critical if \(G-x\) is decomposable. We generalize this definition. A prime graph \(G=(V,E)\) is \(X\)-critical, where \(X\) is a subset of \(V\), if for each \(x\in X\), \(x\) is a critical vertex. Moreover, \(G\) is \((-k)\)-\textit{critical}, where \(0\leq k\leq |V|\), if \(G\) is \((V\backslash X)\)-critical for some subset \(X\) of \(V\) such that \(|X|=k\). In [Discrete Math. 113, No. 1--3, 191--205 (1993; Zbl 0776.06002)], \textit{J. H. Schmerl} and \textit{W. T. Trotter} characterized the \(V\)-critical graphs, called critical graphs with vertex set \(V\). Recently, \textit{H. Belkhechine} et al. [Ars Comb. 119, 293--319 (2015; Zbl 1349.05139)] characterized the \((-1)\)-critical graphs. In this paper, we characterize the \((-k)\)-critical graphs within the family of triangle-free graphs where \(k\leq 2\).A graph approach for fuzzy-rough feature selection.https://www.zbmath.org/1452.682032021-02-12T15:23:00+00:00"Chen, Jinkun"https://www.zbmath.org/authors/?q=ai:chen.jinkun"Mi, Jusheng"https://www.zbmath.org/authors/?q=ai:mi.jusheng"Lin, Yaojin"https://www.zbmath.org/authors/?q=ai:lin.yaojinSummary: Rough sets, especially fuzzy-rough sets, have proven to be a powerful tool for dealing with vagueness and uncertainty in data analysis. Fuzzy-rough feature selection has been shown to be highly useful in data dimensionality reduction. However, many fuzzy-rough feature selection algorithms are still time-consuming when dealing with the large-scale data sets. In this paper, the problem of feature selection in fuzzy-rough sets is studied in the framework of graph theory. We propose a new mechanism for fuzzy-rough feature selection. It is shown that finding the attribute reduction of a fuzzy decision system can be translated into finding the transversal of a derivative hypergraph. Based on the graph-representation model, a novel graph-theoretic algorithm for fuzzy-rough feature selection is proposed. The performance of the proposed method is compared with those of the state-of-the-art methods on various classification tasks. Experimental results show that the proposed technique outperforms all other known feature selection methods in terms of the computation time. Especially for the large-scale data sets, it demonstrates promising performance. Moreover, our proposed method can achieve better classification accuracies with the usage of small number of features.The harmonic index of graphs based on some operations related to the lexicographic product.https://www.zbmath.org/1452.050242021-02-12T15:23:00+00:00"Onagh, B. N."https://www.zbmath.org/authors/?q=ai:onagh.bibi-naimehSummary: The harmonic index of a graph \(G\) is defined as the sum of the weights \(\frac{2}{\deg_G(u)+\deg_G(v)}\) of all edges \(uv\) of \(G\), where \(\deg_G(u)\) denotes the degree of a vertex \(u\) in \(G\). In this paper, we investigate the harmonic index of graphs based on operations related to the lexicographic product, subdivision graph, \(t\)-subdivision graph, vertex-semitotal graph, edge-semitotal graph and total graph.What percent of the plane can be properly 5- and 6-colored?https://www.zbmath.org/1452.050692021-02-12T15:23:00+00:00"Parts, Jaan"https://www.zbmath.org/authors/?q=ai:parts.jaanSummary: We present a tiling of more than 99.985698\% of the Euclidean plane with six colors, reducing the previous record for uncovered fraction of the plane by about 12.8\%. We also present a tiling of more than 95.99\% of the plane with five colors. It is thus shown that any unit-distance graph of order at most 6992 and 24 in the plane can be properly 6-colored and 5-colored, respectively.A small 6-chromatic unit-distance graph in \(\mathbb{R}^3\).https://www.zbmath.org/1452.050552021-02-12T15:23:00+00:00"de Grey, Aubrey"https://www.zbmath.org/authors/?q=ai:de-grey.aubrey-d-n-jSummary: We present a 6-chromatic graph that can be embedded in \(\mathbb{R}^3\) in such a way that all neighbouring pairs of vertices are at distance exactly 1. Our graph has 59 vertices, fewer than for any other such graph of which we are aware.Enumeration of caterpillars.https://www.zbmath.org/1452.050902021-02-12T15:23:00+00:00"Murugan, V."https://www.zbmath.org/authors/?q=ai:murugan.v-vel|murugan.veerapazham"Sethuraman, G."https://www.zbmath.org/authors/?q=ai:sethuraman.gSummary: \textit{F. Harary} and \textit{A. J. Schwenk} [Discrete Math. 6, 359--365 (1973; Zbl 0266.05102)] have given a formula for counting the number of non-isomorphic caterpillars on \(n\) vertices with \(n\ge 3\). Inspired by the formula of Harary and Schwenk [loc. cit.], in this paper, we give a formula for counting the number of non-isomorphic caterpillars with the same degree sequence.Fully dynamic arboricity maintenance.https://www.zbmath.org/1452.681302021-02-12T15:23:00+00:00"Banerjee, Niranka"https://www.zbmath.org/authors/?q=ai:banerjee.niranka"Raman, Venkatesh"https://www.zbmath.org/authors/?q=ai:raman.venkatesh"Saurabh, Saket"https://www.zbmath.org/authors/?q=ai:saurabh.saketThe arboricity of a graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges is defined as the minimum number of edge-disjoint forests that the edges of the graph can be partitioned into. The exact arboricity can be determined in \(O(m^{3/2}\log(n^2/m))\) time and 2-approximation in \(O(m+n)\) time. There is also an \((1+\epsilon)\)-approximation scheme that requires \(O(m\log n\log\tau \epsilon^{-1})\) time, where \(\tau\) is the arboricity of graph \(G\).
This paper focuses on the dynamic graph algorithms. If edges are inserted or deleted over time, a dynamic algorithm maintains some additional graph information which is then used to calculate graph arboricity faster than a static algorithm that starts from scratch. The algorithm presented in the paper maintains a decomposition into \(\tau\) edge-disjoint spanning forests and both insertion and deletion take \(O(m\log n)\) time in the worst case. The paper concludes with an amortized bound of \(\Omega(\log n)\) for the cost of answering the arboricity query under edge insertions and deletions.
Reviewer: Vladimír Lacko (Košice)The bandwidth theorem for locally dense graphs.https://www.zbmath.org/1452.051422021-02-12T15:23:00+00:00"Staden, Katherine"https://www.zbmath.org/authors/?q=ai:staden.katherine"Treglown, Andrew"https://www.zbmath.org/authors/?q=ai:treglown.andrewSummary: The bandwidth theorem of \textit{J. Böttcher} et al. [Math. Ann. 343, No. 1, 175--205 (2009; Zbl 1229.05132)] gives a condition on the minimum degree of an \(n\)-vertex graph \(G\) that ensures \(G\) contains every \(r\)-chromatic graph \(H\) on \(n\) vertices of bounded degree and of bandwidth \(o(n)\), thereby proving a conjecture of Bollobás and Komlós [\textit{J. Komlós}, Comb. Probab. Comput. 8, No. 1--2, 161--176 (1999; Zbl 0927.05041)]. In this paper, we prove a version of the bandwidth theorem for locally dense graphs. Indeed, we prove that every locally dense \(n\)-vertex graph \(G\) with \(\delta (G)> (1/2+o(1))n\) contains as a subgraph any given (spanning) \(H\) with bounded maximum degree and sublinear bandwidth.Restrained domination in signed graphs.https://www.zbmath.org/1452.050782021-02-12T15:23:00+00:00"Mathias, Anisha Jean"https://www.zbmath.org/authors/?q=ai:mathias.anisha-jean"Sangeetha, V."https://www.zbmath.org/authors/?q=ai:sangeetha.v"Acharya, Mukti"https://www.zbmath.org/authors/?q=ai:acharya.muktiSummary: A signed graph \(\Sigma\) is a graph with positive or negative signs attatched to each of its edges. A signed graph \(\Sigma\) is balanced if each of its cycles has an even number of negative edges. Restrained dominating set \(D\) in \(\Sigma\) is a restrained dominating set of its underlying graph where the subgraph induced by the edges across \(\Sigma [D : V\backslash D]\) and within \(V\backslash D\) is balanced. The set \(D\) having least cardinality is called minimum restrained dominating set and its cardinality is the restrained domination number of \(\Sigma\) denoted by \(\gamma_r(\Sigma)\). The ability to communicate rapidly within the network is an important application of domination in social networks. The main aim of this paper is to initiate a study on restrained domination in the realm of different classes of signed graphs.A 6-chromatic two-distance graph in the plane.https://www.zbmath.org/1452.050482021-02-12T15:23:00+00:00"Exoo, Geoffrey"https://www.zbmath.org/authors/?q=ai:exoo.geoffrey"Ismailescu, Dan"https://www.zbmath.org/authors/?q=ai:ismailescu.dan-pSummary: We prove that if one colors each point of the Euclidean plane with one of five colors, then there exist two points of the same color that are either distance 1 or distance 2 apart.Linear codes over signed graphs.https://www.zbmath.org/1452.941172021-02-12T15:23:00+00:00"Martínez-Bernal, José"https://www.zbmath.org/authors/?q=ai:martinez-bernal.jose"Valencia-Bucio, Miguel A."https://www.zbmath.org/authors/?q=ai:valencia-bucio.miguel-a"Villarreal, Rafael H."https://www.zbmath.org/authors/?q=ai:villarreal.rafael-heraclioA signed graph is a pair \((G,\sigma)\) where \(G\) is a graph (not necessarily simple) and \(\sigma\) is a map of the edge set, \(E(G)\), into \(\{+,-\}\). Letting \(V(G)=\{t_1,\dots,t_s\}\) be the vertex set of \(G\) and \(K\) a field, the incidence matrix of \((G,\sigma)\) is the matrix with columns, indexed by an ordering of the edge set of \(G\), equal to
\[\mathbf{e}_i-\sigma(\ell)\mathbf{e}_j,\]
where \(\mathbf{e}_i\), for \(i=1,\dots,s\), are the elements of the canonical basis of \(K^s\), for every edge \(\ell\) incident to \(t_i\) and \(t_j\)
(choosing an ordering of \(\{t_i,t_j\}\)), and where \(i=j\) if and only if \(\ell\) is a loop. The usual incidence matrix of graph and of a dygraph can be seen as particular cases of this.
This article is devoted to the study of linear codes which have generator matrix the incidence matrix of \((G,\sigma)\), as well as the study of some aspects of some combinatorial structures that may be associated to \((G,\sigma)\).
The focus on linear codes is in the computation of the sequence of generalized Hamming weights in terms of \((G,\sigma)\). Two ideas come into play. First, Theorem 2 in [\textit{V. K. Wei}, IEEE Trans. Inf. Theory 37, No. 5, 1412--1418 (1991; Zbl 0735.94008)], which enables the computation of the generalized Hamming weights of a linear code using (the dual of) the matroid of the generator matrix of the code. Secondly, Theorems 8B.1 and 8B.2 in [\textit{T. Zaslavsky}, Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)] stating that for a field of characteristic \(2\) the incidence matrix of a signed graph is a matrix representation for the graphic matroid of the underlying graph and for fields of characteristic different from \(2\), it is a matrix representation for the signed-graphic matroid. (The signed-graphic matroid is the matroid on \(E(G)\) with circuits the sets of edges forming balanced cycles or bow-ties, where a balanced cycle is a cycle with an even number of negative edges and a bow-tie is either the edge disjoint union of two cycles, each with an odd number of negatives edges, having a single common vertex or two such cycles, vertex disjoint, connected by path meeting them exactly at its end-points.)
Exploring this connection, the main results of Section 3 of this article (Theorem 3.16 and Theorem 3.19) equate the generalized Hamming weights of the incidence matrix code of \((G,\sigma)\), and of its dual, with (numerical) invariants of \((G,\sigma)\). Section 4 contains the computation of the Castelnuovo-Mumford regularity of the Stanley-Reisner rings of the independence complex of the matroid of the incidence matrix of \((G,\sigma)\) and of its dual in terms of graphs invariants (Theorem 4.7). In Section 5, the authors give an algebraic formula (based on the multiplicity invariant) for the frustration index, i.e., the minimum number of edges the removal of which turns \((G,\sigma)\) into a balanced graph. Finally, Section 6 contains several examples illustrating the results obtained. The article has also an appendix containing procedures, in \texttt{Macaulay2} code, for the computation of the featured ideals and invariants.
Reviewer: Jorge Neves (Coimbra)Computation of inverse 1-center location problem on the weighted trapezoid graphs.https://www.zbmath.org/1452.050772021-02-12T15:23:00+00:00"Jana, Biswanath"https://www.zbmath.org/authors/?q=ai:jana.biswanath"Mondal, Sukumar"https://www.zbmath.org/authors/?q=ai:mondal.sukumar"Pal, Madhumangal"https://www.zbmath.org/authors/?q=ai:pal.madhumangalSummary: Let \(T_{TRP}\) be the tree corresponding to the weighted trapezoid graph \(G=(V,E)\). The eccentricity \(e(v)\) of the vertex \(v\) is defined as the sum of the weights of the vertices from \(v\) to the vertex farthest from \(v \in T_{TRP}\). A vertex with minimum eccentricity in the tree \(T_{TRP}\) is called the 1-center of that tree. In an inverse 1-center location problem, the parameter of the tree \(T_{TRP}\) corresponding to the weighted trapezoid graph \(G=(V,E)\), like vertex weights, have to be modified at minimum total cost such that a pre-specified vertex \(s\in V\) becomes the 1-center of the trapezoid graph \(G\). In this paper, we present an optimal algorithm to find an inverse 1-center location on the weighted tree \(T_{TRP}\) corresponding to the weighted trapezoid graph \(G=(V,E)\), where the vertex weights can be changed within certain bounds. The time complexity of our proposed algorithm is \(O(n)\), where \(n\) is the number of vertices of the trapezoid graph \(G\).Even arbitrary supersubdivision of corona related MMD graphs.https://www.zbmath.org/1452.051652021-02-12T15:23:00+00:00"Revathi, R."https://www.zbmath.org/authors/?q=ai:revathi.ravilisetty"Jothi, Mary Jeya"https://www.zbmath.org/authors/?q=ai:jothi.mary-jeyaSummary: A graph \(G(V,E)\) with \(n\) vertices is said to have modular multiplicative divisor (MMD) labeling if there exists a bijection \(f:V(G) \to \{1,2,\dots,n\}\) and the induced function \(f^\ast :E(G)\to\{0,1,2,\dots,n-1\}\), where \(f^\ast(uv)=f(u)f(v)\pmod n\) for all \(uv\in E(G)\) such that \(n\) divides the sum of all edge labels of \(G\). This paper studies MMD labeling of an even arbitrary supersubdivision (EASS) of corona related graphs.SIS model of rumor spreading in social network with time delay and nonlinear functions.https://www.zbmath.org/1452.912512021-02-12T15:23:00+00:00"Zhu, Linhe"https://www.zbmath.org/authors/?q=ai:zhu.linhe"Huang, Xiaoyuan"https://www.zbmath.org/authors/?q=ai:huang.xiaoyuanA primer on Laplacian dynamics in directed graphs.https://www.zbmath.org/1452.050752021-02-12T15:23:00+00:00"Veerman, J. J. P."https://www.zbmath.org/authors/?q=ai:veerman.j-j-p"Lyons, R."https://www.zbmath.org/authors/?q=ai:lyons.russell|lyons.rainey|lyons.richard-n|lyons.richardSummary: We analyze the asymptotic behavior of general first order Laplacian processes on digraphs. The most important ones of these are diffusion and consensus with both continuous and discrete time. We treat diffusion and consensus as dual processes. This is the first complete exposition of this material in a single work.The sepr-sets of sign patterns.https://www.zbmath.org/1452.150182021-02-12T15:23:00+00:00"Hogben, Leslie"https://www.zbmath.org/authors/?q=ai:hogben.leslie"Lin, Jephian C.-H."https://www.zbmath.org/authors/?q=ai:lin.jephian-chin-hung"Olesky, D. D."https://www.zbmath.org/authors/?q=ai:olesky.d-dale"van den Driessche, P."https://www.zbmath.org/authors/?q=ai:van-den-driessche.paulineSummary: Given a real symmetric \(n\times n\) matrix, the sepr-sequence \(t_1\cdots t_n\) records information about the existence of principal minors of each order that are positive, negative, or zero. This paper extends the notion of the sepr-sequence to matrices whose entries are of prescribed signs, that is, to sign patterns. A sufficient condition is given for a sign pattern to have a unique sepr-sequence, and it is conjectured to be necessary. The sepr-sequences of sign semi-stable patterns are shown to be well-structured; in some special circumstances, the sepr-sequence is enough to guarantee that the sign pattern is sign semi-stable. In alignment with previous work on symmetric matrices, the sepr-sequences for sign patterns realized by symmetric nonnegative matrices of orders two and three are characterized.Dominator chromatic number of certain graph.https://www.zbmath.org/1452.050672021-02-12T15:23:00+00:00"Manjula, T."https://www.zbmath.org/authors/?q=ai:manjula.taduru"Rajeswari, Dr. R."https://www.zbmath.org/authors/?q=ai:rajeswari.dr-rSummary: A proper vertex coloring of a graph where every node of the graph dominates all nodes of some color class is called the dominator coloring of the graph. The least number of colors used in the dominator coloring of a graph is called the dominator coloring number denoted by \(\chi_d(G)\). The dominator coloring number and domination number of central, middle, total and line graph of quadrilateral snake graph are derived and the relation between them are expressed in this paper.iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data.https://www.zbmath.org/1452.650672021-02-12T15:23:00+00:00"Huang, Wei-Qiang"https://www.zbmath.org/authors/?q=ai:huang.weiqiang"Lin, Wen-Wei"https://www.zbmath.org/authors/?q=ai:lin.wen-wei"Lu, Henry Horng-Shing"https://www.zbmath.org/authors/?q=ai:lu.henry-horng-shing"Yau, Shing-Tung"https://www.zbmath.org/authors/?q=ai:yau.shing-tungSummary: The eigenvalue problem of a graph Laplacian matrix \(L\) arising from a simple, connected and undirected graph has been given more attention due to its extensive applications, such as spectral clustering, community detection, complex network, image processing and so on. The associated matrix \(L\) is symmetric, positive semi-definite, and is usually large and sparse. It is often of interest for finding some smallest positive eigenvalues and corresponding eigenvectors.
However, the singularity of \(L\) makes the classical eigensolvers inefficient since we need to factorize \(L\) for the purpose of solving large and sparse linear systems exactly. The next difficulty is that it is usually prohibitive to factorize \(L\) generated by real network problems from big data such as social media transactional databases, and sensor systems because there is in general not only local connections.
In this paper, we propose a trimming to cure the singularity of \(L\) according to its special property: zero row/column sum. This remedy technique leads us to solve a positive definite linear system reduced in one dimension and then recover the result to get a suitable solution of the original system involved in an eigensolver. Besides, we apply a deflating approach to exclude the influence of converged eigenvalues. We show how to apply the idea of trimming to the graph Laplacian eigenvalue problem together with a deflated term and a target shift. Accordingly, based on the inexact residual Arnoldi method [\textit{C.-R. Lee}, Residual Arnoldi method: theory, package and experiments. College Park, MD: University of Maryland. (PhD Thesis) (2007); with \textit{G. W. Stewart}, Analysis of the residual Arnoldi method. Tech. Rep. College Park, MD: University of Maryland. (2007)], we propose an integrated eigensolver for this kind of \(L\) combining with the \textit{implicit remedy of the singularity}, an \textit{effective deflation for convergent eigenvalues} and the shift-invert enhancement.
Numerical experiments reveal that the integrated eigensolver outperforms the classical Arnoldi/Lanczos method for computing some smallest positive eigeninformation especially when the LU factorization is not available.Resilience of networks formed of interdependent modular networks.https://www.zbmath.org/1452.912312021-02-12T15:23:00+00:00"Shekhtman, Louis M."https://www.zbmath.org/authors/?q=ai:shekhtman.louis-m"Shai, Saray"https://www.zbmath.org/authors/?q=ai:shai.saray"Havlin, Shlomo"https://www.zbmath.org/authors/?q=ai:havlin.shlomoLinear \(k\)-arboricity of complete bipartite graphs.https://www.zbmath.org/1452.050952021-02-12T15:23:00+00:00"Guo, Zhiwei"https://www.zbmath.org/authors/?q=ai:guo.zhiwei"Zhao, Haixing"https://www.zbmath.org/authors/?q=ai:zhao.haixing"Mao, Yaping"https://www.zbmath.org/authors/?q=ai:mao.yapingSummary: A linear \(k\)-forest refers to a forest in which every component is a path of length at most \(k\). The linear \(k\)-arboricity of a graph \(G\) is defined as the least number of linear \(k\)-forests, whose union is the set of all edges of \(G\). Recently, \textit{L. Zuo} et al. [Int. J. Comb. 2013, Article ID 501701, 6 p. (2013; Zbl 1295.05132)] obtained the exact values of the linear 2- and 4-arboricity of complete bipartite graphs \(K_{m,n}\) for some \(m\) and \(n\). In this paper, the exact values of the linear \(2i\)-arboricity of complete bipartite graphs \(K_{2in+2n,2in}\), \(K_{2in+2n,2in+1}\) and \(K_{2in+2n+1,2in}\) are obtained, which can be seen as an extension of Zuo et al.'s results [loc. cit.].Newman-Ziff algorithm for the bootstrap percolation: application to the Archimedean lattices.https://www.zbmath.org/1452.820052021-02-12T15:23:00+00:00"Choi, Jeong-Ok"https://www.zbmath.org/authors/?q=ai:choi.jeong-ok"Yu, Unjong"https://www.zbmath.org/authors/?q=ai:yu.unjongSummary: We propose very efficient algorithms for the bootstrap percolation and the diffusion percolation models by extending the Newman-Ziff algorithm of the classical percolation [\textit{M. E. J. Newman} and \textit{R. M. Ziff}, ``Efficient Monte Carlo algorithm and high-precision results for percolation'', Phys. Rev. Lett. 85, No. 19, 4104--4107 (2000; \url{doi:10.1103/PhysRevLett.85.4104})]. Using these algorithms and the finite-size-scaling, we calculated with high precision the percolation threshold and critical exponents in the eleven two-dimensional Archimedean lattices. We present the condition for the continuous percolation transition in the bootstrap percolation and the diffusion percolation, and show that they have the same critical exponents as the classical percolation within error bars in two dimensions. We conclude that the bootstrap percolation and the diffusion percolation almost certainly belong to the same universality class as the classical percolation.SSP-cyclic structure of some circulant graphs.https://www.zbmath.org/1452.051222021-02-12T15:23:00+00:00"Jothi, R. Mary Jeya"https://www.zbmath.org/authors/?q=ai:jeya-jothi.r-mary"Revathi, R."https://www.zbmath.org/authors/?q=ai:revathi.ravilisettySummary: If every induced subgraph \(H\) of a graph \(G\) contains a minimal dominating set that intersects every maximal cliques of \(H\), then \(G\) is SSP (super strongly perfect). This paper presents a cyclic structure of some circulant graphs and later investigates their SSP properties, while also giving attention to find the SSP parameters like colourability, cardinality of minimal dominating set and number of maximal cliques of circulant graphs.On computing the number of short cycles in bipartite graphs using the spectrum of the directed edge matrix.https://www.zbmath.org/1452.050942021-02-12T15:23:00+00:00"Dehghan, Ali"https://www.zbmath.org/authors/?q=ai:dehghan.ali-a"Banihashemi, Amir H."https://www.zbmath.org/authors/?q=ai:banihashemi.amir-hEditorial remark: No review copy delivered.On finding bipartite graphs with a small number of short cycles and large girth.https://www.zbmath.org/1452.050932021-02-12T15:23:00+00:00"Dehghan, Ali"https://www.zbmath.org/authors/?q=ai:dehghan.ali-a"Banihashemi, Amir H."https://www.zbmath.org/authors/?q=ai:banihashemi.amir-hEditorial remark: No review copy delivered.Total domination in certain nanotori.https://www.zbmath.org/1452.051302021-02-12T15:23:00+00:00"Rajasingh, Indra"https://www.zbmath.org/authors/?q=ai:rajasingh.indra"Jayagopal, R."https://www.zbmath.org/authors/?q=ai:jayagopal.r"Rajan, R. Sundara"https://www.zbmath.org/authors/?q=ai:rajan.r-sundaraSummary: A set \(S\) of vertices in a graph \(G\) is said to be a dominating set if every vertex in \(V(G)\setminus S\) is adjacent to some vertex in \(S\). A dominating set \(S\) is called a total dominating set if each vertex of \(V(G)\) is adjacent to some vertex in \(S\). Molecules arranging themselves into predictable patterns on silicon chips could lead to microprocessors with much smaller circuit elements. Mathematically, assembling in predictable patterns is equivalent to packing in graphs. In this paper, we determine the total domination number for certain nanotori using packing as a tool.Enumerating the decomposable neighbors of a decomposable graph under a simple perturbation scheme.https://www.zbmath.org/1452.621292021-02-12T15:23:00+00:00"Thomas, Alun"https://www.zbmath.org/authors/?q=ai:thomas.alun"Green, Peter J."https://www.zbmath.org/authors/?q=ai:green.peter-jSummary: Given a decomposable graph, we characterize and enumerate the set of pairs of vertices whose connection or disconnection results in a new graph that is also decomposable. We discuss the relevance of these results to Markov chain Monte Carlo methods that sample or optimize over the space of decomposable graphical models according to probabilities determined by a posterior distribution given observed multivariate data.Optimal proper connection of graphs.https://www.zbmath.org/1452.050582021-02-12T15:23:00+00:00"Fujita, Shinya"https://www.zbmath.org/authors/?q=ai:fujita.shinyaAn edge-colored graph \(G\) is properly colored if no two adjacent edges share a color in \(G\). An edge-colored connected graph \(G\) is properly connected if between every pair of distinct vertices, there exists a path that is properly colored. In this paper, the author considers the problem to convert a given monochromatic graph into a properly connected graph by recoloring \(p\) edges with \(q\) colors so that \(p + q\) is as small as possible. The author also discusses how this can be done efficiently for some restricted graphs, such as trees, complete bipartite graphs and graphs with independence number 2.
Reviewer: Juan José Montellano Ballesteros (Coyoacán)On the sum of the powers of distance signless Laplacian eigenvalues of graphs.https://www.zbmath.org/1452.050522021-02-12T15:23:00+00:00"Pirzada, S."https://www.zbmath.org/authors/?q=ai:pirzada.shariefuddin"Ganie, Hilal A."https://www.zbmath.org/authors/?q=ai:ganie.hilal-ahmad"Alhevaz, A."https://www.zbmath.org/authors/?q=ai:alhevaz.abdollah"Baghipur, M."https://www.zbmath.org/authors/?q=ai:baghipur.maryamSummary: Let \(G\) be a connected graph with \(n\) vertices, \(m\) edges and having distance signless Laplacian eigenvalues \(\rho_1 \geq \rho_2 \geq \dots \geq \rho_n \geq 0\). For any real number \(\alpha \neq 0\), let \(m_\alpha \left( G \right) = \sum\nolimits_{i = 1}^n {\rho_i^\alpha}\) be the sum of \(\alpha^{th}\) powers of the distance signless Laplacian eigenvalues of the graph \(G\). In this paper, we obtain various bounds for the graph invariant \(m_\alpha (G)\), which connects it with different parameters associated to the structure of the graph \(G\). We also obtain various bounds for the quantity \(\mathrm{DEL} (G)\), the distance signless Laplacian-energy-like invariant of the graph \(G\). These bounds improve some previously known bounds. We also pose some extremal problems about \(\mathrm{DEL}(G)\).New concept of cubic graph with application.https://www.zbmath.org/1452.051492021-02-12T15:23:00+00:00"P. K., Kishore Kumar"https://www.zbmath.org/authors/?q=ai:p-k.kishore-kumar"Talebi, Yahya"https://www.zbmath.org/authors/?q=ai:talebi.yahya"Rashmanlou, Hossein"https://www.zbmath.org/authors/?q=ai:rashmanlou.hossein"Talebi, A. A."https://www.zbmath.org/authors/?q=ai:talebi.ali-asghar"Mofidnakhaei, Farshid"https://www.zbmath.org/authors/?q=ai:mofidnakhaei.farshidSummary: A cubic graph is a generalized structure of a fuzzy graph that gives more precision, flexibility and compatibility to a system when compared with systems that are designed using fuzzy graphs. In this paper, some properties of an edge regular cubic graph are given. Particularly, strongly regular, edge regular and bi-regular cubic graphs are defined and the necessary and sufficient condition for a cubic graph to be strongly regular is studied. Likewise, we have introduced a partially edge regular cubic graph and fully edge regular cubic graph with suitable illustrations. Finally, we gave an application of cubic digraph in travel time.New concepts of bipolar fuzzy graphs.https://www.zbmath.org/1452.051472021-02-12T15:23:00+00:00"Lakdashti, Abolfazl"https://www.zbmath.org/authors/?q=ai:lakdashti.abolfazl"Rashmanlou, Hossein"https://www.zbmath.org/authors/?q=ai:rashmanlou.hossein"Borzooei, R. A."https://www.zbmath.org/authors/?q=ai:borzooei.rajab-ali"Samanta, S."https://www.zbmath.org/authors/?q=ai:samanta.sovan"Pal, M."https://www.zbmath.org/authors/?q=ai:pal.madhumangalSummary: The energy of a graph is the sum of the absolute values of its eigenvalues. It is used in chemistry to approximate the total \(\pi\)-electron energy of molecules. In this paper, the concept of energy of fuzzy graph is extended to the energy of bipolar fuzzy graph. It has many applications in computer science, physics, chemistry, and other sciences. We define adjacency matrix, degree matrix, Laplacian matrix, spectrum, and energy of a bipolar fuzzy graph in terms of their adjacency matrix. Also, the lower and upper bounds for the energy of a bipolar fuzzy graph are also derived.Direct sum of \(n\) Pythagorean fuzzy graphs with application to group decision-making.https://www.zbmath.org/1452.051452021-02-12T15:23:00+00:00"Akram, Muhammad"https://www.zbmath.org/authors/?q=ai:akram.muhammad"Habib, Amna"https://www.zbmath.org/authors/?q=ai:habib.amna"Davvaz, Bijan"https://www.zbmath.org/authors/?q=ai:davvaz.bijanSummary: A Pythagorean fuzzy set is an influential approach for describing ambiguous concepts more precisely. The Pythagorean fuzzy set-based models bring more pliability in handling human analysis. The intention of present paper is to illustrate an operation, namely direct sum of Pythagorean fuzzy graphs. An attempt has been made to analyze certain crucial properties, including regularity, strongness, completeness and connectedness with examples. Furthermore, some necessary and sufficient conditions have been established for direct sum to retain prescribed properties. In particular, the direct sum of \(n\) Pythagorean fuzzy graphs is described. Finally, an application on group decision-making problem has been displayed in which a new approach is suggested for selection of the best entity by employing Pythagorean fuzzy digraphs.\( \mathcal{P} \)-energy of graphs.https://www.zbmath.org/1452.051052021-02-12T15:23:00+00:00"Joshi, Prajakta Bharat"https://www.zbmath.org/authors/?q=ai:joshi.prajakta-bharat"Joseph, Mayamma"https://www.zbmath.org/authors/?q=ai:joseph.mayammaSummary: Given a graph \(G = (V, E)\), with respect to a vertex partition \(\mathcal{P}\) we associate a matrix called \(\mathcal{P} \)-matrix and define the \(\mathcal{P} \)-energy, \(E_\mathcal{P} (G)\) as the sum of \(\mathcal{P} \)-eigenvalues of \(\mathcal{P} \)-matrix of \(G\). Apart from studying some properties of \(\mathcal{P} \)-matrix, its eigenvalues and obtaining bounds of \(\mathcal{P} \)-energy, we explore the robust (shear) \( \mathcal{P} \)-energy which is the maximum (minimum) value of \(\mathcal{P} \)-energy for some families of graphs. Further, we derive explicit formulas for \(E_\mathcal{P} (G)\) of few classes of graphs with different vertex partitions.The role of interconnection patterns on synchronizability of duplex oscillatory power network.https://www.zbmath.org/1452.051762021-02-12T15:23:00+00:00"Yang, Li-xin"https://www.zbmath.org/authors/?q=ai:yang.lixin"Jiang, Jun"https://www.zbmath.org/authors/?q=ai:jiang.jun"Liu, Xiao-Jun"https://www.zbmath.org/authors/?q=ai:liu.xiao-jun.2Summary: This paper firstly proposes a multiplex oscillatory power network dynamical model, and then investigates the influence of interconnection patterns on synchronous ability of duplex power network being comprised of two subnetworks. In this work, we provide analytical vital conditions for synchronous stability in a multiplex oscillatory power network. Meanwhile, the relationship between interconnection types and synchronizability of duplex oscillatory power network is investigated. Moreover, we also find a counterintuitive phenomenon of connecting high-degree nodes where the synchronization has worst performance, on a specific duplex network composed of two star networks. In addition, our results show that increasing the interlink number favors synchronizability of duplex network consisting of two ring networks with the same properties in separate layers. However, the interlink number has no obvious effect on synchronizability for oscillatory network with strong heterogeneity in separate layers. Nonetheless, synchronization has better performance for duplex network composed of two ring networks than two star networks when the inter-layer connections are one-to-one. Our results provide an innovative guide for constructing a cost-effective multiplex power network.Geometry of graph partitions via optimal transport.https://www.zbmath.org/1452.651072021-02-12T15:23:00+00:00"Abrishami, Tara"https://www.zbmath.org/authors/?q=ai:abrishami.tara"Guillen, Nestor"https://www.zbmath.org/authors/?q=ai:guillen.nestor"Rule, Parker"https://www.zbmath.org/authors/?q=ai:rule.parker"Schutzman, Zachary"https://www.zbmath.org/authors/?q=ai:schutzman.zachary"Solomon, Justin"https://www.zbmath.org/authors/?q=ai:solomon.justin"Weighill, Thomas"https://www.zbmath.org/authors/?q=ai:weighill.thomas"Wu, Si"https://www.zbmath.org/authors/?q=ai:wu.siOn the connectivity of proper colorings of random graphs and hypergraphs.https://www.zbmath.org/1452.051672021-02-12T15:23:00+00:00"Anastos, Michael"https://www.zbmath.org/authors/?q=ai:anastos.michael"Frieze, Alan"https://www.zbmath.org/authors/?q=ai:frieze.alan-mThe paper under review considers the structure of the set of proper colourings of random hypergraphs. We say, for a hypergraph \(\Gamma\) with \(n\) vertices, that \(\Gamma_{q}\) is the graph whose vertices are all proper \(q\)-colourings of the hypergraph, with an edge between two colourings (vertices of \(\Gamma_{q}\)) if they agree on all but one vertex of \(\Gamma\). It is well known that this graph need not be connected: for example, even in the simple case of 2-uniform hypergraphs (i.e. simple graphs) if we choose the complete bipartite graph with \(n\) vertices in both classes, with a perfect matching removed and colour each pair of vertices which were adjacent in the removed matching the same colour, using \(n\) diferent colours for the \(n\) pairs, then with \(n\) colours we cannot change the colouring so this is an isolated vertex. However often \(\Gamma_{q}\) is connected and the main aim of the paper under review is to show that this is true whp (i.e. with probability tending to 1 as the number of vertices goes to infinity) for a certain model of random hypergraphs.
The model of random hypergraphs focused on is \(H_{n,m,k}\) where we have \(n\) vertices in the hypergraph and \(m\) edges are chosen uniformly at random from all \(k\)-element subsets of the \(n\) vertices to be the hyperedges. Note that in the case \(k=2\) this is simply the random graph \(G_{n,m}\). The main result is now that, if \(k\geq 2\) and \(p=d/\binom{n-1}{k-1}\) and \(m=\binom{n}{k}p\) for some large constant \(d\), there are certain functions \(\alpha\) and \(\beta\) of \(k\) and \(d\) such that if \(q\geq \alpha+\beta+1\) the graph \(\Gamma_{q}\) is whp connected. Further, if \( q\geq \alpha+2\beta+1\) then whp \(\Gamma_{q}\) has diameter at most \(O(\alpha\beta n)\). One can take
\[\alpha=\left(\frac{(k-1)d}{\log(d)-5(k-1)\log\log(d)}\right)^{1/(k-1)},\,\beta=3\log^{3k}(d).\]
The authors provide some evidence that the lower bound for \(q\) is in some sense close to where the greedy colouring algorithm succeeds whp. A noteworthy feature is that, using results of \textit{M. Molloy} [in: Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19--22, 2012. New York, NY: Association for Computing Machinery (ACM). 921--930 (2012; Zbl 1286.05049)], and of \textit{P. Ayre} and \textit{C. Greenhill} [SIAM J. Discrete Math. 33, No. 3, 1575--1606 (2019; Zbl 1420.05159)], when \(q=o(d/\log(d))\) \(\Gamma_{q}\) has only small components whp: thus \(\Gamma\) moves from typically having only small components to being (typically) connected without going through having a ``giant component'' (which is somewhat unusual in probabilistic combinatorics).
A sketch of the argument is that for relevant values of \(\alpha\) and \(\beta\), \(H_{n,m,k}\) will have the property that any greedy colouring of the hypergraph will use at most \(\alpha\) colours before being left with a hypergraph that has no \(\beta\)-core -- call such a colouring a good greedy colouring. One then shows that every colouring is within a short distance of a good greedy colouring and there is then scope to do some simple changes and use an inductive argument to finish the proofs.
Reviewer: David B. Penman (Colchester)The Weisfeiler-Leman dimension of planar graphs is at most 3.https://www.zbmath.org/1452.050432021-02-12T15:23:00+00:00"Kiefer, Sandra"https://www.zbmath.org/authors/?q=ai:kiefer.sandra"Ponomarenko, Ilia"https://www.zbmath.org/authors/?q=ai:ponomarenko.ilya"Schweitzer, Pascal"https://www.zbmath.org/authors/?q=ai:schweitzer.pascalLaplacian spectral characterization of (broken) dandelion graphs.https://www.zbmath.org/1452.051082021-02-12T15:23:00+00:00"Yang, Xiaoyun"https://www.zbmath.org/authors/?q=ai:yang.xiaoyun"Wang, Ligong"https://www.zbmath.org/authors/?q=ai:wang.ligongSummary: Let \(H(p,tK_{1,m}^*)\) be a connected unicyclic graph with \(p + t(m + 1)\) vertices obtained from the cycle \(C_p\) and \(t\) copies of the star \(K_{1, m}\) by joining the center of \(K_{1, m}\) to each one of \(t\) consecutive vertices of the cycle \(C_p\) through an edge, respectively. When \(t = p\), the graph is called a dandelion graph and when \(t \neq p\), the graph is called a broken dandelion graph. In this paper, we prove that the dandelion graph \(H(p,pK_{1,m}^*)\) and the broken dandelion graph \(H(p,tK_{1,m}^*)\) (\(0 < t < p\)) are determined by their Laplacian spectra when \(m \neq 2\) and \(p\) is even.Structure of triadic relations in multiplex networks.https://www.zbmath.org/1452.051692021-02-12T15:23:00+00:00"Cozzo, Emanuele"https://www.zbmath.org/authors/?q=ai:cozzo.emanuele"Kivelä, Mikko"https://www.zbmath.org/authors/?q=ai:kivela.mikko"Domenico, Manlio De"https://www.zbmath.org/authors/?q=ai:de-domenico.manlio"Solé-Ribalta, Albert"https://www.zbmath.org/authors/?q=ai:sole-ribalta.albert"Arenas, Alex"https://www.zbmath.org/authors/?q=ai:arenas.alex"Gómez, Sergio"https://www.zbmath.org/authors/?q=ai:gomez.sergio-alejandro.1"Porter, Mason A."https://www.zbmath.org/authors/?q=ai:porter.mason-a"Moreno, Yamir"https://www.zbmath.org/authors/?q=ai:moreno.yamirDefinable decompositions for graphs of bounded linear cliquewidth.https://www.zbmath.org/1452.030882021-02-12T15:23:00+00:00"Bojańczyk, Mikołaj"https://www.zbmath.org/authors/?q=ai:bojanczyk.mikolaj"Grohe, Martin"https://www.zbmath.org/authors/?q=ai:grohe.martin"Pilipczuk, Michał"https://www.zbmath.org/authors/?q=ai:pilipczuk.michalGraph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane.https://www.zbmath.org/1452.050702021-02-12T15:23:00+00:00"Parts, Jaan"https://www.zbmath.org/authors/?q=ai:parts.jaanSummary: We introduce a new graph minimization method, in which it is required to preserve some graph property and there is an effective procedure for checking this property. We applied this method to minimize 5-chromatic unit-distance graphs and obtained a graph with 509 vertices and 2142 edges.The action of \(\mathrm{SL}(2,{\mathbb {C}})\) on hyperbolic 3-space and orbital graphs.https://www.zbmath.org/1452.200482021-02-12T15:23:00+00:00"Beşenk, Murat"https://www.zbmath.org/authors/?q=ai:besenk.muratSummary: In this paper we discuss the action of \(\mathrm{SL}(2,{\mathbb {C}})\) on hyperbolic 3-space using quaternions. And then we investigate suborbital graphs for the special subgroup of \(\mathrm{PSL}(2,\mathbb {C})\). We point out the relation between elliptic elements and circuits in graphs. Results obtained by the method used are important because they mean that suborbital graphs have a potential to explain signature problems.Subspace arrangements, graph rigidity and derandomization through submodular optimization.https://www.zbmath.org/1452.680892021-02-12T15:23:00+00:00"Raz, Orit E."https://www.zbmath.org/authors/?q=ai:raz.orit-e"Wigderson, Avi"https://www.zbmath.org/authors/?q=ai:wigderson.aviSummary: This paper presents a deterministic, strongly polynomial time algorithm for computing the matrix rank for a class of symbolic matrices (whose entries are polynomials over a field). This class was introduced, in a different language, by
\textit{L. Lovász} [in: Proceedings of the 6th British combinatorics conference. London, etc: Academic Press. 45--86 (1977; Zbl 0361.05027)]
in his study of flats in matroids, and proved a duality theorem putting this problem in \(\mathrm{NP}\cap\mathrm{coNP}\). As such, our result is another demonstration where ``good characterization'' in the sense of Edmonds leads to an efficient algorithm. In a different paper
\textit{L. Lovász} [in: Fundamentals of computation theory -- FCT '79. Proceedings of the conference on algebraic, arithmetic, and categorial methods in computation theory held in Berlin/Wendisch-Rietz (GDR). Berlin: Akademie-Verlag. 565--574 (1979; Zbl 0446.68036)]
proved that all such symbolic rank problems have efficient probabilistic algorithms, namely are in BPP. As such, our algorithm may be interpreted as a derandomization result, in the long sequence special cases of the PIT (Polynomial Identity Testing) problem. Finally,
\textit{L. Lovász} and \textit{Y. Yemini} [SIAM J. Algebraic Discrete Methods 3, 91--98 (1982; Zbl 0497.05025)]
showed how the same problem generalizes the \textit{graph rigidity} problem in two dimensions. As such, our algorithm may be seen as a generalization of the well-known deterministic algorithm for the latter problem. There are two somewhat unusual technical features in this paper. The first is the translation of Lovász' flats problem into a symbolic rank one. The second is the use of submodular optimization for derandomization. We hope that the tools developed for both will be useful for related problems, in particular for better understanding of graph rigidity in higher dimensions.
For the entire collection see [Zbl 1443.05002].Predicting unobserved links in incompletely observed networks.https://www.zbmath.org/1452.620932021-02-12T15:23:00+00:00"Marchette, David J."https://www.zbmath.org/authors/?q=ai:marchette.david-j"Priebe, Carey E."https://www.zbmath.org/authors/?q=ai:priebe.carey-eSummary: In this paper we consider networks in which the links (edges) are imperfectly observed. This may be a result of sampling, or it may be caused by actors (vertices) who are actively attempting to hide their links (edges). Thus the network is incompletely observed, and we wish to predict which of the possible unobserved links are actually present in the network. To this end, we apply a constrained random dot product graph (CRDPG) to rank the potential edges according to the probability (under the model) that they are in fact present. This model is then extended to utilize covariates measured on the actors, to improve the link prediction. The method is illustrated on a data set of alliances between nations, in which a subset of the links (alliances) is assumed unobserved for the purposes of illustration.An exact approach for the multi-constraint graph partitioning problem.https://www.zbmath.org/1452.902252021-02-12T15:23:00+00:00"Recalde, Diego"https://www.zbmath.org/authors/?q=ai:recalde.diego"Torres, Ramiro"https://www.zbmath.org/authors/?q=ai:torres.ramiro"Vaca, Polo"https://www.zbmath.org/authors/?q=ai:vaca.poloSummary: In this work, a multi-constraint graph partitioning problem is introduced. The input is an undirected graph with costs on the edges and multiple weights on the nodes. The problem calls for a partition of the node set into a fixed number of clusters, such that each cluster satisfies a collection of node weight constraints, and the total cost of the edges whose end nodes are in the same cluster is minimized. It arises as a sub-problem of an integrated vehicle and pollster problem from a real-world application. Two integer programming formulations are provided, and several families of valid inequalities associated with the respective polyhedra are proved. An exact algorithm based on Branch \& Bound and cutting planes is proposed, and it is tested on real-world instances.Hamiltonian paths of the knight in an \(8\times 8\) chessboard.https://www.zbmath.org/1452.050972021-02-12T15:23:00+00:00"Bañon Serrano, Alberto"https://www.zbmath.org/authors/?q=ai:banon-serrano.alberto(no abstract)Random groups, random graphs and eigenvalues of \(p\)-Laplacians.https://www.zbmath.org/1452.200372021-02-12T15:23:00+00:00"Druţu, Cornelia"https://www.zbmath.org/authors/?q=ai:drutu.cornelia"Mackay, John M."https://www.zbmath.org/authors/?q=ai:mackay.john-mSummary: We prove that a random group in the triangular density model has, for density larger than 1/3, fixed point properties for actions on \(L^p\)-spaces (affine isometric, and more generally \((2 - 2 \varepsilon)^{1 / 2 p}\)-uniformly Lipschitz) with \(p\) varying in an interval increasing with the set of generators. In the same model, we establish a double inequality between the maximal \(p\) for which \(L^p\)-fixed point properties hold and the conformal dimension of the boundary.
In the Gromov density model, we prove that for every \(p_0 \in [2, \infty)\) for a sufficiently large number of generators and for any density larger than 1/3, a random group satisfies the fixed point property for affine actions on \(L^p\)-spaces that are \((2 - 2 \varepsilon)^{1 / 2 p}\)-uniformly Lipschitz, and this for every \(p \in [2, p_0]\). To accomplish these goals we find new bounds on the first eigenvalue of the \(p\)-Laplacian on random graphs, using methods adapted from Kahn and Szemerédi's approach to the 2-Laplacian. These in turn lead to fixed point properties using arguments of Bourdon and Gromov, which extend to \(L^p\)-spaces previous results for Kazhdan's Property (T) established by \textit{A. Żuk} [C. R. Acad. Sci., Paris, Sér. I 323, No. 5, 453--458 (1996; Zbl 0858.22007); Geom. Funct. Anal. 13, No. 3, 643--670 (2003; Zbl 1036.22004)] and \textit{W. Ballmann} and \textit{J. Świątkowski} [Geom. Funct. Anal. 7, No. 4, 615--645 (1997; Zbl 0897.22007)]i.Common knowledge and multi-scale locality analysis in Cayley structures.https://www.zbmath.org/1452.030492021-02-12T15:23:00+00:00"Canavoi, Felix"https://www.zbmath.org/authors/?q=ai:canavoi.felix"Otto, Martin"https://www.zbmath.org/authors/?q=ai:otto.martinOmega and related counting polynomials of \(\mathrm{TiO_2}\) nanostructures.https://www.zbmath.org/1452.051832021-02-12T15:23:00+00:00"Shaker, Hani"https://www.zbmath.org/authors/?q=ai:shaker.hani"Nadeem, Imran"https://www.zbmath.org/authors/?q=ai:nadeem.imran"Imran, Muhammad"https://www.zbmath.org/authors/?q=ai:imran.muhammadSummary: Graph theory provides valuable mathematical tools such as counting polynomials to explore the characteristics of molecular graphs. Recently, the Omega, Sadhana and Theta polynomials have been studied for the two-dimensional three-layer titania lattice and nanotube. In this paper, we formulate these polynomials for the two-dimensional six-layer titania lattice and nanotube.Some interpretations for algebraic invariants of edge ideals of hypergraphs via combinatorial invariants.https://www.zbmath.org/1452.130282021-02-12T15:23:00+00:00"Moradi, Somayeh"https://www.zbmath.org/authors/?q=ai:moradi.somayeh"Khosh-Ahang, Fahimeh"https://www.zbmath.org/authors/?q=ai:khosh-ahang.fahimehAuthors' abstract: The present work is concerned with characterizing some algebraic invariants of edge ideals of hypergraphs. To this aim, first, we introduce some kinds of combinatorial invariants similar to matching numbers for hypergraphs. Then we compare them to each other and to previously existing ones. These invariants are used for characterizing or bounding some algebraic invariants of edge ideals of hypergraphs such as graded Betti numbers, projective dimension and Castelnouvo-Mumford regularity.
Reviewer: Hero Saremi (Sanandaj)On Hadwiger conjecture for certain families of graphs with restricted number of cycles.https://www.zbmath.org/1452.050862021-02-12T15:23:00+00:00"Alarmelmangai, G."https://www.zbmath.org/authors/?q=ai:alarmelmangai.g"Anuradha, A."https://www.zbmath.org/authors/?q=ai:anuradha.arumugamSummary: Let \(G_k\), \((k\ge 0)\) be the family of graphs that have exactly \(k\) cycles. For \(0\le k\le 3\), we compute the Hadwiger number for graphs in \(G_k\) and further deduce that the Hadwiger conjecture is true for such families of graphs.Nonnegative signed Roman domination in graphs.https://www.zbmath.org/1452.051192021-02-12T15:23:00+00:00"Dehgardi, Nasrin"https://www.zbmath.org/authors/?q=ai:dehgardi.nasrin"Volkmann, L."https://www.zbmath.org/authors/?q=ai:volkmann.lutzSummary: Let \(G\) be a finite and simple graph with vertex set \(V(G)\). A nonnegative signed Roman dominating function (NNSRDF) on a graph \(G\) is a function \(f:V(G)\to\{-1,1,2\}\) satisfying the conditions that (i) \(\sum_{x\in N[v]}f(x)\ge 0\) for each \(v\in V(G)\), where \(N[v]\) is the closed neighborhood of \(v\), and (ii) every vertex \(u\) for which \(f(u)=-1\) has a neighbor \(v\) for which \(f(v)=2\). The weight of an NNSRDF \(f\) is \(\omega(f)=\sum_{v\in V(G)}f(v)\). The nonnegative signed Roman domination number \(\gamma^{NN}_{sR}(G)\) of \(G\) is the minimum weight of an NNSRDF on \(G\). In this paper, we initiate the study of the nonnegative signed Roman domination number of graphs, and we present different bounds on \(\gamma^{NN}_{sr}(G)\). We determine the nonnegative signed Roman domination number of some classes of graphs. If \(n\) is the order and \(m\) the size of the graph \(G\), then we show that \(\gamma^{N,N}_{sr}(G)\ge\frac 34(\sqrt{8n+1}-1)-n\) and \(\gamma^{N,N}_{sr}(G)\ge(8n-12m)/7\). In addition, if \(G\) is a bipartite graph of order \(n\), then we prove that \(\gamma^{N,N}_{sr}(G)\ge\frac32(\sqrt{4n+9}-3)-n\), and we characterize the extremal graphs.Bounds for some generalized vertex Folkman numbers.https://www.zbmath.org/1452.050632021-02-12T15:23:00+00:00"Jiang, Yu"https://www.zbmath.org/authors/?q=ai:jiang.yu.1|jiang.yu.2|jiang.yu|jiang.yu.3|jiang.yu.4"Liang, Meilian"https://www.zbmath.org/authors/?q=ai:liang.meilian"Xu, Xiaodong"https://www.zbmath.org/authors/?q=ai:xu.xiaodongSummary: For a graph \(G\) and positive integers \(a_1,\dots,a_r\) if every \(r\)-coloring of vertices in \(V(G)\) must result in a monochromatic \(a_i\)-clique of color \(i\) for some \(i\in\{1,\dots,r\}\), then we write \(G\to(a_1,\dots, a_r)^v\). \(F_v(K_{a_1},\dots,K_{a_r};H)\) is the smallest integer \(n\) such that there is an \(H\)-free graph \(G\) of order \(n\), and \(G\to(a_1, \dots,a_r)^v\). In this paper we study upper and lower bounds for some generalized vertex Folkman numbers of form \(F_v(K_{a_1},\dots, K_{a_r};K_4-e)\), where \(r\in\{2,3\}\) and \(a_i\in\{2,3\}\) for any \(i\in \{1,\dots,r\}\). We prove that \(F_v(K_2,K_2,K_2;K_4-e)=10\) and \(F_v(K_3,K_3;K_4-e)\ge 19\) by computing, and prove \(F_v(K_3,K_3;K_4-e)\ge F_v(K_2,K_2,K_3;K_4-e)\ge 25\).The signed total Roman domatic number of a digraph.https://www.zbmath.org/1452.050762021-02-12T15:23:00+00:00"Volkmann, L."https://www.zbmath.org/authors/?q=ai:volkmann.lutzSummary: Let \(D\) be a finite and simple digraph with vertex set \(V(D)\). A signed total Roman dominating function on the digraph \(D\) is a function \(f:V(D)\to\{-1,1,2\}\) such that \(\sum_{u\in N^-(v)}f(u)\ge 1\) for every \(v\in V(D)\) where \(N^-(v)\) consists of all inner neighbors of \(v\), and every vertex \(u\in V(D)\) for which \(f(u)=-1\) has an inner neighbor \(v\) for which \(f(v)=2\). A set \(\{f_1,f_2,\dots,f_d\}\) of distinct signed total Roman dominating functions on \(D\) with the property that \(\sum^d_{i=1}f_i(v)\le 1\) for each \(v\in V(D)\), is called a signed total Roman dominating family (of functions) on \(D\). The maximum number of functions in a signed total Roman dominating family on \(D\) is the signed total Roman domatic number of \(D\), denoted by \(d_{\mathrm{stR}}(D)\). In this paper we initiate the study of the signed total Roman domatic number in digraphs and we present some sharp bounds for \(d_{\mathrm{stR}}(D)\). In addition, we determine the signed total Roman domatic number of some digraphs. Some of our results are extensions of well-known properties of the signed total Roman domatic number of graphs.The transitivity of special graph classes.https://www.zbmath.org/1452.050812021-02-12T15:23:00+00:00"Haynes, Teresa W."https://www.zbmath.org/authors/?q=ai:haynes.teresa-w"Hedetniemi, Jason T."https://www.zbmath.org/authors/?q=ai:hedetniemi.jason-t"Hedetniemi, Stephen T."https://www.zbmath.org/authors/?q=ai:hedetniemi.stephen-t"McRae, Alice"https://www.zbmath.org/authors/?q=ai:mcrae.alice-a"Phillips, Nicholas"https://www.zbmath.org/authors/?q=ai:phillips.nicholas-cSummary: Let \(G=(V,E)\) be a graph. The transitivity of a graph \(G\), denoted \(\operatorname{Tr}(G)\), equals the maximum order \(k\) of a partition \(\pi=\{V_1,V_2, \dots,V_k\}\) of \(V\) such that for every \(i\), \(j\), \(1\le i<j\le k\), \(V_i\) dominates \(V_j\). We consider the transitivity in many special classes of graphs, including cactus graphs, coronas, Cartesian products, and joins. We also consider the effects of vertex or edge deletion and edge addition on the transivity of a graph. par We dedicate this paper to the memory of Professor Bohdan Zelinka for his pioneering work on domatic numbers of graphs.Domination in transformation graph \(G^{xy-}\).https://www.zbmath.org/1452.051332021-02-12T15:23:00+00:00"Wang, Tao"https://www.zbmath.org/authors/?q=ai:wang.tao.9|wang.tao.5|wang.tao.6|wang.tao.8|wang.tao.3|wang.tao.2|wang.tao.7|wang.tao.1"Wu, Baoyindureng"https://www.zbmath.org/authors/?q=ai:wu.baoyindurengSummary: Let \(G=(V(G)\), be a simple undirected graph of order \(n\) and size \(m\), and \(x\), \(y\), \(z\) be three variables taking value \(+\) or \(-\). The transformation graph \(G^{xy-}\) of \(G\) is the graph with vertex set \(V(G)\cup E(G)\) in which the vertex \(\alpha\) and \(\beta\) are joined by an edge if one of the following conditions holds: (i) \(\alpha,\beta\in V(G)\), and \(\alpha\) and \(\beta\) are adjacent in \(G\) if \(x=+\), and \(\alpha\) and \(\beta\) are not adjacent in \(G\) if \(x=-\), (ii) \(\alpha,\beta \in E(G)\), and \(\alpha\) and \(\beta\) are adjacent in \(G\) if \(Y=+\), and \(\alpha\) and \(\beta\) are not adjacent in \(G\) if \(y=-\), (iii) one of \(\alpha\) and \(\beta\) is in \(V(G)\) and the other is in \(E(G)\), and they are not incident in \(G\). In this note, it is shown that \(\gamma(G^{xy-} \le 3\) for a nonempty graph \(G\) and for any \(x,y\in\{+,-\}\), with a unified proof. Furthermore, we characterize the graph \(G\) with \(\gamma(G^{xy-})=k\) for each \(k\in\{1,2,3\}\), where \(x,y\in\{+,-\}\). As a consequence, a minimum dominating set of \(G^{xy-}\) can be found in polynomial time (in linear time in some cases).Energy and the Zagreb index conditions for nearly balanced bipartite graphs to be traceable.https://www.zbmath.org/1452.050412021-02-12T15:23:00+00:00"Yu, Gui-Dong"https://www.zbmath.org/authors/?q=ai:yu.guidong"Xu, Yi"https://www.zbmath.org/authors/?q=ai:xu.yi"Jiang, Gui-Sheng"https://www.zbmath.org/authors/?q=ai:jiang.guishengSummary: The energy of a graph is defined as the sum of the absolute values of the eigenvalues of its adjacency matrix. The first Zagreb index of a graph is defined as the sum of squares of the degrees of the vertices of the graph. The second Zagreb index of a graph is defined as the sum of products of the degrees of a pairs of the adjacent vertices of the graph. In this paper, we establish some sufficient conditions for a nearly balanced bipartite graph with large minimum degree to be traceable in terms of the energy, the first Zagreb index and the second Zagreb index of the quasi-complement of the graph, respectively.Majestic \(t\)-tone colorings of bipartite graphs with large cycles.https://www.zbmath.org/1452.050602021-02-12T15:23:00+00:00"Hart, Ian"https://www.zbmath.org/authors/?q=ai:hart.ian"Zhang, Ping"https://www.zbmath.org/authors/?q=ai:zhang.ping.1Summary: For a positive integer \(k\), let \([k]=\{1,2,\dots,k\}\), let \(\mathcal{P}([k])\) denote the power set of the set \([k]\) and let \(\mathcal{P}^\ast([k])=\mathcal{P}([k])-\emptyset\). For each integer \(t\) with \(1\le t<k\), let \(\mathcal{P}_t([k])\) denote the set of \(t\)-element subsets of \(\mathcal{P}([k])\). For an edge coloring \(c:E(G)\to \mathcal{P}([k])\) of a graph \(G\), where adjacent edges may be colored the same, \(c^\prime:V(G)\to\mathcal{P}^\ast([k])\) is the vertex coloring in which \(c^\prime(v)\) is the union of the color sets of the edges incident with \(v\). If \(c^\prime\) is a proper vertex coloring of \(G\), then \(c\) is a majestic \(t\)-tone \(k\)-coloring of \(G\). For a fixed positive integer \(t\), the minimum positive integer \(k\) for which a graph \(G\) has a majestic \(t\)-tone \(k\)-coloring is the majestic \(t\)-tone index \(\text{maj}_t(G)\) of \(G\). It is known that if \(G\) is a connected bipartite graph of order at least 3, then \(\text{maj}_t(G)=t+1\) or maj\(_t(G)=t+2\) for each positive integer \(t\). It is shown that (i) if \(G\) is a 2-connected bipartite graph of arbitrarily large order \(n\) whose longest cycles have length \(\ell\), where \(n-5\le\ell\le n\) and \(t\ge 2\) is an integer, then \(\text{maj}_t(G)=t+1\) and (ii) there is a 2-connected bipartite graph \(F\) of arbitrarily large order \(n\) whose longest cycles have length \(n-6\) and maj\(_2(F)=4\). Furthermore, it is shown for integers \(k,t\ge 2\) that there exists a \(k\)-connected bipartite graph \(G\) such that \(\text{maj}_t(G)=t+2\). Other results and open questions are also presented.Spanning trees and Hamiltonicity.https://www.zbmath.org/1452.050212021-02-12T15:23:00+00:00"Byers, Alexis"https://www.zbmath.org/authors/?q=ai:byers.alexis"Olejniczak, Drake"https://www.zbmath.org/authors/?q=ai:olejniczak.drake"Zayed, Mohra"https://www.zbmath.org/authors/?q=ai:zayed.mohra"Zhang, Ping"https://www.zbmath.org/authors/?q=ai:zhang.ping.1Summary: The 3-path graph \(\mathcal{P}_3(G)\) of a connected graph \(G\) of order 3 or more has the set of all 3-paths (paths of order 3) of \(G\) as its vertex set and two vertices of \(\mathcal{P}_3(G)\) are adjacent if they have a 2-path in common. A Hamiltonian walk in a nontrivial connected graph \(G\) is a closed walk of minimum length that contains every vertex of \(G\). With the aid of spanning trees and Hamiltonian walks in graphs, we provide sufficient conditions for the 3-path graph of a connected graph to be Hamiltonian.Counting acyclic and strong digraphs by descents.https://www.zbmath.org/1452.050732021-02-12T15:23:00+00:00"Archer, Kassie"https://www.zbmath.org/authors/?q=ai:archer.kassie"Gessel, Ira M."https://www.zbmath.org/authors/?q=ai:gessel.ira-m"Graves, Christina"https://www.zbmath.org/authors/?q=ai:graves.christina-m"Liang, Xuming"https://www.zbmath.org/authors/?q=ai:liang.xumingIn this paper, the authors refine the counting formulas for four classes of labeled directed graphs with \(n\) nodes and \(m\) edges by additional accounting for the number of descents. Hereby, a descent is a directed edge \((s,t)\) with \(s > t\).
The considered classes are strongly connected tournaments, strongly connected directed graphs, acyclic directed graphs, and forests (or trees). Their method builds on the known recursive formulas for these classes which are enriched by the number of descents. Then, they use special types of generating functions, such as Eulerian generating functions and a new variant developed by them called graphic Eulerian generating function, to derive closed forms or functional equations.
Reviewer: Michael Wallner (Vienna)Extremal Zagreb indices of unicyclic graphs.https://www.zbmath.org/1452.050322021-02-12T15:23:00+00:00"Chen, Shubo"https://www.zbmath.org/authors/?q=ai:chen.shubo"Zhou, Houqing"https://www.zbmath.org/authors/?q=ai:zhou.houqingSummary: The Zagreb indices are topological indices of graphs defined as, \(M_1(G)=\sum_{v\in V(G)}(d(v))^2\), \(M_2(G)=\sum_{uv\in E(G)} (d(u)d(v))\). In this paper, we determine the upper and lower bounds for the Zagreb indices of unicyclic graphs in terms of their order and girth. In each case, we characterize the extremal graphs.RDF-BF-hypergraph representation for relational database.https://www.zbmath.org/1452.680672021-02-12T15:23:00+00:00"Ghaleb, Fayed F. M."https://www.zbmath.org/authors/?q=ai:ghaleb.fayed-f-m"Taha, Azza A."https://www.zbmath.org/authors/?q=ai:taha.azza-a"Hazman, Maryam"https://www.zbmath.org/authors/?q=ai:hazman.maryam"ElLatif, Mahmoud Abd"https://www.zbmath.org/authors/?q=ai:ellatif.mahmoud-abd"Abbass, Mona"https://www.zbmath.org/authors/?q=ai:abbass.monaSummary: The semantic web is designed to provide machine accessible meaning for its constructs. Semantic web depends on Resource Description Framework (RDF), which is a standard model for data interchange on the Web. The RDF can be represented as graph which is known as RDF-graph data model. One of the goals of the semantic web is to display the huge quantities of data that is stored in the Relational Databases (RDB) for computer processing. In order to integrate RDB into semantic web applications, RDB should be represented as RDF-graph data model, which is fundamental for developing the semantic web in the recent decade. In the last decades a special class of database schemes, called acyclic database schema was introduced. This class is preferred in order to minimize the time of answering query and decrease its space efficient access paths. Also the result of answering a query will be reduced specially in the case of representing RDB as graph data model. This paper introduces a Backward and Forward hypergrapg (BF-hypergraph) representation for the RDF schema that corresponds to RDB schema. The BF-hypergraph is a suitable model to represent the set of functional dependencies of RDB, since the domain and codomain of the functional dependency may contain more than one attribute. Finally, the paper proposes a model to represent the RDF-BF-hypergraph schema that corresponds to an acyclic/cyclic RDB schema according to its set of functional dependency. A formal representation of RDF-graph schema will preserve the integrity constraints and data semantics. Moreover, a formal representation of RDF-graph schema will facilitate the data conversion and will allow graph connectivity which is essential for querying the RDF using various traversal algorithms.The intersection problem for \(\mathrm{PBD}(4,7^\ast)\).https://www.zbmath.org/1452.051092021-02-12T15:23:00+00:00"Zhang, Guizhi"https://www.zbmath.org/authors/?q=ai:zhang.guizhi"An, Yonghong"https://www.zbmath.org/authors/?q=ai:an.yonghong"Feng, Tao"https://www.zbmath.org/authors/?q=ai:feng.taoSummary: For every \(v\equiv 7,10\pmod{12}\) with \(v\ge 22\) there exist a pairwise balanced design PBD of order \(v\) with exactly one block of size 7 and rest of size 4, denoted by \(\mathrm{PBD}(4,7^\ast)\) of order \(v\). The intersection problem for \(\mathrm{PBD}(4,7^\ast)\) is the determination of all pairs \((v,k)\) such that there exist a pair of \(\mathrm{PBD}(4,7^\ast)\)s \((X,\mathcal{B}_1)\) and \((X,\mathcal{B}_2)\) of order \(v\) containing the same block \(B\) of size 7 such that \(|(\mathcal{B}_1\setminus\{B\})\cap(\mathcal{B}_2 \setminus\{B\})|=k\). We will denote the set of all such \(k\) by \(J(v)\). \(I(v)=\{0,1,\dots,b_v-8,b_v-6,b_v\}\), where \(b_v=(v^2-v-42)/12\) be the number of blocks of size 4 in \(\mathrm{PBD}(4,7^\ast)\) of order \(v\). It is established that \(J(v)=I(v)\) for any positive integer \(v\equiv 7,10\pmod{12}\) and \(v\not\in\{10,19,22,31,34,46,58,70\}\).Monochromatic equilateral triangles in the unit distance graph.https://www.zbmath.org/1452.050682021-02-12T15:23:00+00:00"Naslund, Eric"https://www.zbmath.org/authors/?q=ai:naslund.ericSummary: Let \(\chi_{\Delta} ( \mathbb{R}^n )\) denote the minimum number of colors needed to color \(\mathbb{R}^n\) so that there will not be a monochromatic equilateral triangle with side length 1. Using the slice rank method, we reprove a result of \textit{P. Frankl} and \textit{V. Rödl} [Trans. Am. Math. Soc. 300, 259--286 (1987; Zbl 0611.05002)], and show that \(\chi_{\Delta} ( \mathbb{R}^n )\) grows exponentially with \(n\). This technique substantially improves upon the best known quantitative lower bounds for \(\chi_{{\Delta}} ( \mathbb{R}^n )\), and we obtain
\[
\chi_{{\Delta}} \left(\mathbb{R}^n\right) > ( 1.01446 + o ( 1 ) )^n .
\]Computing the Zagreb eccentricity indices of thorny graphs.https://www.zbmath.org/1452.050272021-02-12T15:23:00+00:00"Berberler, Zeynep Nihan"https://www.zbmath.org/authors/?q=ai:berberler.zeynep-nihan-odabasSummary: The first and second Zagreb eccentricity indices are defined respectively in terms of the vertex eccentricities as \(E_1(G)=\sum_{v\in V(G)}\varepsilon(v)^2\) and \(E_2(G)=\sum_{uv\in E(G)}\varepsilon(u) \varepsilon(v)\), where \(\varepsilon(u)\) denotes the eccentricity of the vertex \(U\). In this paper, Zagreb eccentricity indices of a class of composite graphs, namely, thorny graphs are investigated. Explicit formulas for Zagreb eccentricity indices of these types of graphs are presented.Efficient network dismantling via node explosive percolation.https://www.zbmath.org/1452.051732021-02-12T15:23:00+00:00"Qin, Shao-Meng"https://www.zbmath.org/authors/?q=ai:qin.shao-meng"Ren, Xiao-Long"https://www.zbmath.org/authors/?q=ai:ren.xiaolong"Lü, Lin-Yuan"https://www.zbmath.org/authors/?q=ai:lu.linyuanOn the domination, strong and weak domination in transformation graph \(G^{xy-}\).https://www.zbmath.org/1452.051182021-02-12T15:23:00+00:00"Aytaç, Aysun"https://www.zbmath.org/authors/?q=ai:aytac.aysun-ozan"Turach, Tufan"https://www.zbmath.org/authors/?q=ai:turach.tufanSummary: Let \(G=(V(G),E(G))\) be a simple undirected graph of order \(n\) and size \(m\), and \(x\), \(y\), \(z\) be three variables taking value \(+\) or \(-\). The transformation graph of \(G\), \(G^{xyz}\) is a simple graph having \(V(G)\cup E(G)\) as the vertex set. If an expression has \(n\) variables, and each variable can have the value \(+\) or \(-\), the number of different combinations of values of the variables is \(2^n\). Thus, we obtain eight kinds of transformation graphs. A set \(S\subseteq V(G)\) is a dominating set if every vertex in \(V(G)-S\) is adjacent to at least one vertex in \(S\). The minimum cardinality taken over all dominating sets of \(G\) is called the domination number of \(G\) and is denoted by \(\gamma(G)\). There are several types of domination parameters depending upon the nature of dominating sets. In this paper, we investigate the domination number, the strong domination number and the weak domination number of the transformation graph \(G^{xy-}\).Edge even graceful labeling of torus grid graph.https://www.zbmath.org/1452.051592021-02-12T15:23:00+00:00"Daoud, Salama Nagy"https://www.zbmath.org/authors/?q=ai:daoud.salama-nagy"Saleh, Wedad"https://www.zbmath.org/authors/?q=ai:saleh.wedadSummary: We study the family of torus grid graphs. We also obtain necessary and sufficient conditions to be edge even graceful labeling for all of the cases of every member of this family.Entire forgotten topological index of graphs.https://www.zbmath.org/1452.050282021-02-12T15:23:00+00:00"Bharali, A."https://www.zbmath.org/authors/?q=ai:bharali.arup"Doley, Amitav"https://www.zbmath.org/authors/?q=ai:doley.amitav"Buragohain, Jibonjyoti"https://www.zbmath.org/authors/?q=ai:buragohain.jibonjyotiSummary: The Forgotten topological index or F-index is defined as the sum of cubes of the degrees of vertices of a graph. For this classical F-index, we ignore the intermolecular forces that exist between the atoms and bonds and consider only the intermolecular forces between the atoms of a molecule. In this paper, we introduce a new graph invariant called ``Entire Forgotten topological index'' or ``Entire F-index'', that includes incidency of edges and vertices in addition to the adjacency of the vertices. We obtain some important properties of the index and also establish formulae of this newly defined index for some operations of graphs.On the spectral radius of bipartite graphs.https://www.zbmath.org/1452.051022021-02-12T15:23:00+00:00"Fan, Dandan"https://www.zbmath.org/authors/?q=ai:fan.dandan"Wang, Guoping"https://www.zbmath.org/authors/?q=ai:wang.guoping"Zao, Yuying"https://www.zbmath.org/authors/?q=ai:zao.yuyingSummary: The adjacency matrix \(A(G)\) of a graph \(G\) is the \(n\times n\) matrix with its \((i,j)\)-entry equal to 1 if \(v_i\) and \(v_j\) are adjacent, and 0 otherwise. The spectral radius of \(G\) is the largest eigenvalue of \(A(G)\). In this paper we determine the graph with maximum spectral radius among all connected bipartite graphs of order \(n\) with a given matching number and a given vertex connectivity, respectively.Super antimagic total labeling under duplication operations.https://www.zbmath.org/1452.051622021-02-12T15:23:00+00:00"Khalaf, Abdul Jalil M."https://www.zbmath.org/authors/?q=ai:khalaf.a-m"Naeem, Muhammad"https://www.zbmath.org/authors/?q=ai:naeem.muhammad-nawaz"Siddiqui, Muhammad Kamran"https://www.zbmath.org/authors/?q=ai:siddiqui.muhammad-kamran"Baig, Abdul Qudair"https://www.zbmath.org/authors/?q=ai:baig.abdul-qudairSummary: For a graph \(G\) the duplication operation of a vertex \(v\) by a new edge \(e = uw\) results in a new graph \(G'\) such that \(N (u) = \{v, w\}\) and \(N (w) = \{v, u\}\). The duplication operation of an edge \(e = uv\) by a new vertex \(w\) results in a new graph \(G''\) such that \(N (w) = \{u, v\}\). In this article we have discussed that the properties of a graph, with minimum degree 2 of any vertex, to be super vertex-antimagic total and to be super edge-antimagic total are invariant under the above duplication operations. Also, we have discussed on the existence of the so-called \(k\) super vertex-antimagic total vertex modifications and \(k\) super edge-antimagic total edge modifications for graphs.Topological properties of four types of porphyrin dendrimers.https://www.zbmath.org/1452.050422021-02-12T15:23:00+00:00"Khalaf, Abdul Jalil M."https://www.zbmath.org/authors/?q=ai:khalaf.a-m"Javed, Aisha"https://www.zbmath.org/authors/?q=ai:javed.aisha"Jamil, Muhammad Kamran"https://www.zbmath.org/authors/?q=ai:jamil.muhammad-kamran"Alaeiyan, Mehdi"https://www.zbmath.org/authors/?q=ai:alaeiyan.mehdi"Farahani, Mohammad Reza"https://www.zbmath.org/authors/?q=ai:farahani.mohammad-rezaSummary: A chemical compound can be represented as a chemical graph. A topological index of a (chemical) graph is a numeric value of a graph which characterize its topology and is usually graph invariant. The Zagreb indices, Randić index and sum-connectivity indices are useful in the study of anti-inflammatory activities, boiling point, molecular complexity heterosystems of certain chemical instances, and in elsewhere. In this paper, we calculate the mentioned topological indices of some infinite classes of prophyrin dendrimers.Final solution to the open problem regarding double stars proposed by Marr and Wallis.https://www.zbmath.org/1452.051552021-02-12T15:23:00+00:00"Afzal, H. U."https://www.zbmath.org/authors/?q=ai:afzal.hafiz-usmanSummary: In \textit{A. Kotzig} and \textit{A. Rosa} [Can. Math. Bull. 13, 451--461 (1970; Zbl 0213.26203)] introduced the idea of edge-magic total labeling of graphs. In this article, we will provide the final solution to an open problem, regarding edge-magicness of the double star \(S_{m,n}\), originally proposed by \textit{A. M. Marr} and \textit{W. D. Wallis} [Magic graphs. 2nd ed. New York, NY: Birkhäuser (2013; Zbl 1267.05002)], for all possible values of \(m\) and \(n\), hence closing it.Programming with MATLAB to color Latin squares.https://www.zbmath.org/1452.050172021-02-12T15:23:00+00:00"Shokri, A."https://www.zbmath.org/authors/?q=ai:shokri.abbasali|shokri.abbas-ali|shokri.ali|shokri.ali.1"Golriz, M."https://www.zbmath.org/authors/?q=ai:golriz.mohammad-r"Alaeiyan, M."https://www.zbmath.org/authors/?q=ai:alaeiyan.mehdi|alaeiyan.mohammadhadiSummary: With a Matlab programming we will find the chromatic number for all Latin squares of order smaller than 7. Previously, a manual algorithm for coloring the Latin square was provided. This algorithm determined the chromatic number of some special classes of Latin squares such as Cyclic or Dihedral, so, we tried to speed up the process of this algorithm with a programming.Some resistance distance and distance-based graph invariants and number of spanning trees in the tensor product of \(P_2\) and \(K_n\).https://www.zbmath.org/1452.050372021-02-12T15:23:00+00:00"Sardar, Muhammad Shoaib"https://www.zbmath.org/authors/?q=ai:shoaib-sardar.muhammad"Cancan, Murat"https://www.zbmath.org/authors/?q=ai:cancan.murat"Ediz, Süleyman"https://www.zbmath.org/authors/?q=ai:ediz.suleyman"Sajjad, Wasim"https://www.zbmath.org/authors/?q=ai:sajjad.wasimSummary: The resistance distance (Kirchhoff index and multiplicative Kirchhoff index) and distance-based (Wiener index and Gutman index) graph invariants of \(\Gamma_n= P_2 \times K_n\) are considered. Firstly by using the decomposition theorem, we procure the Laplacian and Normalized Laplacian spectrum for graph \(\Gamma_n\), respectively. Based on which, we can procured the formulae for the number of spanning trees and some resistance distance and distance-based graph invariants of graph \(\Gamma_n\). Also, it is very interesting to see that when \(n\) tends to infinity, \(Kf(\Gamma_n)\) is a polynomial and \(W(\Gamma_n)\) is a quadratic polynomial.Irregularity indices for line graph of Dutch windmill graph.https://www.zbmath.org/1452.050442021-02-12T15:23:00+00:00"Mohammed, Mohanad A."https://www.zbmath.org/authors/?q=ai:mohammed.mohanad-a"Al-Mayyahi, Suad Younus A."https://www.zbmath.org/authors/?q=ai:al-mayyahi.suad-younus-a"Virk, Abaid ur Rehman"https://www.zbmath.org/authors/?q=ai:virk.abaid-ur-rehman"Mutee ur Rehman, Hafiz"https://www.zbmath.org/authors/?q=ai:ur-rehman.hafiz-muteeSummary: Among topological descriptors topological indices are significant and they have a conspicuous role in chemistry. Dutch Windmill graph \(D^x_y\) can be obtain by taking \(x\) copies of cycle \(C_y\) with a vertex in common. In this paper, we will compute some irregularity índices that are useful in quantitative structure activity relationship for Line Graph of Dutch Windmill graph.Study of topology of block shift networks via topological indices.https://www.zbmath.org/1452.050462021-02-12T15:23:00+00:00"Cancan, Murat"https://www.zbmath.org/authors/?q=ai:cancan.murat"Ahmad, Iftikhar"https://www.zbmath.org/authors/?q=ai:ahmad.iftikhar"Ahmad, Sarfarz"https://www.zbmath.org/authors/?q=ai:ahmad.sarfarzSummary: Topological indices (TIs) are important numerical number associate with the molecular graph of a chemical structure/compound because due to these parameters, one can guess almost all properties of concerned structure/compound with our performing experiments. In recent years, huge amount work has been done for calculating degreedependent indices for different structures/compouds. In order to compute TIs, one need to do many calculations. Our aim of this paper is to present a simple method to compute degree-dependent TIs. We computed \(M\)-polynomials for Block Shift Networks and with the help of this simple algebraic polynomials, we recovered nine important TIs for Block Shift Networks. Our work is important for chemists, physicians and pharmaceutical industry.Distance and eccentricity based polynomials and indices of \(m\)-level wheel graph.https://www.zbmath.org/1452.050312021-02-12T15:23:00+00:00"Cancan, Murat"https://www.zbmath.org/authors/?q=ai:cancan.murat"Hussain, Muhammad"https://www.zbmath.org/authors/?q=ai:hussain.muhammad-adnan|hussain.muhammad-tanveer"Ahmad, Haseeb"https://www.zbmath.org/authors/?q=ai:ahmad.haseebSummary: Distance and degree based topological polynomial and indices of molecular graphs have various applications in chemistry, computer networking and pharmacy. In this paper, we give hosoya polynomial, Harary polynomial, Schultz polynomial, modified Schultz polynomial, eccentric connectivity polynomial, modified Wiener index, modified hyper Wiener index, generalized Harary index, multiplicative Wiener index, Schultz index, modified Schultz index, eccentric connectivity index of generalized wheel networks \(W_{n,m}\). We also give pictorial representation of computed topological polynomials and indices on the involved parameters \(m\) and \(n\).Redefined Zagreb indices of rhombic, triangular, hourglass and jagged-rectangle benzenoid systems.https://www.zbmath.org/1452.050352021-02-12T15:23:00+00:00"Mohammed, Mohanad A."https://www.zbmath.org/authors/?q=ai:mohammed.mohanad-a"Haoer, Raad S."https://www.zbmath.org/authors/?q=ai:haoer.raad-s"Ali, Ashaq"https://www.zbmath.org/authors/?q=ai:ali.ashaq"Ahmad, Maqbool"https://www.zbmath.org/authors/?q=ai:ahmad.maqbool"Farahani, Mohammad Reza"https://www.zbmath.org/authors/?q=ai:farahani.mohammad-reza"Nazeer, Saima"https://www.zbmath.org/authors/?q=ai:nazeer.saimaSummary: In the fields of mathematical chemistry and chemical graph theory, a topological index generally called a connectivity index is a kind of a molecular descriptor that is calculated in perspective of the molecular graph of a chemical compound. Topological indices are numerical parameters of a graph which depict its topology and are graph invariant up to graph isomorphism. Topological indices are used for example in the progression of quantitative structure-activity relationships (QSARs) in which the common activity or distinctive properties of atoms are connected with their molecular structure. There are in excess of 140 topological indices but none of them totally describe the molecular compound completely so there is dependably a space to characterize and register new topological indices. Benzenoid Systems are utilized basically as an intermediate to make different synthetic compounds. In this report we aim to compute redefined Zagreb indices for Zigzag, Rhombic, triangular, Hourglass and Jagged-rectangle Benzenoid systems.Two-geodesic transitive graphs of order a product of two primes.https://www.zbmath.org/1452.050822021-02-12T15:23:00+00:00"Jin, Wei"https://www.zbmath.org/authors/?q=ai:jin.wei.1|jin.wei"Tan, Li"https://www.zbmath.org/authors/?q=ai:tan.liSummary: In a non-complete graph \(\Gamma\), a vertex triple \((u,v,w)\) with \(v\) adjacent to both \(u\) and \(w\) is called a 2-geodesic if \(u\ne w\) and \(u,w\) are not adjacent. The graph \(\Gamma\) is said to be 2-geodesic transitive if its automorphism group is transitive on the set of arcs, and also transitive on the set of 2-geodesics. We first classify the family of 2-geodesic transitive graphs of order a product of two primes. Then, we determine exactly such graphs of valency 4.Multi-scale process modelling and distributed computation for spatial data.https://www.zbmath.org/1452.623642021-02-12T15:23:00+00:00"Zammit-Mangion, Andrew"https://www.zbmath.org/authors/?q=ai:mangion.andrew-zammit"Rougier, Jonathan"https://www.zbmath.org/authors/?q=ai:rougier.jonathan-cSummary: Recent years have seen a huge development in spatial modelling and prediction methodology, driven by the increased availability of remote-sensing data and the reduced cost of distributed-processing technology. It is well known that modelling and prediction using infinite-dimensional process models is not possible with large data sets, and that both approximate models and, often, approximate-inference methods, are needed. The problem of fitting simple global spatial models to large data sets has been solved through the likes of multi-resolution approximations and nearest-neighbour techniques. Here we tackle the next challenge, that of fitting complex, nonstationary, multi-scale models to large data sets. We propose doing this through the use of superpositions of spatial processes with increasing spatial scale and increasing degrees of nonstationarity. Computation is facilitated through the use of Gaussian Markov random fields and parallel Markov chain Monte Carlo based on graph colouring. The resulting model allows for both distributed computing and distributed data. Importantly, it provides opportunities for genuine model and data scalability and yet is still able to borrow strength across large spatial scales. We illustrate a two-scale version on a data set of sea-surface temperature containing on the order of one million observations, and compare our approach to state-of-the-art spatial modelling and prediction methods.Bounds for neighborhood Zagreb index and its explicit expressions under some graph operations.https://www.zbmath.org/1452.050362021-02-12T15:23:00+00:00"Mondal, Sourav"https://www.zbmath.org/authors/?q=ai:mondal.sourav"Ali, Muhammad Arfan"https://www.zbmath.org/authors/?q=ai:ali.muhammad-arfan"De, Nilanjan"https://www.zbmath.org/authors/?q=ai:de.nilanjan"Pal, Anita"https://www.zbmath.org/authors/?q=ai:pal.anitaSummary: Topological indices are useful in QSAR/QSPR studies for modeling biological and physiochemical properties of molecules. The neighborhood Zagreb index (MN) is a novel topological index having good correlations with some physiochemical properties. For a simple connected graph \(G\), the neighborhood Zagreb index is the totality of square of \(\delta_G(v)\) over the vertex set, where \(\delta_G(v)\) is the total count of degrees of all neighbors of \(v\) in \(G\). In this report, some bounds are established for the neighborhood Zagreb index. Some explicit expressions of the index for some graph operations are also computed, which are used to obtain the index for some chemically significant molecular graphs.Edge irregularity strength of certain families of comb graph.https://www.zbmath.org/1452.051662021-02-12T15:23:00+00:00"Zhang, Xiujun"https://www.zbmath.org/authors/?q=ai:zhang.xiujun"Cancan, Murat"https://www.zbmath.org/authors/?q=ai:cancan.murat"Nadeem, Muhammad Faisal"https://www.zbmath.org/authors/?q=ai:nadeem.muhammad-faisal"Imran, Muhammad"https://www.zbmath.org/authors/?q=ai:imran.muhammadSummary: Edge irregular mapping or vertex mapping \(h : V (U) - \rightarrow \{1, 2, 3, 4,\dots, s\}\) is a mapping of vertices in such a way that all edges have distinct weights. We evaluate weight of any edge by using equation \(wt_h(cd) = h(c)+h(d)\), \( \forall c, d \in V (U)\)) and \(\forall cd \in E(U)\). Edge irregularity strength denoted by \(es(U)\) is a minimum positive integer use to label vertices to form edge irregular labeling. In this paper, we find exact value of edge irregularity strength of different families of comb graph.Molecular descriptors of certain OTIS interconnection networks.https://www.zbmath.org/1452.050292021-02-12T15:23:00+00:00"Cancan, Murat"https://www.zbmath.org/authors/?q=ai:cancan.murat"Ahmad, Iftikhar"https://www.zbmath.org/authors/?q=ai:ahmad.iftikhar"Ahmad, Sarfarz"https://www.zbmath.org/authors/?q=ai:ahmad.sarfarzSummary: Network theory as an important role in the field of electronic and electrical engineering, for example, in signal processing, networking, communication theory, etc. The branch of mathematics known as Graph theory found remarkable applications in this area of study. A topological index (TI) is a real number attached with graph networks and correlates the chemical networks with many physical and chemical properties and chemical reactivity. The Optical Transpose Interconnection System (OTIS) network has received considerable attention in recent years and has a special place among real world architectures for parallel and distributed systems. In this report, we compute redefined first, second and third Zagreb indices of OTIS swapped and OTIS biswapped networks. We also compute some Zagreb polynomials of understudy Networks.\(M\)-polynomial and topological indices of benzene ring embedded in P-type surface network.https://www.zbmath.org/1452.050302021-02-12T15:23:00+00:00"Cancan, Murat"https://www.zbmath.org/authors/?q=ai:cancan.murat"Ediz, Süleyman"https://www.zbmath.org/authors/?q=ai:ediz.suleyman"Baig, Abdul Qudair"https://www.zbmath.org/authors/?q=ai:baig.abdul-qudair"Khalid, Waqas"https://www.zbmath.org/authors/?q=ai:khalid.waqasSummary: The representation of chemical compounds and chemical networks with the \(M\)-polynomials is a new idea and it gives nice and good results of the topological indices. These results are used to correlate the chemical compounds and chemical networks with their chemical properties and bioactivities.
Particular attention is paid to the derivation of the \(M\) polynomia -- for the benzene ring embedded in the P-type surface network in 2D. Furthermore, the topological indices based on the degrees are also derived by using the general form of \(M\)-polynomial of benzene ring embedded in the P-type surface network \(BR(m, n)\). In the end, the graphical representation and comparison of the \(M\)-polynomial and the topological indices of benzene ring embedded in P-type surface network in 2D are described.Rainbow and strong rainbow connection number for some families of graphs.https://www.zbmath.org/1452.050652021-02-12T15:23:00+00:00"Khan, Yaqoub Ahmed"https://www.zbmath.org/authors/?q=ai:khan.yaqoub-ahmed"Naeem, Muhammad"https://www.zbmath.org/authors/?q=ai:naeem.muhammad-nawaz"Siddiqui, Muhammad Kamran"https://www.zbmath.org/authors/?q=ai:siddiqui.muhammad-kamran"Farahani, Mohammad Reza"https://www.zbmath.org/authors/?q=ai:farahani.mohammad-rezaSummary: Let \(G\) be a nontrivial connected graph. Then \(G\) is called a rainbow connected graph if there exists a coloring \(c : E(G) \rightarrow \{1, 2,\dots, k\}\), \(k\in N\), of the edges of \(G\), such that there is a \(u - v\) rainbow path between every two vertices of \(G\), where a path \(P\) in \(G\) is a rainbow path if no two edges of \(P\) are colored the same. The minimum \(k\) for which there exists such a \(k\)-edge coloring is the rainbow connection number \(\operatorname{rc}(G)\) of \(G\). If for every pair \(u\), \(v\) of distinct vertices, \(G\) contains a rainbow \(u - v\) geodesic, then \(G\) is called strong rainbow connected. The minimum \(k\) for which \(G\) is strong rainbow-connected is called the strong rainbow connection number \(\operatorname{src}(G)\) of \(G\).
The exact \(\operatorname{rc}\) and \(\operatorname{src}\) of the rotationally symmetric graphs are determined.Decontaminating arbitrary graphs by mobile agents: a survey.https://www.zbmath.org/1452.900812021-02-12T15:23:00+00:00"Osula, Dorota"https://www.zbmath.org/authors/?q=ai:osula.dorotaSummary: A team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented in order to better describe real life problems like decontaminating danger areas by a group of robots or cleaning networks from viruses.
A centralized searching, when a topology of a graph is known in advance is well studied. This survey presents comprehensive results focusing mainly on an issue of the distributed monotone contiguous decontamination problem, including recent results for clearing graphs with and without a priori knowledge about its topology. We introduce a bibliography for various models, which differ on e.g., knowledge about a graph, properties of agents, time clock or size of the available memory.The sharp bounds of topological indices of strong product of new \(F\)-sum on connected graphs.https://www.zbmath.org/1452.050392021-02-12T15:23:00+00:00"Siddiqui, Hafiz Muhammad Afzal"https://www.zbmath.org/authors/?q=ai:afzal-siddiqui.hafiz-muhammad"Baby, Shakila"https://www.zbmath.org/authors/?q=ai:baby.shakila"Shafiq, Muhammad Kashif"https://www.zbmath.org/authors/?q=ai:shafiq.muhammad-kashifSummary: The degree of a vertex \(v\) in a graph \(G\) is the number of its first neighbors. Degree based topological indices are of much importance because of their vital role in chemical graph theory and particularly in theoretical chemistry. In this paper, the lower and upper bounds for general Randić, general sum-connectivity and harmonic indices for the strong product of the \(F\)-sum on graphs are determined.Complexity of restricted variant of star colouring.https://www.zbmath.org/1452.681412021-02-12T15:23:00+00:00"Shalu, M. A."https://www.zbmath.org/authors/?q=ai:shalu.m-a"Antony, Cyriac"https://www.zbmath.org/authors/?q=ai:antony.cyriacSummary: Restricted star colouring is a variant of star colouring introduced to design heuristic algorithms to estimate sparse Hessian matrices. For \(k\in \mathbb{N} \), a \(k\)-restricted star (\(k\)-rs) colouring of a graph \(G\) is a function \(f:V(G)\rightarrow \{0,1,\dots ,k-1\}\) such that (i) \( f(x)\ne f(y)\) for every edge \(xy\) of \(G \), and (ii) there is no bicoloured 3-vertex path \(( P_3)\) in \(G\) with the higher colour on its middle vertex. We show that for \(k\ge 3\), it is NP-complete to decide whether a given planar bipartite graph of maximum degree \(k\) and girth at least six is \(k\)-rs colourable, and thereby answer a problem posed by
\textit{M. A. Shalu} and \textit{T. P. Sandhya} [Graphs Comb. 32, No. 5, 2121--2134 (2016; Zbl 1351.05089)].
In addition, we design an \(O(n^3)\) algorithm to test whether a chordal graph is 3-rs colourable.
For the entire collection see [Zbl 1435.68020].Unimodular lattice triangulations as small-world and scale-free random graphs.https://www.zbmath.org/1452.051722021-02-12T15:23:00+00:00"Krüger, B."https://www.zbmath.org/authors/?q=ai:kruger.benedikt"Schmidt, E. M."https://www.zbmath.org/authors/?q=ai:schmidt.ella-m"Mecke, K."https://www.zbmath.org/authors/?q=ai:mecke.klaus-rA mild changed condition for fractional \((g,f,n)\)-critical deleted graph.https://www.zbmath.org/1452.051382021-02-12T15:23:00+00:00"Gao, Wei"https://www.zbmath.org/authors/?q=ai:gao.wei.3"Guirao, Juan L. G."https://www.zbmath.org/authors/?q=ai:garcia-guirao.juan-luisSummary: A graph \(G\) is fractional \((g,f,n)\)-critical deleted if after deleting any edge \(e\), the resulting graph is still a fractional \((g,f,n)\)-critical graph. In [\textit{W. Gao} and \textit{W. Wang}, Colloq. Math. 147, No. 1, 55--65 (2017; Zbl 1358.05228)], it is presented that \(G\) is a fractional \((g,f,n)\)-critical graph if \(I(G)\ge\frac{b^2+bn-\Delta}{a}\), where \(I(G)\) is the isolated toughness of graph \(G\). The aim of this work is to reveal that after mild changing of this bound, we obtain an isolated toughness condition for a graph to be fractional \((g,f,n)\)-critical deleted. Furthermore, we show that this conclusion can help to directly deduce an \(I(G)\) bound for all fractional \((g,f,n)\)-critical deleted graphs. Finally, we propose an open question for a more generalized case.On the signed Roman \(k\)-domination in graphs.https://www.zbmath.org/1452.051152021-02-12T15:23:00+00:00"Amjadi, J."https://www.zbmath.org/authors/?q=ai:amjadi.jafar"Nazari-Moghaddam, S."https://www.zbmath.org/authors/?q=ai:nazari-moghaddam.sakineh"Sheikholeslami, S. M."https://www.zbmath.org/authors/?q=ai:sheikholeslami.seyed-mahmoud"Volkmann, L."https://www.zbmath.org/authors/?q=ai:volkmann.lutzA signed Roman \(k\)-dominating function on a graph \(G = (V(G), E(G))\) is a function \(f: V(G) \rightarrow \{-1, 1, 2\}\) such that (i) every vertex \(u\) with \(f(u) = -1\) is adjacent to at least one vertex \(v\) with \(f(v) = 2\) and (ii) \(\sum_{x \in N[w]}f(x) \geq k\) holds for each \(w\in V(G)\). The weight of \(f\) is \(\sum_{u \in V(G)}f(u)\), the minimum weight of a signed Roman \(k\)-dominating function is the signed Roman \(k\)-domination number \(\gamma_{sR}^k(G)\) of \(G\). In this paper, several lower bounds on \(\gamma_{sR}^k(G)\) are given involving the order and the size of \(G\). For trees \(T\) of order \(n\), it is proved that \((4n+7)/5 \le \gamma_{sR}^3(T)\le 3n/2\) and that \(n+2 \le \gamma_{sR}^4(T)\le 2n\). For each of these four bounds, the extremal trees are classified.
Reviewer: Sandi Klavžar (Ljubljana)\(F\)-root square mean labeling of line graph of some graphs.https://www.zbmath.org/1452.051562021-02-12T15:23:00+00:00"Arockiaraj, S."https://www.zbmath.org/authors/?q=ai:arockiaraj.s"Baskar, A. Durai"https://www.zbmath.org/authors/?q=ai:durai-baskar.a"Kannan, A. Rajesh"https://www.zbmath.org/authors/?q=ai:kannan.a-rajeshSummary: A function \(f\) is called a \(F\)-root square mean labeling of a graph \(G(V,E)\) with \(p\) vertices and \(q\) edges if \(f:V(G)\to\{1,2,3,\dots, q+1\}\) is injective and the induced function \(f^\ast\) defined as \(f^\ast (uv)=\left\lfloor\sqrt{\frac{f(u)^2+f(v)^2}{2}}\right\rfloor\) for all \(uv\in E(G)\), is bijective. A graph that admits a \(F\)-root square mean labeling is called a \(F\)-root square mean graph. The line graph is one among the graph operations. In this paper, it is tried to analyse that the line graph operation preserves the \(F\)- property. Here we have discussed the \(F\)-root square mean of line graph of the path, cycle, star, \(P_n\circ S_1,P_n\circ S_2,[P_n;S_1],S(P_n\circ S_1)\), ladder, slanting ladder, the crown graph \(C_n\circ S_1\) and the arbitrary subdivision of \(S_3\).Tetravalent normal edge-transitive Cayley graphs of order \(12n\).https://www.zbmath.org/1452.050832021-02-12T15:23:00+00:00"Lou, Bengong"https://www.zbmath.org/authors/?q=ai:lou.bengong"Han, Xiaori"https://www.zbmath.org/authors/?q=ai:han.xiaoriSummary: Let \(G=\langle a,b\mid a^{4n}=b^3=1\), \(a^{-1}ba=b^{-1}\rangle\) be a group of order \(12n\), where \(6\not| n\). In this paper, we consider tetravalent normal edge-transitive Cayley graphs on \(G\), and give their automorphism groups when \(\Gamma\) is normal.On the relations between liars' dominating and set-sized dominating parameters.https://www.zbmath.org/1452.051312021-02-12T15:23:00+00:00"Roden-Bowie, Miranda L."https://www.zbmath.org/authors/?q=ai:roden-bowie.miranda-l"Slater, Peter J."https://www.zbmath.org/authors/?q=ai:slater.peter-jamesSummary: We define the \((i,j)\)-liars' domination number of \(G\), denoted by \(LR_{(i,j)}(G)\), to be the minimum cardinality of a set \(L\subseteq V(G)\) such that detection devices placed at the vertices in \(L4\) can precisely determine the set of intruder locations when there are between 1 and \(i\) intruders and at most \(j\) detection devices that might ``lie''.
We also define the \(X(c_1,c_2,\dots,c_t,\dots)\)-domination number, denoted by \(\gamma_{X(c_1,c_2,\dots,c_t,\dots)}(G)\), to be the minimum cardinality of a set \(D\subseteq V(G)\) such that, if \(S\subseteq V(G)\) with \(|S|=k\), then \(|(\cup_{s\in S}N[s])\cap D|\ge c_k\). Thus, \(D\) dominates each set of \(k\) vertices at least \(c_k\) times making \(\gamma_{X(c_1,c_2,\dots,c_t,\dots)}(G)\) a set-sized dominating parameter. We consider the relations between these set-sized dominating parameters and the liars' dominating parameters.Distance pebbling on directed cycle graphs.https://www.zbmath.org/1452.051102021-02-12T15:23:00+00:00"Knapp, Michael P."https://www.zbmath.org/authors/?q=ai:knapp.michael-pSummary: Let \(G\) be a graph we define the distance \(d\) pebbling number of \(G\) to be the smallest number \(s\) such that if \(s\) pebbles are placed on the vertices of \(G\), then there must exist a sequence of pebbling moves which takes a pebble to a vertex which is at a distance of at least \(d\) from its starting point. In this article, we evaluate the distance \(d\) pebbling numbers for a directed cycle graph with \(n\) vertices.Decentral smart grid control.https://www.zbmath.org/1452.912302021-02-12T15:23:00+00:00"Schäfer, Benjamin"https://www.zbmath.org/authors/?q=ai:schafer.benjamin-william"Matthiae, Moritz"https://www.zbmath.org/authors/?q=ai:matthiae.moritz"Timme, Marc"https://www.zbmath.org/authors/?q=ai:timme.marc"Witthaut, Dirk"https://www.zbmath.org/authors/?q=ai:witthaut.dirkDefining and identifying cograph communities in complex networks.https://www.zbmath.org/1452.051712021-02-12T15:23:00+00:00"Jia, Songwei"https://www.zbmath.org/authors/?q=ai:jia.songwei"Gao, Lin"https://www.zbmath.org/authors/?q=ai:gao.lin"Gao, Yong"https://www.zbmath.org/authors/?q=ai:gao.yong"Nastos, James"https://www.zbmath.org/authors/?q=ai:nastos.james"Wang, Yijie"https://www.zbmath.org/authors/?q=ai:wang.yijie"Zhang, Xindong"https://www.zbmath.org/authors/?q=ai:zhang.xindong"Wang, Haiyang"https://www.zbmath.org/authors/?q=ai:wang.haiyangThe existence of regular and quasi-regular bipartite self-complementary 3-uniform hypergraphs.https://www.zbmath.org/1452.051122021-02-12T15:23:00+00:00"Kamble, Lata N."https://www.zbmath.org/authors/?q=ai:kamble.lata-n"Deshpande, C. M."https://www.zbmath.org/authors/?q=ai:deshpande.charusheela-m"Athawale, B. P."https://www.zbmath.org/authors/?q=ai:athawale.b-pSummary: A hypergraph \(H\) with vertex set \(V\) and edge set \(E\) is called bipartite if \(V\) can be partitioned into two subsets \(V_1\) and \(V_2\) such that \(e\cap V_1\ne\emptyset\) and \(e\cap V_2\ne\emptyset\) for any \(e\in E\). A bipartite self-complementary 3-uniform hypergraph \(H\) with partition \((V_1,V_2)\) of a vertex set \(V\) such that \(|V_1|=m\) and \(|V_2|=n\) exists if and only if either (i) \(m=n\) or (ii) \(m\ne n\) and either \(m\) or \(n\) is congruent to 0 modulo 4 or (iii) \(m\ne n\) and both \(m\) and \(n\) are congruent to 1 or 2 modulo 4.
In this paper we prove that, there exists a regular bipartite self-complementary 3-uniform hypergraph \(H(V_1,V_2)\) with \(|V_1|=m\), \(|V_2|=n\), \(m+n>3\) if and only if \(m=n\) and \(n\) is congruent to 0 or 1 modulo 4. Further we prove that, there exists a quasi-regular bipartite self-complementary 3-uniform hypergraph \(H(V_1,V_2)\) with \(|V_1|=m\), \(|V_2|=n\), \(m+n>3\) if and only if either \(m=3\), \(n=4\) or \(m=n\) and \(n\) is congruent to 2 or 3 modulo 4.Modularity of Erdős-Rényi random graphs.https://www.zbmath.org/1452.051682021-02-12T15:23:00+00:00"McDiarmid, Colin"https://www.zbmath.org/authors/?q=ai:mcdiarmid.colin"Skerman, Fiona"https://www.zbmath.org/authors/?q=ai:skerman.fionaThis paper studies modularity \(q^\ast\) of random graph models \(G(n,p)\) and \(G(n,m)\). For \(0<p\le1\), if \(n^2p\rightarrow\infty\) and \(np\le 1+o(1)\), it is shown that \(q^\ast(G(n,p))\) tends to 1 in probability.
If for two constants \(1<C_0\le C_1\), there exists \(\delta>0\) satisfying \(C_0\le np\le C_1\) for all large \(n\), then with high probability it is shown that \(\delta<q^\ast(G(n,p))<1-\delta\). If \(np\rightarrow\infty\), then it is shown that \(q^\ast(G(n,p))\) tends to zero in probability. For the \(G(n,m)\) model, if \(m\rightarrow\infty\) and \(d=2m/n\le 1+o(1)\), then \(q^\ast(G(n,m))\) tends to 1 in probability. If for two constants \(1<C_0\le C_1\) there exists \(\delta>0\) satisfying \(C_0\le d\le C_1\) for all large \(n\), then with high probability it is shown that \(\delta<q^\ast(G(n,m))<1-\delta\). If \(d\rightarrow\infty\), it is shown that \(q^\ast(G(n,m))\) tends to zero in probability.
Reviewer: Yilun Shang (Newcastle)Discrete chain graph models.https://www.zbmath.org/1452.623482021-02-12T15:23:00+00:00"Drton, Mathias"https://www.zbmath.org/authors/?q=ai:drton.mathiasSummary: The statistical literature discusses different types of Markov properties for chain graphs that lead to four possible classes of chain graph Markov models. The different models are rather well understood when the observations are continuous and multivariate normal, and it is also known that one model class, referred to as models of LWF (Lauritzen-Wermuth-Frydenberg) or block concentration type, yields discrete models for categorical data that are smooth. This paper considers the structural properties of the discrete models based on the three alternative Markov properties. It is shown by example that two of the alternative Markov properties can lead to non-smooth models. The remaining model class, which can be viewed as a discrete version of multivariate regressions, is proven to comprise only smooth models. The proof employs a simple change of coordinates that also reveals that the model's likelihood function is unimodal if the chain components of the graph are complete sets.Assorted musings on dimension-critical graphs.https://www.zbmath.org/1452.050512021-02-12T15:23:00+00:00"Noble, Matt"https://www.zbmath.org/authors/?q=ai:noble.mattSummary: For a finite simple graph \(G\), we say \(G\) is of dimension \(n\), and write \(\dim(G)=n\), if \(n\) is the smallest integer such that \(G\) can be represented as a unit-distance graph in \(\mathbb{R}^n\). Define \(G\) to be dimension-critical if every proper subgraph of \(G\) has dimension less than \(G\). In this article, we determine exactly which complete multipartite graphs are dimension-critical. It is then shown that for each \(n\ge 2\), there is an arbitrarily large dimension-critical graph \(G\) with \(\dim(G)=n\). We close with a few observations and questions that may aid in future work.\(C_6\)-decomposition of the tensor product of complete graphs.https://www.zbmath.org/1452.051372021-02-12T15:23:00+00:00"Akwu, A. D."https://www.zbmath.org/authors/?q=ai:akwu.abolape-d"Oyewumi, O."https://www.zbmath.org/authors/?q=ai:oyewumi.oSummary: Let \(G\) be a simple and finite graph. A graph is said to be decomposed into subgraphs \(H_1\) and \(H_2\) which is denoted by \(G=H_1\oplus H_2\), if \(G\) is the edge disjoint union of \(H_1\) and \(H_2\). If \(G=H_1\oplus H_2\oplus\cdots\oplus H_k\), where \(H_1,H_2,\dots,H_k\) are all isomorphic to \(H\), then \(G\) is said to be \(H\)-decomposable. Futhermore, if \(H\) is a cycle of length \(m\) then we say that \(G\) is \(C_m\)-decomposable and this can be written as \(C_m|G\), where \(G\times H\) denotes the tensor product of graphs \(G\) and \(H\). In this paper, we prove that the necessary conditions for the existence of \(C_6\)-decomposition of \(K_m\times K_n\) are sufficient. Using these conditions it can be shown that every even regular complete multipartite graph \(G\) is \(C_6\)-decomposable if the number of edges of \(G\) is divisible by 6.Packing the crowns with cycles and stars.https://www.zbmath.org/1452.051402021-02-12T15:23:00+00:00"Lin, Jenq-Jong"https://www.zbmath.org/authors/?q=ai:lin.jenq-jong"Jou, Min-Jen"https://www.zbmath.org/authors/?q=ai:jou.min-jenSummary: Let \(F\), \(G\) and \(H\) be graphs. A \((G,H)\)-decomposition of \(F\) is a partition of the edge set of \(F\) into copies of \(G\) and copies of \(H\) with at least one copy of \(G\) and at least one copy of \(H\). For \(L\subseteq F\), a \((G,H)\)-packing of \(F\) with leave \(L\) is a \((G,H)\)-decomposition of \(F-E(L)\). A \((G,H)\)-packing of \(F\) with the largest cardinality is a maximum \((G,H)\)-packing. This paper gives the solution of finding the maximum \((C_k,S_k)\)-packing of the crown \(C_{n,n-1}\).On the \(k\)-domination, \(k\)-tuple domination and Roman \(k\)-domination numbers in graphs.https://www.zbmath.org/1452.051292021-02-12T15:23:00+00:00"Rad, Nader Jafari"https://www.zbmath.org/authors/?q=ai:jafari-rad.naderSummary: \textit{D. Rautenbach} and \textit{L. Volkmann} [Appl. Math. Lett. 20, No. 1, 98--102 (2007; Zbl 1137.05054)] gave an upper bound for the \(k\)-domination number and \(k\)-tuple domination number of a graph. \textit{A. Hansberg} and \textit{L. Volkmann} [Discrete Appl. Math. 157, No. 7, 1634--1639 (2009; Zbl 1179.05081)] gave upper bounds for the \(k\)-domination number and Roman \(k\)-domination number of a graph. In this note, using the probabilistic method and the known Caro-Wei theorem on the size of the independence number of a graph, we improve the above bounds on the \(k\)-domination number, the \(k\)-tuple domination number and the Roman \(k\)-domination number in a graph for any integer \(k\ge 1\). The special case \(k=1\) of our bounds improve the known bounds of \textit{V. I. Arnautov} [Prikl. Mat. Programm. 11, 3--8 (1974; Zbl 0297.05131)] and \textit{C. Payan} [Cah. Cent. Étud. Rech. Opér. 17, 307--317 (1975; Zbl 0341.05126)] and \textit{E. J. Cockayne} et al. [Discrete Math. 278, No. 1--3, 11--22 (2004; Zbl 1036.05034)].Relating 2-rainbow domination to weak Roman domination.https://www.zbmath.org/1452.051142021-02-12T15:23:00+00:00"Alvarado, Jose D."https://www.zbmath.org/authors/?q=ai:alvarado.jose-d"Dantas, Simone"https://www.zbmath.org/authors/?q=ai:dantas.simone"Rautenbach, Dieter"https://www.zbmath.org/authors/?q=ai:rautenbach.dieterSummary: Addressing a problem posed by \textit{M. Chellali} et al. [Discrete Appl. Math. 178, 27--32 (2014; Zbl 1300.05212)] we prove \(\gamma_{r2}(G)\le 2\gamma_r(G)\) for every graph \(G\), where \(\gamma_{r2}(G)\) and \(\gamma_r(G)\) denote the 2-rainbow domination number and the weak Roman domination number of \(G\), respectively. We characterize the extremal graphs for this inequality that are \(\{K_4,K_4-e\}\)-free, and show that the recognition of the \(K_5\)-free extremal graphs is NP-hard.A generalization of Dirac's theorem for claw-free graphs.https://www.zbmath.org/1452.050982021-02-12T15:23:00+00:00"Chen, Zhi-Hong"https://www.zbmath.org/authors/?q=ai:chen.zhihong"Dale, Ashley"https://www.zbmath.org/authors/?q=ai:dale.ashley"Dale, Sarah"https://www.zbmath.org/authors/?q=ai:dale.sarahSummary: For a graph \(H\), let \(\delta_t(H)=\min\{|\bigcup^t_{j=1}N_H(v_i)\mid \{v_1,\dots,v_t\}\text{ are } t \text{ vertices in } H\}\). We show that for a given number \(\varepsilon\) and given integers \(p\ge t>0\) and \(k\in(2,3)\), the family of \(k\)-connected Hamiltonian claw-free graphs \(H\) of sufficiently large order \(n\) with \(\delta(H)\ge 3\) and \(\delta_t(H)\ge t(n+\varepsilon)/p\) has a finite obstruction set in which each member is a \(k\)-edge-connected \(K_3\)-free graph of order at most \(\max\{p/t+2t, 3p/t+2t-7\}\) and without spanning closed trails. We found the best possible values of \(p\) and \(\varepsilon\) for some \(t\ge 2\) when the obstruction set is empty or has the Petersen graph only. In particular, we prove the following for such graphs \(H\):
(a) For \(k=2\) and a given \(t(1\le t\le 4)\), if \(\delta_t(H)\ge\binom{n+1}{3}\) and \(\delta(H)\ge 3\), then \(H\) is Hamiltonian.
(b) For \(k=3\) and \(t=2\), (i) if \(\delta_2(H)\ge\binom{n+12}{9}\), then \(H\) is Hamiltonian; (ii) if \(\delta_2(H)\ge \frac{n+9}{10}\), then either \(H\) is Hamiltonian, or \(H\) can be characterized by the Petersen graph.
(c) For \(k=3\) and \(t=3\), (i) if \(\delta_3(H)\ge\frac{n+9}{8}\), then \(H\) is Hamiltonian; (ii) if \(\delta_3(H)\ge\frac{n-6}{9}\), then either \(H\) is Hamiltonian, or \(H\) can be characterized by the Petersen graph.
These bounds on \(\delta_t(H)\) are sharp. Since the number of graphs of orders at most \(\max\{p/1+2t,3p/t+2t-7\}\) is finite for given \(p\) and \(t\), improvements to (a), (b) or (c) by increasing the value of \(p\) are possible with the help of a computer.Coloring and domination of vertices in triangle-free graphs.https://www.zbmath.org/1452.050562021-02-12T15:23:00+00:00"Dutton, Ronald"https://www.zbmath.org/authors/?q=ai:dutton.ronald-dSummary: Any dominating set of vertices in a triangle-free graph can be used to specify a graph coloring with at most one color class more than the number of vertices in the dominating set. This bound is sharp for many graphs. Properties of graphs for which this bound is achieved are presented.The matching number and Hamiitonicity of quasi-claw-free graphs.https://www.zbmath.org/1452.051412021-02-12T15:23:00+00:00"Li, Rao"https://www.zbmath.org/authors/?q=ai:li.rao|li.rao.1Summary: A graph \(G\) is quasi-claw-free if it satisfies the property: \(d(x,y)=2 \Rightarrow\) there exists \(u\in N(x)\cap N(y)\) such that \(N[u]\subseteq N[x]\cup N[y]\). The matching number of a graph \(G\) is the size of a maximum matching in the graph. In this note, we present a sufficient condition involving the matching number for the Hamiltonicity of quasi-claw-free graphs.Counting directed acyclic and elementary digraphs.https://www.zbmath.org/1452.050872021-02-12T15:23:00+00:00"De Panafieu, Élie"https://www.zbmath.org/authors/?q=ai:de-panafieu.elie"Dovgal, Sergey"https://www.zbmath.org/authors/?q=ai:dovgal.sergeyThe strongly connected components of directed acyclic graphs (DAGs) are only isolated vertices.
Using this fact, the authors discover that when \(m =cn\), where \(m\) is the number of directed edges, \(n\) is the number of vertices, and \(c <1\) is a constant, the asymptotic probability for a random digraph to be acyclic is an explicit function \(p(c) = e^{-c}(1- c)\).
When \(m = n(1 + \mu n^{-1/3})\), the asymptotic behavior changes, and the probability for a digraph to be acyclic becomes \(n^{-1/3}C(\mu)\), where \(C(\mu)\) is an explicit function of \(\mu\). \textit{T. Łuczak} and \textit{T. G. Seierstad} [Random Struct. Algorithms 35, No. 3, 271--293 (2009; Zbl 1214.05157)] showed that, as \(\mu \rightarrow -\infty\), the strongly connected components of a random digraph with \(n\) vertices and \(m = n(1 +\mu n^{-1/3})\) directed edges are, with high probability, only isolated vertices and cycles, and such digraphs are called elementary digraphs. The present authors also express the probability for a random digraph to be elementary as a function of \(\mu\).
These results are obtained using techniques from analytic combinatorics, developed in particular for the study of random graphs.
Reviewer: Xueliang Li (Tianjin)Note on \(p\)-competition graphs of double stars.https://www.zbmath.org/1452.050742021-02-12T15:23:00+00:00"Nakada, Kyohei"https://www.zbmath.org/authors/?q=ai:nakada.kyohei"Ogawa, Kenjiro"https://www.zbmath.org/authors/?q=ai:ogawa.kenjiro"Tagusari, Satoshi"https://www.zbmath.org/authors/?q=ai:tagusari.satoshi"Tsuchiya, Morimasa"https://www.zbmath.org/authors/?q=ai:tsuchiya.morimasaSummary: The \(p\)-competition graph \(C_p(D)\) of a digraph \(D=(V,A)\) is a graph with \(V(C_p(D))=V(D)\), and an edge between distinct vertices \(x\) and \(y\) if and only if there exist \(p\) distinct vertices \(v_1,v_2, \dots,v_p\in V\) such that \(x\to v_i\), \(y\to v_i\) are arcs of the digraph \(D\) for each \(i=1,2,\dots,p\). In this paper, we prove that double stars DS\(_m\) \((m\ge 2)\) are \(p\)-competition graphs. We also show that full regular \(m\)-ary trees \(T_{m,n}\) with height \(n\) are \(p\)-competition graphs, where \(p\le\frac{m-1}{2}\).On the Loebl-Komlós-Sós conjecture, lopsided trees, and certain caterpillars.https://www.zbmath.org/1452.050892021-02-12T15:23:00+00:00"Heissan, A. M."https://www.zbmath.org/authors/?q=ai:heissan.a-m"Tiner, G."https://www.zbmath.org/authors/?q=ai:tiner.garySummary: Let \(G\) be a graph with at least half of the vertices having degree at least \(k\). For a tree \(T\) with \(k\) edges, Loebl, Komlós, and Sós conjectured (see [\textit{P. Erdős} et al., Stud. Sci. Math. Hung. 30, No. 1--2, 47--57 (1995; Zbl 0849.05021)]) that \(G\) contains \(T\). It is known that if the length of a longest path in \(T\) (i.e., the diameter of \(T)\) is at most 5, then \(G\) contains \(T\). Since \(T\) is a bipartite graph, let \(\ell\) be the number of vertices in the smaller (or equal) part. Clearly \(1\le\ell\le\frac 12(k+1)\). In our main theorem, we prove that if \(1\le\ell\le\frac 16 k+1\), then the graph \(G\) contains \(T\). Notice that this includes certain trees of diameter up to \(\frac 13k+2\).
If a tree \(T\) consists of only a path and vertices that are connected to the path by an edge, then the tree \(T\) is a caterpillar. Let \(P\) be the path obtained from the caterpillar \(T\) by removing each leaf of \(T\), where \(P=a_1,\dots,a_r\). The path \(P\) is the spine of the caterpillar \(T\), and each vertex on the spine of \(T\) with degree at least 3 in \(T\) is a joint. It is known that the graph \(G\) contains certain caterpillars having at most two joints. If only odd-indexed vertices on the spine \(P\) are joints, then the caterpillar \(T\) is an odd caterpillar. If the spine \(P\) has at most \(\lceil\tfrac 12 k\rceil\) vertices, then \(T\) is a short caterpillar. We prove that the graph \(G\) contains every short, odd caterpillar with \(k\) edges.On the complexity of determining whether there is a unique Hamiltonian cycle or path.https://www.zbmath.org/1452.900632021-02-12T15:23:00+00:00"Hudry, Olivier"https://www.zbmath.org/authors/?q=ai:hudry.olivier"Lobstein, Antoine"https://www.zbmath.org/authors/?q=ai:lobstein.antoine-christopheSummary: The decision problems of the existence of a Hamiltonian cycle or of a Hamiltonian path in a given graph, and of the existence of a truth assignment satisfying a given Boolean formula \(\mathcal{C}\), are well-known \(NP\)-complete problems. Here we study the problems of the uniqueness of a Hamiltonian cycle or path in an undirected, directed or oriented graph, and show that they have the same complexity, up to polynomials, as the problem U-SAT of the uniqueness of an assignment satisfying \(\mathcal{C}\). As a consequence, these Hamiltonian problems are \(NP\)-hard and belong to the class \(DP\), like U-SAT.Quantifying sudden changes in dynamical systems using symbolic networks.https://www.zbmath.org/1452.370122021-02-12T15:23:00+00:00"Masoller, Cristina"https://www.zbmath.org/authors/?q=ai:masoller.cristina"Hong, Yanhua"https://www.zbmath.org/authors/?q=ai:hong.yanhua"Ayad, Sarah"https://www.zbmath.org/authors/?q=ai:ayad.sarah"Gustave, Francois"https://www.zbmath.org/authors/?q=ai:gustave.francois"Barland, Stephane"https://www.zbmath.org/authors/?q=ai:barland.stephane"Pons, Antonio J."https://www.zbmath.org/authors/?q=ai:pons.antonio-j"Gómez, Sergio"https://www.zbmath.org/authors/?q=ai:gomez.sergio-alejandro.1"Arenas, Alex"https://www.zbmath.org/authors/?q=ai:arenas.alexAscending subgraph decompositions of tournaments of order \(6n+5\).https://www.zbmath.org/1452.051432021-02-12T15:23:00+00:00"Wagner, Brian C."https://www.zbmath.org/authors/?q=ai:wagner.brian-cSummary: \textit{Y. Alavi} et al. [Congr. Numerantium 58, 7--14 (1987; Zbl 0641.05046)] conjectured that all graphs have an ascending subgraph decomposition (ASD). In previous papers, we showed that all tournaments of order congruent to 1, 2, or \(3\bmod 6\) have an ASD. In this paper, we will consider the case where the tournament has order congruent to 5 mod 6.Decompositions of various complete graphs into isomorphic copies of 4-cycles with three pendant edges.https://www.zbmath.org/1452.051362021-02-12T15:23:00+00:00"Abueida, Atif"https://www.zbmath.org/authors/?q=ai:abueida.atif-a"Alzahrani, Rabab"https://www.zbmath.org/authors/?q=ai:alzahrani.rababSummary: An \(H\)-decomposition of a graph \(G\) is a partition of the edges of \(G\) into copies isomorphic to \(H\). When the decomposition is not feasible, one looks for the best possible by minimizing; the number of unused edges (leave of a packing), or the number of reused edges (padding of a covering). We consider the \(H\)-decomposition, packing, and covering of the complete graphs and complete bipartite graphs, where \(H\) is a 4-cycle with three pendant edges.Bivariate domination polynomial.https://www.zbmath.org/1452.051262021-02-12T15:23:00+00:00"Preen, James"https://www.zbmath.org/authors/?q=ai:preen.james"Murray, Alexander"https://www.zbmath.org/authors/?q=ai:murray.alexander-gSummary: We introduce a new bivariate polynomial \[J(G;x,y):= \sum_{W \subseteq V(G)}x^{|W|}y^{|N[W]|-|W|}\] which contains the standard domination polynomial of the graph \(G\) in two different ways. We build methods for efficient calculation of this polynomial and prove that there are still some families of graphs which have the same bivariate polynomial.Further results on 3-difference cordial graphs.https://www.zbmath.org/1452.051642021-02-12T15:23:00+00:00"Ponraj, R."https://www.zbmath.org/authors/?q=ai:ponraj.r"Adaickalam, M. Maria"https://www.zbmath.org/authors/?q=ai:adaickalam.m-maria"Kala, R."https://www.zbmath.org/authors/?q=ai:kala.radoslaw|kala.rahulSummary: Let \(G\) be a \((p,q)\) graph. Let \(f:V(G)\to\{1,2,\dots,k\}\) be a map where \(k\) is an integer \(2\le k\le p\). For each edge \(uv\), assign the label \(|f(u)-f(v)|\). \(f\) is called \(k\)-difference cordial labeling of \(G\) if \(|v_f(i)-v_f(j)|\le 1\) and \(|e_f(0)-e_f(1)|\le 1\), where \(v_f(x)\) denotes the number of vertices labelled with \(x\), \(e_f(1)\) and \(e_f(0)\) respectively denote the number of edges labelled with 1 and not labelled with 1. A graph with a \(k\)-difference cordial labeling is called a \(k\)-difference cordial graph. In this paper we investigate the 3-difference cordial labeling behavior of slenting ladders, books with triangular pages, middle graphs of a path, shadow graphs of a path, triangular ladders, and the armed crowns.Non-self-centrality in the corona product of graphs.https://www.zbmath.org/1452.050452021-02-12T15:23:00+00:00"Berberler, Zeynep Nihan"https://www.zbmath.org/authors/?q=ai:berberler.zeynep-nihan-odabas"Berberler, Murat Ersen"https://www.zbmath.org/authors/?q=ai:berberler.murat-ersenSummary: The non-self-centrality number (NSC number for short) of a graph \(G\) is a novel graph invariant defined as follows: \(N(G)= \sum_{\substack{v_i,v_j\in V(G)\\v_i\ne v_j}}|\theta_{v_i}-\theta_{v_j}|\) where the summation goes over all the unordered pairs of vertices in \(G\) and \(\theta_{v_i}\) is the eccentricity of vertex \(v_i\) in \(G\). The third Zagreb eccentricity index of a graph \(G\) is also a novel graph invariant defined as \(E_3(G)=\sum_{v_iv_j\in E(G)}|\theta_{v_i}-\theta_{v_j}|\). \(E_3(G)\) is a good indicator for the non-self-centrality of a graph whereas \(N(G)\) is defined for better indicating the non-self-centrality of a graph. In this paper, explicit formulae are presented and algorithms that have polynomial time complexity are proposed for computing those eccentricity-related invariants for composite graphs.Some remarks on the annihilator graph of a commutative ring.https://www.zbmath.org/1452.050792021-02-12T15:23:00+00:00"Adlifard, M."https://www.zbmath.org/authors/?q=ai:adlifard.maryam"Payrovi, Sh."https://www.zbmath.org/authors/?q=ai:payrovi.shiroyehSummary: Let \(R\) be a commutative ring with nonzero identity. The annihilator graph of \(R\), denoted by \(AG(R)\), is the (undirected) graph whose vertex set is the set of all nonzero zero-divisors of \(R\) and two distinct vertices \(x\) and \(y\) are adjacent if and only if \(\text{ann}_R(xy)\neq{\text{ann}}_R(x)\cup{\text{ann}}_R(y)\). We investigate the interplay between ring-theoretic properties of \(R\) and graph-theoretic properties of \(AG(R)\). We study the relation between two graphs \(\Gamma(R)\) and \(AG(R)\), where \(R\) is a non-reduced commutative ring. Also, we completely characterize the rings whose annihilator graphs are complete.On minimal generating sets for symmetric and alternating groups.https://www.zbmath.org/1452.200032021-02-12T15:23:00+00:00"Iradmusa, Moharram N."https://www.zbmath.org/authors/?q=ai:iradmusa.moharram-n"Taleb, Reza"https://www.zbmath.org/authors/?q=ai:taleb.rezaSummary: By a famous result, the subgroup generated by the \(n\)-cycle \(\sigma =(1,2,\dots,n)\) and the transposition \(\tau =(a,b)\) is the full symmetric group \(S_{n}\) if and only if \(\gcd(n,b-a)=1\). In this paper, we first generalize the above result for one \(n\)-cycle and \(k\) arbitrary transpositions, and then provide similar necessary and sufficient conditions for the subgroups of \(S_{n}\) in the following three cases: first, the subgroup generated by the \(n\)-cycle \(\sigma \) and a 3-cycle \(\delta =(a,b,c)\), second, the subgroup generated by the \(n\)-cycle \(\sigma \) and a set of transpositions and 3-cycles, and third, by the \(n\)-cycle \(\sigma \) and an involution \((a,b)(c,d)\). In the first case, we also determine the structure of the subgroup generated by \((1,2,\dots,n)\) and a 3-cycle \(\delta =(a,b,c)\) in general. Finally, an application to unsolvability of a certain infinite family of polynomials by radicals is given.Edge imbalance sequences and their graphicness.https://www.zbmath.org/1452.050232021-02-12T15:23:00+00:00"Kozerenko, Sergiy"https://www.zbmath.org/authors/?q=ai:kozerenko.sergiySummary: The imbalance of a given edge in a graph is the absolute difference between the degrees of its vertices. The multiset of all edge imbalances in \(G\) is called its imbalance sequence and denoted by \(M_G\). In this paper, we focus on unary and binary graph operations that preserve the graphicness of imbalance sequences. For example, we prove that if a graph \(G^\prime\) is obtained from \(G\) by ``replacing'' each vertex with a complete graph of sufficiently large order, then the graphicness of \(M_G\) implies the graphicness of \(M_{G^\prime}\). Also, we discuss several conjectures related to the graphicness of the imbalance sequence of a graph and explore connections between them.Clustering coefficient of a spatial preferential attachment model.https://www.zbmath.org/1452.624512021-02-12T15:23:00+00:00"Iskhakov, L. N."https://www.zbmath.org/authors/?q=ai:iskhakov.l-n"Mironov, M. S."https://www.zbmath.org/authors/?q=ai:mironov.m-s"Prokhorenkova, L. A."https://www.zbmath.org/authors/?q=ai:prokhorenkova.l-a"Kamiński, B."https://www.zbmath.org/authors/?q=ai:kaminski.bogumil"Prałat, P."https://www.zbmath.org/authors/?q=ai:pralat.pawelSummary: The clustering structure of a graph in a spatial preferential attachment model whose similarity to real-world networks has been shown in many aspects is considered. The behavior of the local clustering coefficient is studied. Namely, the asymptotic behavior of its average value over all graph vertices of a certain degree as the graph size tends to infinity is examined. This characteristic has not been previously analyzed in the SPA model, and it reflects the typical dependence of the clustering structure near some vertex on its degree in the graph. Additionally, it is shown that, with a high probability, there is a vertex for which the value of the clustering coefficient differs from its average.Bounds of Zagreb type indices of strong product of four operations on connected graphs.https://www.zbmath.org/1452.050262021-02-12T15:23:00+00:00"Baby, Shakila"https://www.zbmath.org/authors/?q=ai:baby.shakila"Shafiq, Muhammad Kashif"https://www.zbmath.org/authors/?q=ai:shafiq.muhammad-kashif"Siddiqui, Hafiz Muhammad Afzal"https://www.zbmath.org/authors/?q=ai:afzal-siddiqui.hafiz-muhammadSummary: The first step in the analysis of a structure is to generate its configuration. The use of graph products is one of the means, available for this purpose. Chemical application of graph theory predicts different properties like physico-chemical properties, thermodynamics properties, chemical activity, biological activity, etc. These properties can be characterized by certain graph invariants known as topological indices. These indices play a vital role in QSAR/QSPR studies. In this paper, lower and upper bounds of Zagreb indices, multiple Zagreb indices and the F-index for the strong product of the F-sum on connected graphs are determined.Quantum curves for simple Hurwitz numbers of an arbitrary base curve.https://www.zbmath.org/1452.140332021-02-12T15:23:00+00:00"Liu, Xiaojun"https://www.zbmath.org/authors/?q=ai:liu.xiao-jun.2|liu.xiao-jun|liu.xiao-jun.1"Mulase, Motohico"https://www.zbmath.org/authors/?q=ai:mulase.motohico"Sorkin, Adam"https://www.zbmath.org/authors/?q=ai:sorkin.adamSummary: Various generating functions of simple Hurwitz numbers of the projective line are known to satisfy many properties. They include a heat equation, a cut-and-join recursion, an infinite-order differential equation called a quantum curve equation, and a Schrödinger like partial differential equation. In this paper we generalize these properties to simple Hurwitz numbers with an arbitrary base curve. For projective line case, the equivalency between the cut-and-join recursion and the Chekhov-Eynard-Orantin topological recursion has been proved. However, the relation between these two recursions are not discussed for the simple Hurwitz number we considered here.
For the entire collection see [Zbl 1404.14006].Criterion for the topological conjugacy of multi-dimensional gradient-like flows with no heteroclinic intersections on a sphere.https://www.zbmath.org/1452.370232021-02-12T15:23:00+00:00"Kruglov, V. E."https://www.zbmath.org/authors/?q=ai:kruglov.vladislav-e"Pochinka, O. V."https://www.zbmath.org/authors/?q=ai:pochinka.olga-vGradient-like flows on a $n$-dimensional (\(n\geqslant 3\)) sphere, such that invariant manifolds of different saddle points do not intersect, are considered. A bicolor graph for this class of flows is constructed. It is proved that two flows of this class are topological equivalent if and only if their graphs are isomorphic.
Reviewer: Valentine Tyshchenko (Grodno)On the number of lattice points in \(n\)-dimensional space with an application.https://www.zbmath.org/1452.111192021-02-12T15:23:00+00:00"Salman, Shatha A."https://www.zbmath.org/authors/?q=ai:salman.shatha-aSummary: The principal aim of this work is to provide a proof of a theorem that computes the coefficients of the Ehrhart polynomial in general form. An application for this computation in any dimension is given along with the procedure to calculate the number of lattice points in \(n\)-dimensional space with the aid of the Ehrhart polynomial of the output \(PQ\), for two polytopes \(P\) and \(Q\) whose dimensions are \(n\) and \(m\), respectively.Generating random networks from a given distribution.https://www.zbmath.org/1452.620392021-02-12T15:23:00+00:00"Carter, Nathan"https://www.zbmath.org/authors/?q=ai:carter.nathan-c"Hadlock, Charles"https://www.zbmath.org/authors/?q=ai:hadlock.charles-robert"Haughton, Dominique"https://www.zbmath.org/authors/?q=ai:haughton.dominique-m-aSummary: Several variations are given for an algorithm that generates random networks approximately respecting the probabilities given by any likelihood function, such as from a \(p^{*}\) social network model. A novel use of the genetic algorithm is incorporated in these methods, which improves its applicability to the degenerate distributions that can arise with \(p^{*}\) models. Our approach includes a convenient way to find the high-probability items of an arbitrary network distribution function.On rigidity of toric varieties arising from bipartite graphs.https://www.zbmath.org/1452.140032021-02-12T15:23:00+00:00"Portakal, Irem"https://www.zbmath.org/authors/?q=ai:portakal.iremIn this nicely written article, the author studies rigid toric varieties that arise from bipartite graphs. Let \(G\) be a simple graph with \(V(G)\) the set of its vertices and \(E(G)\) the set of edges. We define the edge ring to \(G\) as
\[\mathrm{Edr}(G):= \mathbb{C}[t_{i}t_{j} \, : \, \{i,j\} \in E(G)\,, i,j \in V(G)\}.\]
Consider the surjective ring morphism
\[\mathbb{C} [x_{e} \, : \, e \in E(G)] \rightarrow\mathrm{Edr}(G)\]
\[x_{e} \mapsto t_{i}t_{j},\]
where \(e = \{i,j\} \in E(G)\). The kernel \(I_{G}\) of this morphism is the well-known edge ideal. The associated toric variety to the graph \(G\) is defined as
\[\mathrm{TV}(G) : =\mathrm{Spec}(\mathbb{C}[x_{e} \, : \, e \in E(G) ] \, \backslash \, I_{G}) =\mathrm{Spec}(\mathbb{C}[\sigma^{\vee}_{G}\cap M]),\]
where \(\sigma^{\vee}_{G}\) is called the dual edge cone. The edge ring \(\mathrm{Edr}(G)\) is an integrally closed domain and hence \(\mathrm{ TV}(G)\) is a normal variety. In the present paper the author focuses on the case where \(G\) is a bipartite graph and the main goal of the paper is to understand the first order deformations of \(\mathrm{TV}(G)\). The main results of the paper provide certain criteria for the bipartite graph \(G\) such that the first oder deformation of \(\mathrm{TV}(G)\) are all trivial, which means that \(\mathrm{TV}(G)\) is rigid.
In the first step, the author describes the edge cone \(\sigma_{G}\) associated to the toric variety \(\mathrm{TV}(G)\). More precisely, the author shows a one-to-one correspondence between the set of extremal ray generators of the cone \(\sigma_{G}\) and the so-called first independent set (see Definition 2.7 therein). Using this approach one can determine the faces of \(\sigma_{G}\). For this, one defines a spanning subgraph \(G\{A\} \subset G\) associated to the first independent set \(A\). It turns out that a set \(S\) of \(d\) first independent sets (or equivalently, a set of \(d\) extremal rays of \(\sigma_{G}\)) spans a face of dimension \(d\) iff \(\bigcap_{A\in S}G\{A\}\) has \(d+1\) connected components. This result allows to prove that \(\mathrm{TV}(G)\) is smooth in codimension \(2\)
The first main result of the paper, devoted to the rigidity, can be formulated as follows.
Theorem A. Let \(G \subseteq K_{n,m}\) be a connected bipartite graph. Assume that the edge cone \(\sigma_{G}\) admits a three-dimensional non-simplicial face. Then \(\mathrm{TV}(G)\) is not rigid.
Moreover, we present the characterization of rigid affine toric varieties \(\mathrm{TV}(G)\), where \(G\) has exactly one two-side first independent set \(C = C_{1} \sqcup C_{2}\). In other words, one considers the connected bipartite graphs \(G \subseteq K_{n,m}\), where we remove all the edges between two vertex sets \(\emptyset \neq C_{1}\subseteq U_{1}\) and \(\emptyset \neq C_{2} \subseteq U_{2}\), where \(U_{1},U_{2}\) are disjoint sets of the bipartite graph \(G\).
Theorem B. Let \(G \subseteq K_{n,m}\) be a connected bipartite graph with exactly one two-side first independent set \(C \in \mathcal{I}^{1}_{G}\). Then
i) \(\mathrm{TV}(G)\) is not rigid if \(|C_{1}|=1\) and \(|C_{2}| = n-2\), or if \(|C_{1}| = m-2\) and \(|C_{2}| = 1\);
ii) \(\mathrm{TV}(G)\) is rigid, otherwise.
Reviewer: Piotr Pokora (Kraków)Reciprocal Steiner degree distance.https://www.zbmath.org/1452.050222021-02-12T15:23:00+00:00"Zhang, Xiaojuan"https://www.zbmath.org/authors/?q=ai:zhang.xiaojuanSummary: The concept of \(k\)-center Steiner degree distance, introduced by \textit{I. Gutman} [``Selected properties of the Schultz molecular topological index'', J. Chem. Inf. Comput. Sci. 34, No. 5, 1087--1089 (1994; \url{doi:10.1021/ci00021a009})], is a natural generalization of classical degree distance. In this paper, we introduce the concept of \(k\)-center reciprocal Steiner degree distance of a graph. The \(k\)-center reciprocal Steiner degree distance \(\mathrm{RSDD}_k(G)\) of a connected graph \(G\) is defined by \(\mathrm{RSDD}_k(G)=\sum_{\substack{S\subseteq V(G)\\|S|=k}}(\sum_{v\in S}\deg_G(v))\frac{1}{d_G(S)}\), where \(d_G(S)\) is the Steiner \(k\)-distance of \(S\) and \(\deg_G(v)\) is the degree of the vertex \(v\) in \(G\). Expressions for \(\mathrm{RSDD}_k\) for some special graphs are obtained. We also give sharp upper and lower bounds of \(\mathrm{RSDD}_k\) of a connected graph, and establish some of its properties in the case of trees.Minimal free resolution of monomial ideals by iterated mapping cone.https://www.zbmath.org/1452.130162021-02-12T15:23:00+00:00"Sharifan, Leila"https://www.zbmath.org/authors/?q=ai:sharifan.leilaSummary: In this paper, we study minimal free resolutions of some classes of monomial ideals. We first give a sufficient condition to check the minimality of the resolution obtained by the mapping cone. Using this condition, we obtain the Betti numbers of max-path ideals of rooted trees and ideals containing powers of variables. In particular, we discuss the resolutions of ideals of the form \(J_{\mathcal H}+(x_{i_1}^2,\dots, x_{i_m}^2)\), where \(J_{\mathcal H}\) is the edge ideal of a hypergraph \(\mathcal H\).Graph similarity through entropic manifold alignment.https://www.zbmath.org/1452.051112021-02-12T15:23:00+00:00"Escolano, Francisco"https://www.zbmath.org/authors/?q=ai:escolano.francisco"Hancock, Edwin R."https://www.zbmath.org/authors/?q=ai:hancock.edwin-robert"Lozano, Miguel A."https://www.zbmath.org/authors/?q=ai:lozano.miguel-angelA note on equitable total coloring of middle and total graph of some graphs.https://www.zbmath.org/1452.050622021-02-12T15:23:00+00:00"Jayaraman, G."https://www.zbmath.org/authors/?q=ai:jayaraman.girija"Muthuramakrishnan, D."https://www.zbmath.org/authors/?q=ai:muthuramakrishnan.dSummary: Among the varius coloring of graphs, the concept of equitable total coloring of graph \(G\) is the coloring of all its vertices and edges in which the number of elements in any two color classes differ by atmost one. The minimum number of colors required is called its equitable total chromatic number. In this paper, we obtained the equitable total chromatic number of the middle graph of a path, of the middle graph of a cycle, of the total graph of a path and of the total graph of a cycle.Convex envelopes on trees.https://www.zbmath.org/1452.352302021-02-12T15:23:00+00:00"Del Pezzo, Leandro M."https://www.zbmath.org/authors/?q=ai:del-pezzo.leandro-m"Frevenza, Nicolas"https://www.zbmath.org/authors/?q=ai:frevenza.nicolas"Rossi, Julio D."https://www.zbmath.org/authors/?q=ai:rossi.julio-danielSummary: We introduce two notions of convexity for an infinite regular tree. For these two notions we show that given a continuous boundary datum there exists a unique convex envelope on the tree and characterize the equation that this envelope satisfies. We also relate the equation with two versions of the Laplacian on the tree. Moreover, for a function defined on the tree, the convex envelope turns out to be the solution to the obstacle problem for this equation.The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm.https://www.zbmath.org/1452.903092021-02-12T15:23:00+00:00"Cheriyan, J."https://www.zbmath.org/authors/?q=ai:cheriyan.joseph"Dippel, J."https://www.zbmath.org/authors/?q=ai:dippel.j"Grandoni, F."https://www.zbmath.org/authors/?q=ai:grandoni.fabrizio"Khan, A."https://www.zbmath.org/authors/?q=ai:khan.arindam"Narayan, V. V."https://www.zbmath.org/authors/?q=ai:narayan.vishnu-vSummary: We present a \(\frac{7}{4}\) approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a \(\frac{7}{4}\) approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by
\textit{S. Vempala} and \textit{A. Vetta} for the (unweighted) min-size 2-ECSS problem [Lect. Notes Comput. Sci. 1913, 262--273 (2000; Zbl 0976.90114)].On two-quotient strong starters for \(\mathbb{F}_q\).https://www.zbmath.org/1452.050152021-02-12T15:23:00+00:00"Alfaro, Carlos A."https://www.zbmath.org/authors/?q=ai:alfaro.carlos-a"Rubio-Montiel, Christian"https://www.zbmath.org/authors/?q=ai:rubio-montiel.christian"Vázquez-Ávila, Adrián"https://www.zbmath.org/authors/?q=ai:vazquez-avila.adrianSummary: Let \(G\) be a finite additive abelian group of odd order \(n\), and let \(G^\ast=G\setminus\{0\}\) be the set of non-zero elements. A starter for \(G\) is a set \(S=\{\{x_i,y_i\}:i=1,\dots,\frac{n-1}{2}\}\) such that \[\cup^{\frac{n-1}{2}}_{i=1}\{x_i,y_i\}=G^\ast,\quad\text{and} \tag{1}\] \[\{\pm(x_i-y_i):i=1,\dots,\frac{n-1}{2}\}=G^\ast \tag{2}.\] Moreover, if \(|\{x_i+y_i:i=1,\dots,\frac{n-1}{2}\}|=\frac{n-1}{2}\), then \(S\) is called a strong starter for \(G\). A starter \(S\) for \(G\) is a \(k\) quotient starter if there is \(Q\subseteq G^\ast\) of cardinality \(k\) such that \(y_i/x_i\in Q\) or \(x_i/y_i\in Q\), for \(i=1,\dots,\frac{n-1}{2}\). In this paper, examples of two-quotient strong starters for \(\mathbb{F}_q\) will be given, where \(q=2^kt+1\) is a prime power with \(k>1\) a positive integer and \(t\) an odd integer greater than 1.Directed dominating set problem studied by cavity method: warning propagation and population dynamics.https://www.zbmath.org/1452.051702021-02-12T15:23:00+00:00"Habibulla, Yusupjan"https://www.zbmath.org/authors/?q=ai:habibulla.yusupjanProperties of annihilator graph of a commutative semigroup.https://www.zbmath.org/1452.050852021-02-12T15:23:00+00:00"Talebi, Yahya"https://www.zbmath.org/authors/?q=ai:talebi.yahya"Akbarzadeh, Sahar"https://www.zbmath.org/authors/?q=ai:akbarzadeh.saharSummary: Let \(S\) be a commutative semigroup with zero. Let \(Z(S)\) be the set of all zero-divisors of \(S\). We define the annihilator graph of \(S\), denoted by \(\operatorname{ANN}_G(S)\), as the undirected graph whose set of vertices is \(Z(S)^{\ast}=Z(S)-\{0\}\), and two distinct vertices \(x\) and \(y\) are adjacent if and only if \(\operatorname{ann}_S(xy)\neq \operatorname{ann}_S(x)\cap \operatorname{ann}_S(y)\). In this paper, we study some basic properties of \(\operatorname{ANN}_G(S)\) by means of \(\Gamma(S)\). We also show that if \(Z(S)\neq S\), then \(\operatorname{ANN}_G(S)\) is a subgraph of \(\Gamma(S)\). Moreover, we investigate some properties of the annihilator graph \(\operatorname{ANN}_G(S)\) related to minimal prime ideals of \(S\). We also study some connections between the domination numbers of annihilator graphs and zero-divisor graphs.On the anti-Kekulé number of \(k\)-polyomino system.https://www.zbmath.org/1452.050332021-02-12T15:23:00+00:00"Hayat, Sakander"https://www.zbmath.org/authors/?q=ai:hayat.sakander"Wang, Shaohui"https://www.zbmath.org/authors/?q=ai:wang.shaohuiSummary: The anti-Kekulé number of a graph \(G\) with a perfect matching, is defined to be the minimum number of edges that should be deleted such that the remaining graph is connected and contains no perfect matchings. This graph parameter finds potential applications in chemistry, especially in the stability and resonance energy of chemical compounds. For a graph \(G\) and a fixed positive integer \(\gamma\), the problem of finding whether the anti-Kekulé number of \(G\) is less than \(\gamma\), is NP-complete. The anti-Kekulé number of parallelograms, catacondensed benzenoids, fullerenes, triangular, rectangular and hexagonal grids has been investigated in a number of papers. In this paper, we propose the concepts of permitted induced subgraph and matching-based edge partitions in chemical graphs which help us to compute lower and upper bounds respectively on the anti-Kekulé number. We further use these concepts to investigate the anti-Kekulé number of the \(k\)-polyomino system which is a finite 2-connected plane graph such that each interior face (also called cell) is surrounded by a regular \(4k\)-cycle of length one. First, we calculate the exact value of the anti-Kekulé number of the \(k\)-polyomino system for \(k=1,2\). Finally, we prove the result for the general \(k\)-polyomino system by induction on \(k\).A tabu search heuristic for the equitable coloring problem.https://www.zbmath.org/1452.902762021-02-12T15:23:00+00:00"Méndez Díaz, Isabel"https://www.zbmath.org/authors/?q=ai:mendez-diaz.isabel"Nasini, Graciela"https://www.zbmath.org/authors/?q=ai:nasini.graciela-l"Severín, Daniel"https://www.zbmath.org/authors/?q=ai:severin.daniel-eSummary: The equitable coloring problem is a variant of the graph coloring problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods.
In this paper, we present a tabu search heuristic for the equitable coloring problem. This algorithm is an adaptation of the dynamic \textsc{TabuCol} version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given.
Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances.
For the entire collection see [Zbl 1319.90005].Parsimonious formulations for low-diameter clusters.https://www.zbmath.org/1452.900832021-02-12T15:23:00+00:00"Salemi, Hosseinali"https://www.zbmath.org/authors/?q=ai:salemi.hosseinali"Buchanan, Austin"https://www.zbmath.org/authors/?q=ai:buchanan.austinSummary: In the analysis of networks, one often searches for tightly knit clusters. One property of a ``good'' cluster is a small diameter (say, bounded by \(k)\), which leads to the concept of a \(k\)-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or dominate several previously existing formulations. Our best-performing formulation uses only node variables (quite unlike previous formulations) and imposes the diameter-at-most-\(k\) constraints via an exponentially large class of cut-like inequalities. A relatively simple implementation of the cut-like formulation easily outperforms previous approaches, solving dozens of instances of the maximum \(k\)-club problem in a second or two that would take hours by other formulations. Moreover, the cut-like formulation is more general in the sense that it applies even when distances are not measured in terms of hops. While we consider only the \(k\)-club problem in this paper, the proposed techniques may also be useful in other applications where compact solutions are key (e.g., political districting and wildlife reserve design).Roman \(k\)-domination number upon vertex and edge removal.https://www.zbmath.org/1452.051202021-02-12T15:23:00+00:00"Ghameshlou, Arezoo N."https://www.zbmath.org/authors/?q=ai:ghameshlou.arezoo-nazi"Golmohammadi, Hamidreza"https://www.zbmath.org/authors/?q=ai:golmohammadi.hamidreza"Moghaddam, S. M. Hosseini"https://www.zbmath.org/authors/?q=ai:moghaddam.seyed-mehdi-hosseini"Volkmann, Lutz"https://www.zbmath.org/authors/?q=ai:volkmann.lutzSummary: Let \(k\ge 1\) be an integer. A Roman \(k\)-dominating function on a graph \(G\) with vertex set \(V\) is a function \(f:V \to\{0,1,2\}\) such that every vertex \(v\in V\) with \(f(v)=0\) has at least \(k\) neighbors \(u_1,u_2, \dots,u_k\) with \(f(u_i)=2\) for \(i=1,2,\dots,k\). The weight of a Roman \(k\)-dominating function is the value \(f(V)=\sum_{v\in V}f(v)\). The minimum weight of Roman \(k\)-dominating functions on a graph \(G\) is called the Roman \(k\)-domination number, denoted by \(\gamma_{kR} (G)\). In this paper, we present bounds for the Roman \(k\)-domination number and we consider the effects of vertex and edge removal on the Roman \(k\)-domination number of a graph.Nonparametric analysis of extremes on web graphs: PageRank versus max-linear model.https://www.zbmath.org/1452.680202021-02-12T15:23:00+00:00"Markovich, Natalia M."https://www.zbmath.org/authors/?q=ai:markovich.natalia-m"Ryzhov, Maxim"https://www.zbmath.org/authors/?q=ai:ryzhov.maxim"Krieger, Udo R."https://www.zbmath.org/authors/?q=ai:krieger.udo-rSummary: We analyze the cluster structure in large networks by means of clusters of exceedances regarding the influence characteristics of nodes. As the latter characteristics we use PageRank and the Max-Linear model and compare their distributions and dependence structure. Due to the heaviness of tail and dependence of PageRank and Max-Linear model observations, the influence indices appear by clusters or conglomerates of nodes grouped around influential nodes. The mean size of such clusters is determined by a so called extremal index. It is related to the tail index that indicates the heaviness of the distribution tail. We consider graphs of Web pages and partition them into clusters of nodes by their influence.
For the entire collection see [Zbl 1393.68018].Graphical representations of cyclic permutation groups.https://www.zbmath.org/1452.200012021-02-12T15:23:00+00:00"Grech, Mariusz"https://www.zbmath.org/authors/?q=ai:grech.mariusz"Kisielewicz, Andrzej"https://www.zbmath.org/authors/?q=ai:kisielewicz.andrzej-piotrThe authors obtain a necessary and sufficient condition that a permutation group generated by a single permutation is an automorphism group of an edge-colored graph.
Reviewer: Mohammad-Reza Darafsheh (Tehran)Preference orders on families of sets -- when can impossibility results be avoided?https://www.zbmath.org/1452.911172021-02-12T15:23:00+00:00"Maly, Jan"https://www.zbmath.org/authors/?q=ai:maly.jan"Truszczyński, Miroslaw"https://www.zbmath.org/authors/?q=ai:truszczynski.miroslaw"Woltran, Stefan"https://www.zbmath.org/authors/?q=ai:woltran.stefanSummary: Lifting a preference order on elements of some universe to a preference order on subsets of this universe is often guided by postulated properties the lifted order should have. Well-known impossibility results pose severe limits on when such liftings exist if \textit{all} non-empty subsets of the universe are to be ordered. The extent to which these negative results carry over to other families of sets is not known. In this paper, we consider families of sets that induce connected subgraphs in graphs. For such families, common in applications, we study whether lifted orders satisfying the well-studied axioms of dominance and (strict) independence exist for every or, in another setting, for \textit{some} underlying order on elements (\textit{strong} and \textit{weak} orderability). We characterize families that are strongly and weakly orderable under dominance and strict independence, and obtain a tight bound on the class of families that are strongly orderable under dominance and independence.Orthogonal graphs modulo power of 2.https://www.zbmath.org/1452.050842021-02-12T15:23:00+00:00"Sriwongsa, Songpon"https://www.zbmath.org/authors/?q=ai:sriwongsa.songponSummary: In this work, we define an orthogonal graph on the set of equivalence classes of \((2v+\delta)\) tuples over \(\mathbb{Z}_{2^n}\), where \(n\) and \(\nu\) are positive integers and \(\delta =0,1\) or \(2\). We classify our graph if it is strongly regular or quasi-strongly regular and compute all parameters precisely. We show that our graph is arc transitive. The automorphisms group is given and the chromatic number of the graph except when \(\delta =0\) and \(\nu\) is odd is determined. Moreover, we work on subconstituents of this orthogonal graph.Spectral radius and Hamiltonian properties of graphs. II.https://www.zbmath.org/1452.051042021-02-12T15:23:00+00:00"Ge, Jun"https://www.zbmath.org/authors/?q=ai:ge.jun.1"Ning, Bo"https://www.zbmath.org/authors/?q=ai:ning.boSummary: In this paper, we first present spectral conditions for the existence of \(C_{n-1}\) in graphs (2-connected graphs) of order \(n\), which are motivated by a conjecture of Erdős. We also prove spectral conditions for the existence of Hamilton cycles in balanced bipartite graphs. This result presents a spectral analog of Moon-Moser's theorem on Hamilton cycles in balanced bipartite graphs, and extends a previous theorem due to \textit{B. Li} and \textit{B. Ning} [Linear Multilinear Algebra 64, No. 11, 2252--2269 (2016; Zbl 1352.05105)] for \(n\) sufficiently large. We conclude this paper with two problems on tight spectral conditions for the existence of long cycles of given lengths.
For Part I see [the authors, ibid. 63, No. 8, 1520--1530 (2015; Zbl 1332.05091)].On the multiplicity of distance signless Laplacian eigenvalues of graphs.https://www.zbmath.org/1452.051072021-02-12T15:23:00+00:00"Xue, Jie"https://www.zbmath.org/authors/?q=ai:xue.jie"Liu, Shuting"https://www.zbmath.org/authors/?q=ai:liu.shuting"Shu, Jinlong"https://www.zbmath.org/authors/?q=ai:shu.jinlongSummary: In this paper, we characterize all connected graphs, which have a distance signless Laplacian eigenvalue with multiplicity at least \(n-2\). As an application, we show that all these graphs, except \(K_2\vee 3K_1\) and \(K_1\vee(K_3+K_1)\), are determined by their distance signless Laplacian spectra. Moreover, we also determine all graphs with the third largest distance signless Laplacian eigenvalue equal \(n-2\).Parameterized complexity of independent set in H-free graphs.https://www.zbmath.org/1452.680902021-02-12T15:23:00+00:00"Bonnet, Édouard"https://www.zbmath.org/authors/?q=ai:bonnet.edouard"Bousquet, Nicolas"https://www.zbmath.org/authors/?q=ai:bousquet.nicolas"Charbit, Pierre"https://www.zbmath.org/authors/?q=ai:charbit.pierre"Thomassé, Stéphan"https://www.zbmath.org/authors/?q=ai:thomasse.stephan"Watrigant, Rémi"https://www.zbmath.org/authors/?q=ai:watrigant.remiSummary: In this paper, we investigate the complexity of \textsc{Maximum Independent Set} (MIS) in the class of \(H\)-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs \(H\), we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously \(K_{1, 4}\), any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of
\textit{K. Dabrowski} et al. [J. Discrete Algorithms 14, 207--213 (2012; Zbl 1247.68109)]
concerning \(C_4\)-free graphs. Then we extend the polynomial algorithm of
\textit{V. E. Alekseev} [``On the number of maximal independent sets in graphs from hereditary classes'' (Russian), in: Combinatorial-algebraic methods in discrete optimization. Nizhny Novgorod: University of Nizhny Novgorod. 5--8 (1991)]
when \(H\) is a disjoint union of edges to an FPT algorithm when \(H\) is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs \(H\).Parameterized leaf power recognition via embedding into graph products.https://www.zbmath.org/1452.681352021-02-12T15:23:00+00:00"Eppstein, David"https://www.zbmath.org/authors/?q=ai:eppstein.david"Havvaei, Elham"https://www.zbmath.org/authors/?q=ai:havvaei.elhamSummary: The \(k\)-leaf power graph \(G\) of a tree \(T\) is a graph whose vertices are the leaves of \(T\) and whose edges connect pairs of leaves at unweighted distance at most \(k\) in \(T\). Recognition of the \(k\)-leaf power graphs for \(k \ge 7\) is still an open problem. In this paper, we provide two algorithms for this problem for sparse leaf power graphs. Our results shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by \(k\) and by the degeneracy of the given graph. To prove this, we first describe how to embed a leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of \(k\) and the degeneracy of \(G\). The first presented algorithm uses methods based on monadic second-order logic \((\text{MSO}_2)\) to recognize the existence of a leaf power as a subgraph of the graph product. Using the same embedding in the graph product, the second algorithm presents a dynamic programming approach to solve the problem and provide a better dependence on the parameters.Dual parameterization of weighted coloring.https://www.zbmath.org/1452.681292021-02-12T15:23:00+00:00"Araújo, Júlio"https://www.zbmath.org/authors/?q=ai:araujo.julio-cesar-silva"Campos, Victor A."https://www.zbmath.org/authors/?q=ai:campos.victor-a"Lima, Carlos Vinícius G. C."https://www.zbmath.org/authors/?q=ai:lima.carlos-vinicius-g-c"dos Santos, Vinícius Fernandes"https://www.zbmath.org/authors/?q=ai:fernandes-dos-santos.vinicius"Sau, Ignasi"https://www.zbmath.org/authors/?q=ai:sau.ignasi"Silva, Ana"https://www.zbmath.org/authors/?q=ai:silva.ana-carolina|silva.ana-maria-f|silva.ana-l|silva.ana-t-cSummary: Given a graph \(G\), a proper \(k\)-coloring of \(G\) is a partition \(c = (S_i)_{i \in [1, k]}\) of \(V(G)\) into \(k\) stable sets \(S_1, \ldots, S_k\). Given a weight function \(w : V(G) \rightarrow \mathbb{R}^+\), the weight of a color \(S_i\) is defined as \(w(i) = \max_{v \in S_i} w(v)\) and the weight of a coloring \(c\) as \(w(c) = \sum_{i=1}^k w(i)\).
\textit{D. J. Guan} and \textit{X. Zhu} [Inf. Process. Lett. 61, No. 2, 77--81 (1997; Zbl 1336.05041)]
defined the weighted chromatic number of a pair \((G, w)\), denoted by \(\sigma (G, w)\), as the minimum weight of a proper coloring of \(G\). The problem of determining \(\sigma (G, w)\) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on \(n\)-vertex trees in time \(n^{o(\log n)}\) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph \((G, w)\) and an integer \(k\), is \(\sigma (G, w) \le \sum_{v \in V(G)} w(v) - k\)? This parameterization has been recently considered by
\textit{B. Escoffier} [Lect. Notes Comput. Sci. 9941, 50--61 (2016; Zbl 1417.05064)],
who provided an FPT algorithm running in time \(2^{{\mathcal{O}}(k \log k)} \cdot n^{{\mathcal{O}}(1)} \), and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time \(9^k \cdot n^{\mathcal{O}(1)}\), and prove that no algorithm in time \(2^{o(k)} \cdot n^{\mathcal{O}(1)}\) exists under the ETH. On the other hand, we present a kernel with at most \((2^{k-1} + 1) (k - 1)\) vertices, and rule out the existence of polynomial kernels unless \(\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}\), even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.Multivariate analysis of orthogonal range searching and graph distances.https://www.zbmath.org/1452.681342021-02-12T15:23:00+00:00"Bringmann, Karl"https://www.zbmath.org/authors/?q=ai:bringmann.karl"Husfeldt, Thore"https://www.zbmath.org/authors/?q=ai:husfeldt.thore"Magnusson, Måns"https://www.zbmath.org/authors/?q=ai:magnusson.mansSummary: We show that the eccentricities, diameter, radius, and Wiener index of an undirected \(n\)-vertex graph with nonnegative edge lengths can be computed in time \(O(n \cdot \begin{pmatrix} k + \lceil \log n\rceil \\ k \end{pmatrix} \cdot 2^k \log n)\), where \(k\) is linear in the treewidth of the graph. For every \(\epsilon > 0\), this bound is \(n^{1 + \epsilon} \exp O(k)\), which matches a hardness result of \textit{A. Abboud} et al. [in: Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 377--391 (2016; Zbl 1410.68392)]
and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of
\textit{S. Cabello} and \textit{C. Knauer} [Comput. Geom. 42, No. 9, 815--824 (2009; Zbl 1200.05218)]
in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form \(\log^d n\) to \(\begin{pmatrix}d + \lceil \log n\rceil \\ d \end{pmatrix}\), as originally observed by
\textit{L. Monier} [J. Algorithms 1, 60--74 (1980; Zbl 0435.68032)].
We also investigate the parameterization by vertex cover number.Counting induced subgraphs: a topological approach to \#W[1]-hardness.https://www.zbmath.org/1452.680862021-02-12T15:23:00+00:00"Roth, Marc"https://www.zbmath.org/authors/?q=ai:roth.marc"Schmitt, Johannes"https://www.zbmath.org/authors/?q=ai:schmitt.johannesSummary: We investigate the problem \(\# \mathsf{IndSub} (\Phi)\) of counting all induced subgraphs of size \(k\) in a graph \(G\) that satisfy a given property \(\Phi\). This continues the work of
\textit{M. Jerrum} and \textit{K. Meeks} who proved the problem to be \#W[1]-hard for some families of properties which include (dis)connectedness
[J. Comput. Syst. Sci. 81, No. 4, 702--716 (2015; Zbl 1320.68101)] and even- or oddness of the number of edges
[Combinatorica 37, No. 5, 965--990 (2017; Zbl 1413.68063)].
Using the recent framework of graph motif parameters due to
[\textit{R. Curticapean} et al., in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC'17. New York, NY: Association for Computing Machinery (ACM). 210--223 (2017; Zbl 1369.05191)],
we discover that for monotone properties \(\Phi\), the problem \(\# \mathsf{IndSub} (\Phi)\) is hard for \#W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of \(\Phi\) is non-zero. This observation links \(\# \mathsf{IndSub} (\Phi)\) to Karp's famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the ``topological approach to evasiveness'' which was introduced in the seminal paper of
\textit{J. Kahn} et al. [Combinatorica 4, 297--306 (1984; Zbl 0577.05061)],
we prove that \(\# \mathsf{IndSub} (\Phi)\) is \#W[1]-hard for every monotone property \(\Phi\) that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not \(k\)-edge-connected for \(k > 2\). Moreover, we show that for those properties \(\# \mathsf{IndSub} (\Phi)\) can not be solved in time \(f(k) \cdot n^{o(k)}\) for any computable function \(f\) unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that \(\# \mathsf{IndSub} (\Phi)\) is \#W[1]-hard if \(\Phi\) is any non-trivial modularity constraint on the number of edges with respect to some prime \(q\) or if \(\Phi\) enforces the presence of a fixed isolated subgraph.On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs.https://www.zbmath.org/1452.681312021-02-12T15:23:00+00:00"Barbero, Florian"https://www.zbmath.org/authors/?q=ai:barbero.florian"Isenmann, Lucas"https://www.zbmath.org/authors/?q=ai:isenmann.lucas"Thiebaut, Jocelyn"https://www.zbmath.org/authors/?q=ai:thiebaut.jocelynSummary: Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-problem may be of main interest. We introduce here a promising solution named \textsc{Distance Identifying Set}. The model contains \textsc{Identifying Code} (IC), \textsc{Locating Dominating Set} (LD) and their generalizations \(r\)-IC and \(r\)-LD where the closed neighborhood is considered up to distance \(r\). It also contains \textsc{Metric Dimension} (MD) and its refinement \(r\)-MD in which the distance between two vertices is considered as infinite if the real distance exceeds \(r\). Note that while IC = 1-IC and LD = 1-LD, we have \(\mathrm{MD} = \infty\text{-}\mathrm{MD}\); we say that MD is not local. In this article, we prove computational lower bounds for several problems included in \textsc{Distance Identifying Set} by providing generic reductions from \textsc{(Planar) Hitting Set} to the meta-problem. We focus on two families of problems from the meta-problem: the first one, called local, contains \(r\)-IC, \(r\)-LD and \(r\)-MD for each positive integer \(r\) while the second one, called 1-layered, contains LD, MD and \(r\)-MD for each positive integer \(r\). We have: (1) the 1-layered problems are NP-hard even in bipartite apex graphs, (2) the local problems are NP-hard even in bipartite planar graphs, (3) assuming ETH, all these problems cannot be solved in \(2^{o(\sqrt{n})}\) when restricted to bipartite planar or apex graph, respectively, and they cannot be solved in \(2^{o(n)}\) on bipartite graphs, and (4) except if \(\mathsf{W}[0] = \mathsf{W}[2]\), they do not admit parameterized algorithms in \(2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}\) even when restricted to bipartite graphs. Here \(k\) is the solution size of a relevant identifying set. In particular, \textsc{Metric Dimension} cannot be solved in \(2^{o(n)}\) under ETH, answering a question of
\textit{S. Hartung} and \textit{A. Nichterlein} [``On the parameterized and approximation hardness of metric dimension'', in: Proceedings of the 28th conference on computational complexity, CCC'13. Los Alamitos, CA: IEEE Computer Society. 266--276 (2013; \url{doi:10.1109/CCC.2013.36})].Minors of Hermitian (quasi-) Laplacian matrix of a mixed graph.https://www.zbmath.org/1452.051062021-02-12T15:23:00+00:00"Sarma, Deepak"https://www.zbmath.org/authors/?q=ai:sarma.deepakSummary: A mixed graph is obtained from an unoriented graph by orienting a subset of its edges. \textit{G. Yu} et al. [Appl. Math. Comput. 293, 287--292 (2017; Zbl 1411.05176)] have established the expression for the determinant of the Hermitian (quasi-) Laplacian matrix of a mixed graph. Here we find general expressions for all minors of the Hermitian (quasi-) Laplacian matrix of a mixed graph.A faster tree-decomposition based algorithm for counting linear extensions.https://www.zbmath.org/1452.682652021-02-12T15:23:00+00:00"Kangas, Kustaa"https://www.zbmath.org/authors/?q=ai:kangas.kustaa"Koivisto, Mikko"https://www.zbmath.org/authors/?q=ai:koivisto.mikko"Salonen, Sami"https://www.zbmath.org/authors/?q=ai:salonen.samiSummary: We investigate the problem of computing the number of linear extensions of a given \(n\)-element poset whose cover graph has treewidth \(t\). We present an algorithm that runs in time \(\tilde{O} (n^{t + 3})\) for any constant \(t\); the notation \(\tilde{O}\) hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters \(n\) and \(t\) alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.Hopf algebras and topological recursion.https://www.zbmath.org/1452.811152021-02-12T15:23:00+00:00"Esteves, João N."https://www.zbmath.org/authors/?q=ai:esteves.joao-nSummary: We first review our previous work where we considered a model for topological recursion based on the Hopf algebra of planar binary trees of Loday and Ronco and showed that extending this Hopf algebra by identifying pairs of nearest neighbour leaves and thus producing graphs with loops we obtain the full recursion formula of Eynard and Orantin. Then we discuss the algebraic structure of the spaces of correlation functions in \(g=0\) and in \(g> 0\). By taking a classical and a quantum product respectively we endow both spaces with a ring structure. This is an extended version of the contributed talk given at the 2016 von Neumann Symposium on Topological Recursion and its Influence in Analysis, Geometry and Topology, from 4 to 8 July 2016 at Hilton Charlotte University Place, USA.
For the entire collection see [Zbl 1404.14006].Monitoring the edges of a graph using distances.https://www.zbmath.org/1452.681362021-02-12T15:23:00+00:00"Foucaud, Florent"https://www.zbmath.org/authors/?q=ai:foucaud.florent"Klasing, Ralf"https://www.zbmath.org/authors/?q=ai:klasing.ralf"Miller, Mirka"https://www.zbmath.org/authors/?q=ai:miller.mirka"Ryan, Joe"https://www.zbmath.org/authors/?q=ai:ryan.joeSummary: We introduce a new graph-theoretic concept in the area of network monitoring. A set \(M\) of vertices of a graph \(G\) is a distance-edge-monitoring set if for every edge \(e\) of \(G\), there is a vertex \(x\) of \(M\) and a vertex \(y\) of \(G\) such that \(e\) belongs to all shortest paths between \(x\) and \(y\). We denote by \(\operatorname{dem}(G)\) the smallest size of such a set in \(G\). The vertices of \(M\) represent distance probes in a network modeled by \(G\); when the edge \(e\) fails, the distance from \(x\) to \(y\) increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge.
In this paper, we initiate the study of this new concept. We show that for a nontrivial connected graph \(G\) of order \(n\), \(1\le\operatorname{dem}(G)\le n-1\) with \(\operatorname{dem}(G)=1\) if and only if \(G\) is a tree, and \(\operatorname{dem}(G)=n-1\) if and only if it is a complete graph. We compute the exact value of \(\operatorname{dem}\) for grids, hypercubes, and complete bipartite graphs.
Then, we relate \(\operatorname{dem}\) to other standard graph parameters. We show that \(\operatorname{dem}(G)\) is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. It is also upper-bounded by five times its feedback edge set number.
Then, we show that determining \(\operatorname{dem}(G)\) for an input graph \(G\) is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikely to be fixed parameter tractable when parameterized by the solution size.
For the entire collection see [Zbl 1435.68020].Power domination in tree derived architectures.https://www.zbmath.org/1452.051172021-02-12T15:23:00+00:00"Anitha, J."https://www.zbmath.org/authors/?q=ai:anitha.j"Rajasingh, Indra"https://www.zbmath.org/authors/?q=ai:rajasingh.indraSummary: A set \(S\) of vertices in a graph \(G\) is called a dominating set of \(G\) if every vertex in \(V(G)\setminus S\) is adjacent to some vertex in \(S\). A set \(S\) is said to be a power dominating set of \(G\) if every vertex in the system is monitored by the set \(S\) following a set of rules for power system monitoring. A zero forcing set of \(G\) is a subset of vertices \(B\) such that if the vertices in \(B\) are colored blue and the remaining vertices are colored white initially, repeated application of the color change rule can color all vertices of \(G\) blue. The power domination number and the zero forcing number of \(G\) are the minimum cardinality of a power dominating set and the minimum cardinality of a zero forcing set respectively of \(G\). In this paper, we obtain the power domination number, total power domination number, zero forcing number and total forcing number for \(m\)-rooted sibling trees, \(l\)-sibling trees and \(l\)-binary trees. We also obtain the power domination number for circular ladders, Möbius ladders, and extended cycle-of-ladders.Centered triangular difference mean graphs.https://www.zbmath.org/1452.051602021-02-12T15:23:00+00:00"Jeyanthi, P."https://www.zbmath.org/authors/?q=ai:jeyanthi.pon"Selvi, M."https://www.zbmath.org/authors/?q=ai:selvi.m-salai-mathi|selvi.m-k-tamil"Ramya, D."https://www.zbmath.org/authors/?q=ai:ramya.dSummary: A graph \(G=(V,E)\) with \(p\) vertices and \(q\) edges is said to have centered triangular difference mean labeling if there is an injective mapping \(f:V(G)\to Z^+\) such that for each edge \(e=uv\), \(f^\ast(e)=\left\lceil\frac{|f(u)-f(v)|}{2}\right\rceil\) and the resulting edge labels are the first \(q\) centered triangular numbers. A graph that admits a centered triangular difference mean labeling is called a centered triangular difference mean graph. In this paper, we prove that the path \(P_n\), \(K_{1,n}\), \(C_n\odot K_1\), \(B_{m,n}\), \(C_n\) \((n>4)\), coconut tree, caterpillar \(S(n_1,n_2,n_3,\dots,n_m)\), \(C_n@ P_m\) \((n>4)\) and \(S_{m,n}\) are centered triangular difference mean graphs.The independent transversal total domination number of some graphs.https://www.zbmath.org/1452.051352021-02-12T15:23:00+00:00"Yue, Jun"https://www.zbmath.org/authors/?q=ai:yue.jun"Ge, Wei"https://www.zbmath.org/authors/?q=ai:ge.weiSummary: A total dominating set of a graph \(G\) having non empty intersection with all the independent sets of maximum cardinality in \(G\) is an independent transversal total dominating set. The minimum cardinality of any independent transversal total dominating set is denoted by \(\gamma_{tt}(G)\). In this paper, we mainly study on the bounds of independent transversal total dominating set of graphs, such as graphs with diameter 2, graphs with some special independence number, cographs and \(P_4\)-sparse graphs. Moreover, we list polynomial-time algorithms to compute the independent transversal total dominating numbers of cographs and \(P_4\)-sparse graphs.Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees.https://www.zbmath.org/1452.050542021-02-12T15:23:00+00:00"Chen, Meirun"https://www.zbmath.org/authors/?q=ai:chen.meirun"Naserasr, Reza"https://www.zbmath.org/authors/?q=ai:naserasr.rezaThe paper extends the notion of odd-girth to weighted graphs, and provides some classifications. It gives a necessary and sufficient condition for a graph of odd-girth $2k+1$ to bound all partial \(t\)-trees of odd-girth at least $2k+1$, and finds an optimal bound of odd-girth $2k + 1$ for partial 3-trees of odd-girth at least $2k + 1$.
A reformulation of the four color theorem is to say that $K_4$ is the smallest graph to which every planar loop-free graph admits a homomorphism. Extending this, it is shown that the Clebsch graph (a well-known triangle-free graph on 16 vertices) is the smallest graph to which every triangle-free planar graph admits a homomorphism. The paper also gives a necessary and sufficient condition for a graph of odd-girth $2k + 1$ to admit a homomorphism from any partial \(t\)-tree of odd-girth at least $2k + 1$. Finally, it is shown that every planar $(2k + 1)$-regular multigraph, whose dual is a partial 3-tree and whose fractional edge chromatic number is $2k + 1$, is $(2k + 1)$-edge-colorable.
Reviewer: Wai-Kai Chen (Fremont)More results on clique-chromatic numbers of graphs with no long path.https://www.zbmath.org/1452.050712021-02-12T15:23:00+00:00"Wichianpaisarn, Tanawat"https://www.zbmath.org/authors/?q=ai:wichianpaisarn.tanawat"Uiyyasathian, Chariya"https://www.zbmath.org/authors/?q=ai:uiyyasathian.chariyaSummary: The clique-chromatic number of a graph is the least number of colors on the vertices of the graph so that no maximal clique of size at least two is monochromatic. In [Discrete Math. 272, No. 2--3, 285--290 (2003; Zbl 1028.05033)], \textit{S. Gravier} et al. have shown that, for any graph \(F\), the class of \(F\)-free graphs has a bounded clique-chromatic number if and only if \(F\) is a vertex-disjoint union of paths, and they give an upper bound for all such cases. In this paper, their bounds for \(F=P_2+kP_1\) and \(F=P_3+kP_1\) with \(k \geq 3\) are significantly reduced to \(k+1\) and \(k+2\) respectively, and sharp bounds are given for some subclasses.
For the entire collection see [Zbl 1318.68008].Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane.https://www.zbmath.org/1452.050642021-02-12T15:23:00+00:00"Kano, Mikio"https://www.zbmath.org/authors/?q=ai:kano.mikio"Suzuki, Kazuhiro"https://www.zbmath.org/authors/?q=ai:suzuki.kazuhiro"Uno, Miyuki"https://www.zbmath.org/authors/?q=ai:uno.miyukiSummary: Let \(X\) be a set of multicolored points in the plane such that no three points are collinear and each color appears on at most \(\lceil |X|/2 \rceil \) points. We show the existence of a non-crossing properly colored geometric perfect matching on \(X\) (if \(|X|\) is even), and the existence of a non-crossing properly colored geometric spanning tree with maximum degree at most \(3\) on \(X\). Moreover, we show the existence of a non-crossing properly colored geometric perfect matching in the plane lattice. In order to prove these our results, we propose an useful lemma that gives a good partition of a sequence of multicolored points.
For the entire collection see [Zbl 1318.68008].Residue product of fuzzy graph structures.https://www.zbmath.org/1452.051462021-02-12T15:23:00+00:00"Akram, Muhammad"https://www.zbmath.org/authors/?q=ai:akram.muhammad"Sitara, Muzzamal"https://www.zbmath.org/authors/?q=ai:sitara.muzzamal"Saeid, Arsham Borumand"https://www.zbmath.org/authors/?q=ai:borumand-saeid.arshamSummary: In this research paper, we introduce the concept of residue product of fuzzy graph structures and explain with examples. Moreover, we discuss degree, \(\mu_i\)-degree, total degree, \(\mu_i\)-total degree of vertex in residue product of fuzzy graph structures and investigate some of their properties. Further, we discuss identification of prominent relationships in decision making by our proposed algorithm.Interval-valued intuitionistic fuzzy competition graph.https://www.zbmath.org/1452.051502021-02-12T15:23:00+00:00"Talebi, A. A."https://www.zbmath.org/authors/?q=ai:talebi.ali-asghar"Rashmanlou, Hossein"https://www.zbmath.org/authors/?q=ai:rashmanlou.hossein"Sadati, S. H."https://www.zbmath.org/authors/?q=ai:sadati.seyed-hasan|sadati.seyed-hosseinSummary: Fuzzy competition graph is the segment of competition graph. We study a special type of fuzzy competition graph. In this paper, intervalvalued intuitionistic fuzzy competition graph of an interval-valued intuitionistic fuzzy digraph is introduced. We investigated their properties. Also, comparison of homomorphism properties between the several of interval-valued intuitionistic fuzzy competition graphs and their corresponding are established. An application of this graph is considered in food web competitionDifferent types of arcs in \(m\)-polar fuzzy graphs with application.https://www.zbmath.org/1452.051482021-02-12T15:23:00+00:00"Mandal, Sonia"https://www.zbmath.org/authors/?q=ai:mandal.sonia"Sahoo, Sankar"https://www.zbmath.org/authors/?q=ai:sahoo.sankar"Ghorai, Ganesh"https://www.zbmath.org/authors/?q=ai:ghorai.ganesh"Pal, Madhumangal"https://www.zbmath.org/authors/?q=ai:pal.madhumangalSummary: Recently, \(m\)-polar fuzzy graph (\(m\)PFG) becomes a growing research topic as it is the generalization of fuzzy graph. In this paper, at first \(\alpha\)-strong \(m\)PF arc, \(\beta\)-strong \(m\)PF arc, \(\delta\)-strong \(m\)PF arc and \(\delta^\ast\)-strong \(m\)PF arc in an \(m\)PFG are defined. An application of decision making using strong path is also given at the end.On computing the irregularity of \(R\)-corona product types of graphs.https://www.zbmath.org/1452.051532021-02-12T15:23:00+00:00"Berberler, Zeynep Nihan"https://www.zbmath.org/authors/?q=ai:berberler.zeynep-nihan-odabasSummary: The imbalance of an edge \(uv\) in a graph \(G\) is defined as \(|d(u)-d(v)|\), where \(d(u)\) denotes the degree of \(u\). The irregularity of \(G\), denoted \(irr(G)\), is the sum of the edge imbalances taken over all edges in \(G\). In this paper, we focus our investigation to the study of how the irregularity of a graph changes with operations based on \(R\)-graphs. Furthermore, we find exact formulae for the irregularity of a class of composite graphs, namely, \(R\)-corona products.Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs.https://www.zbmath.org/1452.681392021-02-12T15:23:00+00:00"Liu, Pengcheng"https://www.zbmath.org/authors/?q=ai:liu.pengcheng"Zhang, Zhao"https://www.zbmath.org/authors/?q=ai:zhang.zhao"Huang, Xiaohui"https://www.zbmath.org/authors/?q=ai:huang.xiaohuiSummary: In this paper, we study the minimum (connected) \(k\)-bounded-degree node deletion problem (Min\((C)k\)BDND). For a connected graph \(G\), a constant \(k\) and a weight function \(w : V \to \mathbb{R}^+\), a vertex set \(C \subseteq V(G)\) is a \(k\) BDND-set if the maximum degree of graph \(G - C\) is at most \(k\). If furthermore, the subgraph of \(G\) induced by \(C\) is connected, then \(C\) is a \(Ck\) BDND-set. The goal of MinW\(k\)BDND (resp. MinWC\(k\)BDND) is to find a \(k\)BDND-set (resp. \(Ck\)BDND-set) with the minimum weight. In this paper, we focus on their cardinality versions with \(w(v) \equiv 1\), \(v \in V\), which are denoted as Min\(k\)BDND and MinC\(k\)BDND. This paper presents a \((1 + \varepsilon)\) and a 3.76-approximation algorithm for Min\(k\)BDND and MinC\(k\)BDND on unit disk graphs, respectively, where \(0 < \varepsilon < 1\) is an arbitrary constant.Some results and examples on vertex equitable labeling.https://www.zbmath.org/1452.051542021-02-12T15:23:00+00:00"Aboshady, Mohamed"https://www.zbmath.org/authors/?q=ai:aboshady.mohamed"Seoud, Mohamed"https://www.zbmath.org/authors/?q=ai:seoud.mohamed-abdel-azim"Elbarkouky, Reda"https://www.zbmath.org/authors/?q=ai:elbarkouky.reda"Roshdy, Eliwa"https://www.zbmath.org/authors/?q=ai:roshdy.eliwaSummary: In this paper we present a survey for all graphs with order at most 6 whether they are vertex equitable or not and we get an upper bound for the number of edges of any graph with \(p\) vertices to be a vertex equitable graph. Also, we establish vertex equitable labeling for the \(m\)-chain of the complete bipartite graph \(K_{2,n}\) and for the graph \(P_n\times P_m\).Quantum probability aspects to lexicographic and strong products of graphs.https://www.zbmath.org/1452.051862021-02-12T15:23:00+00:00"Obata, Nobuaki"https://www.zbmath.org/authors/?q=ai:obata.nobuakiSummary: The adjacency matrix of the lexicographic product of graphs is decomposed into a sum of monotone independent random variables in a certain product state. The adjacency matrix of the strong product of graphs admits an expression in terms of commutative independent random variables in a product state. Their spectral distributions are obtained by using the monotone, classical and Mellin convolutions of probability distributions.Edge monophonic chromatic number of a graph.https://www.zbmath.org/1452.050662021-02-12T15:23:00+00:00"Khayyoom, M. Mohammed Abdul"https://www.zbmath.org/authors/?q=ai:khayyoom.m-mohammed-abdulSummary: The edge monophonic number is a distance related parameter and the chromatic number is a domination related parameter of connected graphs. This paper combines these two parameters and study a new parameter called edge monophonic chromatic number. A set \(E\) of vertices of \(G\) is an edge monophonic chromatic set if \(E\) is both an edge monophonic set and a chromatic set. The minimum cardinality among all edge monophonic chromatic sets is called edge monophonic chromatic number and is denoted by \(\chi_{\text{em}}(G)\). Here, the edge monophonic chromatic number of some standard graphs are identified. For \(3\le m\le n\) there is a connected graph \(G\) of order \(n\) such that \(\chi_{\text{em}}(G)=m\). For \(3\ge r\ge s\ge t\) there is a connected graph \(G\) such that \(\chi(G)=r\), \(\chi_m(G)=s\) and \(\chi_{\text{em}}(G)=t\).Unbiased sampling of network ensembles.https://www.zbmath.org/1452.051742021-02-12T15:23:00+00:00"Squartini, Tiziano"https://www.zbmath.org/authors/?q=ai:squartini.tiziano"Mastrandrea, Rossana"https://www.zbmath.org/authors/?q=ai:mastrandrea.rossana"Garlaschelli, Diego"https://www.zbmath.org/authors/?q=ai:garlaschelli.diegoFrom gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more.https://www.zbmath.org/1452.680832021-02-12T15:23:00+00:00"Chalermsook, Parinya"https://www.zbmath.org/authors/?q=ai:chalermsook.parinya"Cygan, Marek"https://www.zbmath.org/authors/?q=ai:cygan.marek"Kortsarz, Guy"https://www.zbmath.org/authors/?q=ai:kortsarz.guy"Laekhanukit, Bundit"https://www.zbmath.org/authors/?q=ai:laekhanukit.bundit"Manurangsi, Pasin"https://www.zbmath.org/authors/?q=ai:manurangsi.pasin"Nanongkai, Danupon"https://www.zbmath.org/authors/?q=ai:nanongkai.danupon"Trevisan, Luca"https://www.zbmath.org/authors/?q=ai:trevisan.lucaOn approximating the number of \(k\)-cliques in sublinear time.https://www.zbmath.org/1452.682762021-02-12T15:23:00+00:00"Eden, Talya"https://www.zbmath.org/authors/?q=ai:eden.talya"Ron, Dana"https://www.zbmath.org/authors/?q=ai:ron.dana"Seshadhri, C."https://www.zbmath.org/authors/?q=ai:seshadhri.comandurCounting thin subgraphs via packings faster than meet-in-the-middle time.https://www.zbmath.org/1452.681332021-02-12T15:23:00+00:00"Björklund, Andreas"https://www.zbmath.org/authors/?q=ai:bjorklund.andreas"Kaski, Petteri"https://www.zbmath.org/authors/?q=ai:kaski.petteri"Kowalik, Łukasz"https://www.zbmath.org/authors/?q=ai:kowalik.lukaszLinked partition ideals, directed graphs and \(q\)-multi-summations.https://www.zbmath.org/1452.111262021-02-12T15:23:00+00:00"Chern, Shane"https://www.zbmath.org/authors/?q=ai:chern.shaneIn [Bull. Am. Math. Soc. 80, 1033--1052 (1974; Zbl 0301.10016)] \textit{G. E. Andrews} studied systematically Rogers-Ramanujan type identities and developed a general theory in which the concept of linked partition ideals was introduced.
As a follow-ups work of \textit{Z. Li} and the author [Discrete Math. 343, No. 7, Article ID 111876, 23 p. (2020; Zbl 1440.05021)], the author investigates the generating function identities of linked partition ideals in the setting of basic graph theory.
To this end, he first studies some \(q\)-differential systems, which eventually lead to a factorization problem of a special type of column functional vectors involving \(q\)-multi-summations. With the help of recurrence relation enjoyed by certain \(q\)-multi-summations, the author next provides non-computer-assisted proofs of some Andrews-Gordon type generating function identities. Interestingly, these proofs also have an interesting connection with binary trees. Moreover, he gives illustrations of constructing a linked partition ideal, or more loosely, a set of integer partitions whose generating function corresponds to a given set of special \(q\)-multi-summations. Finally, the author presents some interesting open problems to motivate further investigation.
Reviewer: Dazhao Tang (Chongqing)Improved approximation algorithm for Steiner \(k\)-forest with nearly uniform weights.https://www.zbmath.org/1452.682752021-02-12T15:23:00+00:00"Dinitz, Michael"https://www.zbmath.org/authors/?q=ai:dinitz.michael-h"Kortsarz, Guy"https://www.zbmath.org/authors/?q=ai:kortsarz.guy"Nutov, Zeev"https://www.zbmath.org/authors/?q=ai:nutov.zeevExtremal unicyclic graphs with respect to the reformulated reciprocal product-degree distance.https://www.zbmath.org/1452.050252021-02-12T15:23:00+00:00"Wang, Yipei"https://www.zbmath.org/authors/?q=ai:wang.yipei"Chen, Zhibing"https://www.zbmath.org/authors/?q=ai:chen.zhibing"Su, Guifu"https://www.zbmath.org/authors/?q=ai:su.guifuSummary: The reformulated reciprocal product-degree distance of a connected graph \(G\) is defined as \[\mathrm{RDD}^t_\times=\mathrm{RDD}^t_\times(G)= \sum_{\substack{\{u,v\}\subseteq V(G)\\ u\ne v}} \frac{\delta_G(u) \delta_G(v)}{d_G(u,v)+t},t\ge 0,\] where \(\delta_G(u)\) is the degree of vertex \(u\), and \(d_G(u,v)\) is the distance between vertices \(u\) and \(v\) in \(G\). This graph invariant is the generalization of the \(t\)-Harary index in \textit{K. C. Das} et al. [J. Inequal. Appl. 2013, Paper No. 339, 16 p. (2013; Zbl 1283.05238)] and the reciprocal product-degree distance of \textit{Y. Alizadeh} et al. [Discrete Math. 313, No. 1, 26--34 (2013; Zbl 1254.05191)], respectively. In this paper, we determine completely the extremal graph among all unicyclic graphs with \(n\) vertices in terms of the reformulated reciprocal product-degree distance.Three-color graph of the Morse flow on a compact surface with boundary.https://www.zbmath.org/1452.370502021-02-12T15:23:00+00:00"Prishlyak, A. O."https://www.zbmath.org/authors/?q=ai:pryshlyak.oleksandr-olegovych"Prus, A. A."https://www.zbmath.org/authors/?q=ai:prus.andrii-amatoliiovychSummary: We consider Morse flows on compact surfaces with boundary and construct a complete topological invariant of these flows (an equipped three-color graph). The vertices of this graph correspond to standard domains on the surface in the form of curvilinear triangles or quadrangles. We establish conditions under which this three-color graph specifies a Morse flow. We find the number of topologically nonequivalent Morse flows with at most five standard domains on the surfaces with boundary.A central limit theorem in the \(\beta \)-model for undirected random graphs with a diverging number of vertices.https://www.zbmath.org/1452.622142021-02-12T15:23:00+00:00"Yan, Ting"https://www.zbmath.org/authors/?q=ai:yan.ting"Xu, Jinfeng"https://www.zbmath.org/authors/?q=ai:xu.jinfengSummary: \textit{S. Chatterjee} et al. [Ann. Appl. Probab. 21, No. 4, 1400--1435 (2011; Zbl 1234.05206)] established the consistency of the maximum likelihood estimator in the \(\beta\)-model for undirected random graphs when the number of vertices goes to infinity. By approximating the inverse of the Fisher information matrix, we prove asymptotic normality of the maximum likelihood estimator under mild conditions. Simulation studies and a data example illustrate the theoretical results.Partitioning a graph into small pieces with applications to path transversal.https://www.zbmath.org/1452.681372021-02-12T15:23:00+00:00"Lee, Euiwoong"https://www.zbmath.org/authors/?q=ai:lee.euiwoongSummary: Given a graph \(G = (V, E)\) and an integer \(k \in \mathbb{N}\), we study \(k\)-\textsc{Vertex Separator} (resp. \(k\)-\textsc{Edge Separator}), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has less than \(k\) vertices. We also study \(k\)-\textsc{Path Transversal}, where the goal is to remove the minimum number of vertices such that there is no simple path of length \(k\). Our main results are the following improved approximation algorithms.\begin{itemize} \item[--] \(O(\log k)\)-approximation algorithm for \(k\)-\textsc{Vertex Separator} that runs in time \(2^{O(k)} n + n^{O(1)}\). It improves the simple \(k\)-approximation, and runs faster than the lower bound \(k^{\varOmega (\mathsf{OPT})} n^{\varOmega (1)}\) for exact algorithms assuming the exponential time hypothesis (ETH) when \(\mathsf{OPT}> k\). We also prove that there is no \(n^{(1/\log \log n)^c}\)-approximation algorithm that runs in time \(\operatorname{poly}(n, k)\) assuming the ETH. \item[--] \(O(\log k)\)-approximation algorithm for \(k\)-\textsc{Edge Separator} that runs in time \(n^{O(1)}\). It improves the best previous graph partitioning algorithm for small \(k = n^{o(1)}\). \item[--] \(O(\log k)\)-approximation algorithm for \(k\)-\textsc{Path Transversal} that runs in time \(n^{O(1)} + 2^{O(k^3 \log k)} n^{2} \log n\). Previously, the existence of an \((1 - \delta )k\)-approximation algorithm for fixed \(\delta > 0\) (even using \(n^{f(k)}\) time) was open. \end{itemize}Intersections of subgroups in virtually free groups and virtually free products.https://www.zbmath.org/1452.200212021-02-12T15:23:00+00:00"Klyachko, Anton A."https://www.zbmath.org/authors/?q=ai:klyachko.anton-a"Ponfilenko, Anastasia N."https://www.zbmath.org/authors/?q=ai:ponfilenko.anastasia-nThe authors prove the following generalisation of the Friedman-Mineyev theorem (earlier known as the Hanna Neumann conjecture): if \(A\) and \(B\) are nontrivial free subgroups of any group containing a free subgroup of index \(n\), then \(\mbox{rank}(A \cap B) - 1 \leq n (\mbox{rank}(A) - 1) (\mbox{rank}(B) - 1)\). Also they show that for any natural numbers \(k, l, n\) there exists a group \(G\) containing free subgroups \(A\), \(B\) and \(F\) such that rank\((A) = k\), rank\((B) = l\), \(|G:F| = n\) and this inequality is an equality.
Reviewer: Alexander Ivanovich Budkin (Barnaul)Domination number and Hamiltonicity of graphs.https://www.zbmath.org/1452.050992021-02-12T15:23:00+00:00"Li, Rao"https://www.zbmath.org/authors/?q=ai:li.rao|li.rao.1Summary: Let \(G\) be a \(k\)-connected \((k\ge 2)\) graph of order \(n\). If \(\gamma(G^c)\ge n-k\), then \(G\) is Hamiltonian or \(K_k\vee K^c_{k+1}\), where \(\gamma(G^c)\) is the domination number of the complement of the graph \(G\).Chromatic index of simple hypergraphs.https://www.zbmath.org/1452.050722021-02-12T15:23:00+00:00"Zhang, Guo-Hui"https://www.zbmath.org/authors/?q=ai:zhang.guohui"Skinner, Brett"https://www.zbmath.org/authors/?q=ai:skinner.brettThe authors consider the problem of edge coloring of simple hypergraphs. There is a very well-known conjecture given independly by \textit{C. Berge} [in: Combinatorial mathematics, Proc. 3rd Int. Conf., New York/ NY (USA) 1985, Ann. N. Y. Acad. Sci. 555, 40--44 (1989; Zbl 0726.05055)] and \textit{Z. Füredi} [Graphs Comb. 2, 89--92 (1986; Zbl 0589.05036)]. It says that \(\chi^\prime(H)\leq \Delta(H)+1\) for any simple hypergraph \(H\). The authors prove this conjecture for simple hypergraphs of degree at most 5. Moreover, they give a new upper bound on the chromatic index of the hypergraph \(H\), namely \(\chi^\prime(H)\leq \frac{7}{4}\Delta(H) - 1\).
The paper gives a very nice contribution to the problem of hyperedge coloring.
Reviewer: Hanna Furmańczyk (Gdańsk)Italian domination in digraphs.https://www.zbmath.org/1452.051322021-02-12T15:23:00+00:00"Volkmann, Lutz"https://www.zbmath.org/authors/?q=ai:volkmann.lutzSummary: An Italian dominating function on a digraph \(D\) with vertex set \(V(D)\) is defined as a function \(f:V(D)\to\{0,1,2\}\) such that every vertex \(v\in V(D)\) with \(f(v)=0\) has at least two in-neighbors assigned 1 under \(f\) or one in-neighbor \(w\) with \(f(w)=2\). The weight of an Italian dominating function is the sum \(\sum_{v\in V(D)}f(v)\), and the minimum weight of an Italian dominating function \(f\) is the Italian domination number, denoted by \(\gamma_I(D)\). We initiate the study of the Italian domination number for digraphs, and we present different sharp bounds on \(\gamma_I(D)\). In addition, we determine the Italian domination number of some classes of digraphs. As applications of the bounds and properties on the Italian domination number in digraphs, we give some new and some known results of the Italian domination number in graphs.Wiener index for common neighborhood graphs of special trees.https://www.zbmath.org/1452.050402021-02-12T15:23:00+00:00"Subhashini, A."https://www.zbmath.org/authors/?q=ai:subhashini.a"Babujee, J. Baskar"https://www.zbmath.org/authors/?q=ai:babujee.j-baskarSummary: Molecular graphs are models of molecules in which atoms are represented by vertices and chemical bonds by edges of a graph. Graph invariant numbers reflecting certain structural features of a molecule that are derived from its molecular graph are known as topological indices. A topological index is a numerical descriptor of a molecule, based on a certain topological feature of the corresponding molecular graph. One of the most widely known topological descriptor is the Wiener index. The Wiener index \(W(G)\) of a graph \(G\) is defined as the half of the sum of the distances between every pair of vertices of \(G\). The construction and investigation of topological indices is one of the important directions in mathematical chemistry. The common neighborhood graph of \(G\), denoted by \(\operatorname{con}(G)\), has the same vertex set as \(G\), and two vertices of \(\operatorname{con}(G)\) are adjacent if they have a common neighbor in \(G\). In this paper we investigate the Wiener index of the \(Y\)-tree, the \(X\)-tree, the \(\operatorname{con}(Y\)-tree) and the \(\operatorname{con}(X\)-tree).Domination in transformation graph \(G^{xy^-}\).https://www.zbmath.org/1452.051342021-02-12T15:23:00+00:00"Wang, Tao"https://www.zbmath.org/authors/?q=ai:wang.tao.7|wang.tao.9|wang.tao.2|wang.tao.1|wang.tao.8|wang.tao.3|wang.tao.6|wang.tao.5"Wu, Baoyindureng"https://www.zbmath.org/authors/?q=ai:wu.baoyindurengSummary: Let \(G=(V(G),E(G))\) be a simple undirected graph of order \(n\) and size \(m\), and \(x\), \(y\), \(z\) be three variables taking value \(+\) or \(-\). The transformation graph \(G^{xy-}\) of \(G\) is the graph with vertex set \(V(G)\cup E(G)\) in which the vertex \(\alpha\) and \(\beta\) are joined by an edge if one of the following conditions holds: (i) \(\alpha,\beta\in V(G)\), and \(\alpha\) and \(\beta\) are adjacent in \(G\) if \(x=+\), and \(\alpha\) and \(\beta\) are not adjacent in \(G\) if \(x=-\), (ii) \(\alpha,\beta \in E(G)\), and \(\alpha\) and \(\beta\) are adjacent in \(G\) if \(Y=+\), and \(\alpha\) and \(\beta\) are not adjacent in \(G\) if \(y=-\), (iii) one of \(\alpha\) and \(\beta\) is in \(V(G)\) and the other is in \(E(G)\), and they are not incident in \(G\).
In this note, it is shown that \(\gamma(G^{xy-})\le 3\) for a nonempty graph \(G\) and for any \(x,y\in\{+,-\}\), with a unified proof. Furthermore, we characterize the graph \(G\) with \(\gamma(G^{xy-})=k\) for each \(k\in\{1,2,3\}\), where \(x,y\in\{+,-\}\). As a consequence, a minimum dominating set of \(G^{xy-}\) can be found in polynomial time (in linear time in some cases).Antimagicness of star forests.https://www.zbmath.org/1452.051582021-02-12T15:23:00+00:00"Chen, Zhen-Chun"https://www.zbmath.org/authors/?q=ai:chen.zhen-chun"Huang, Kuo-Ching"https://www.zbmath.org/authors/?q=ai:huang.kuo-ching"Shang, Jen-Ling"https://www.zbmath.org/authors/?q=ai:shang.jen-ling"Lee, Ming-Ju"https://www.zbmath.org/authors/?q=ai:lee.ming-juSummary: An edge labeling of a graph \(G\) is a bijection \(f:E(G)\to\{1,2,\dots, |E(G)|\}\). The induced vertex sum \(f^+\) of \(f\) is a function defined on \(V(G)\) given by \(f^+(u)=\sum_{uv\in E(G)}f(uv)\) for all \(u\in V(G)\). The value \(f^+(u)\) is called the vertex sum at \(u\). The graph \(G\) is called antimagic if there exists an edge labeling of \(G\) such that the vertex sums at all vertices of \(G\) are distinct. A star forest is the union of disjoint stars. Let \(S_n\) denote a star with \(n\) edges, and \(mS_n\) denote a star forest consisting of the disjoint \(m\) copies of \(S_n\). It is known that \(mS_2\) is antimagic if and only if \(m=1\). In this study, a necessary condition and a sufficient condition are obtained whereby a star forest \(mS_2\cup S_{n_1}\cup S_{n_2}\cup\cdots\cup S_{n_k}\) (\(n_1,n_2,\dots,n_k\ge 3\)) may be antimagic. In addition, a necessary and sufficient condition is obtained whereby a star forest \(mS_2\cup S_n\) \((n\ge 3)\) may be antimagic. Moreover, a graph consisting of disjoint stars together with an extra disjoint path is also verified to be antimagic.Uncrossed chords of cycles in chordal graphs.https://www.zbmath.org/1452.051522021-02-12T15:23:00+00:00"McKee, Terry A."https://www.zbmath.org/authors/?q=ai:mckee.terry-aSummary: Strongly chordal graphs are characterized here as being the chordal graphs in which the uncrossed chords of a cycle always form a forest (an ``independent set of edges''). Ptolemaic graphs are characterized here as being the chordal graphs in which the uncrossed chords of a cycle always form a matching (a ``set of independent edges''). Additional characterizations of ptolemaic graphs involve the number of (un)crossed chords.A new probabilistic lower bound on the limited packing number of a graph.https://www.zbmath.org/1452.051852021-02-12T15:23:00+00:00"Mohammadi, Mehdi"https://www.zbmath.org/authors/?q=ai:mohammadi.mehdi"Rad, NaderJafari"https://www.zbmath.org/authors/?q=ai:jafari-rad.nader"Maghasedi, Mohammad"https://www.zbmath.org/authors/?q=ai:maghasedi.mohammadSummary: A set of vertices \(B\subseteq V(G)\) is called a \(k\)-limited packing set in \(G\) if \(|N[v]\cap B|\le k\) for all \(u\in V(G)\), where \(k\ge 1\). The \(k\)-limited packing number, \(L_k(G)\), is the largest number of vertices in a \(k\)-limited packing set. In this paper we present a new probabilistic lower bound for the \(k\)-limited packing number of a graph and improve previous lower bound given in \textit{A. Gagarin} and \textit{V. Zverovich} [Discrete Appl. Math. 184, 146--153 (2015; Zbl 1310.05171)].On majority total domination in graphs.https://www.zbmath.org/1452.051242021-02-12T15:23:00+00:00"Muthuselvi, A."https://www.zbmath.org/authors/?q=ai:muthuselvi.a"Arumugam, S."https://www.zbmath.org/authors/?q=ai:arumugam.senthil-m|arumugam.subramanian|arumugam.sivabalanSummary: A majority total dominating function of a graph \(G=(V,E)\) is a function \(g:V\to\{-1,1\}\) such that \(g(N(v))\ge 1\) for at least half of the vertices \(v\in V\), where \(N(v)\) is the open neighborhood of \(v\) and \(g(N(v))=\sum_{u\in N(v)}g(u)\). The weight of \(g\) is defined by \(g(V)=\sum_{u\in V}g(u)\). The minimum weight of a majority total dominating function of \(G\) is called the majority total domination number of \(G\) and is denoted by \(\gamma^t_{\mathrm{maj}}(G)\). In this paper we determine \(\gamma^t_{\mathrm{maj}}\) for several classes of graphs. We also present bounds for \(\gamma^t_{\mathrm{maj}}(G)\) and investigate extremal graphs which attain the bounds.On majority total domination in graphs.https://www.zbmath.org/1452.051232021-02-12T15:23:00+00:00"Muthuselvi, A."https://www.zbmath.org/authors/?q=ai:muthuselvi.a"Arumugam, S."https://www.zbmath.org/authors/?q=ai:arumugam.subramanian|arumugam.sivabalan|arumugam.senthil-mSummary: A majority total dominating function of a graph \(G=(V,E)\) is a function \(g:V\to\{-1,1\}\) such that \(g(N(v))\ge 1\) for at least half of the vertices \(v\in V\), where \(N(v)\) is the open neighborhood of \(v\) and \(g(N(v))=\sum_{u\in N(v)}g(u)\). The weight of \(g\) is defined by \(g(V)=\sum_{u\in V}g(u)\). The minimum weight of a majority total dominating function of \(G\) is called the majority total domination number of \(G\) and is denoted by \(\gamma^t_{\mathrm{maj}}(G)\). In this paper we determine \(\gamma^t_{\mathrm{maj}}\) for several classes of graphs. We also present bounds for \(\gamma^t_{\mathrm{maj}}(G)\) and investigate extremal graphs which attain the bounds.New perspectives on neighborhood-prime labelings of graphs.https://www.zbmath.org/1452.051572021-02-12T15:23:00+00:00"Asplund, John"https://www.zbmath.org/authors/?q=ai:asplund.john"Fox, N. Bradley"https://www.zbmath.org/authors/?q=ai:fox.n-bradley"Hamm, Arran"https://www.zbmath.org/authors/?q=ai:hamm.arranSummary: Neighborhood-prime labeling is a variation of prime labeling. A labeling \(f:V(G)\to[|V(G)|]\) is a neighborhood-prime labeling if for each vertex \(v\in V(G)\) with degree greater than 1, the greatest common divisor of the set of labels in the neighborhood of \(v\) is 1. In this paper, we introduce techniques for finding neighborhood-prime labelings based on the Hamiltonicity of the graph, by using conditions on possible degrees of vertices, and by examining a neighborhood graph. In particular, classes of graphs shown to be neighborhood-prime include all generalized Petersen graphs, grid graphs of any size, and lobsters given restrictions on the degree of the vertices. In addition, we show that almost all graphs and almost all regular graphs are neighborhood-prime, and we find all graphs of order 10 or less that have a neighborhood-prime labeling. We give several conjectures for future work in this area.A sufficient condition for fractional ID-\([a,b]\)-factor-critical covered graphs.https://www.zbmath.org/1452.051392021-02-12T15:23:00+00:00"Jiang, Jiashang"https://www.zbmath.org/authors/?q=ai:jiang.jiashangSummary: A graph \(G\) is fractional ID-\([a,b]\)-factor-critical covered if for any independent set \(I\) of \(G\), \(G-I\) is fractional \([a,b]\)-covered. In this article, we present a neighborhood union condition for a graph to be fractional ID-\([a,b]\)-factor-critical covered, and show this result is best possible in some sense.On sequences of molecular descriptors related to some counting polynomials of a benzenoid graph.https://www.zbmath.org/1452.051822021-02-12T15:23:00+00:00"Nadeem, Muhammad"https://www.zbmath.org/authors/?q=ai:nadeem.muhammad|nadeem.muhammad-faisal"Yousaf, Awais"https://www.zbmath.org/authors/?q=ai:yousaf.awais"Razaq, Abdul"https://www.zbmath.org/authors/?q=ai:razaq.abdulSummary: Opposite edges in a connecting graph which lies in the same face eventually form a strip of adjacent faces and plays a major rule in the construction of counting polynomials. Polynomials are the sequel description of topological properties in such a way that the exponents represent the extent of its partitions while the coefficients are related to the occurrence of these partitions. Topological indices are used to model chemical properties of molecular graph. In this paper, we construct Omega, Sadhana, Theta and PI polynomials and, related sequences of degree based molecular descriptors of these polynomials. As a consequence of these generalized sequences; molecular descriptors for the graph \(\tau_{(\alpha, \beta,\gamma)}\) can be calculated without further calculation at any level.Decycling \(d\)-ary \(n\)-dimensional cubes.https://www.zbmath.org/1452.050882021-02-12T15:23:00+00:00"Gao, Liqing"https://www.zbmath.org/authors/?q=ai:gao.liqing"Wang, Jian"https://www.zbmath.org/authors/?q=ai:wang.jian.5Summary: The decycling number of a graph \(G\) is the minimum number of vertices whose removal from \(G\) results in an acyclic subgraph. The \(d\)-ary \(n\)-dimensional cubes are \(n\)-fold Cartesian product graphs of complete graph on \(d\) vertices. When \(d=2\), it reduces to the ordinary \(n\)-dimensional hypercubes. In this paper, we show that the decycling number \(f(d,n)\) of the \(d\)-ary \(n\)-dimensional cubes \(Q_n(d)\) can be bounded as follows: \[(d-1)^2d^{n-2}\le f(d,n)\le\left(d-1-\frac{d-1}{M}\right)d^{n-1},\] where \(M=(d-1)(2nd-3d+2)+1\).Isolated toughness and \(P_{\ge 3}\)-factors in graphs.https://www.zbmath.org/1452.051442021-02-12T15:23:00+00:00"Zhou, Sizhong"https://www.zbmath.org/authors/?q=ai:zhou.sizhong"Sun, Zhiren"https://www.zbmath.org/authors/?q=ai:sun.zhirenSummary: Let \(m\), \(n\), \(k\) be three positive integers. A path factor with each component having at least \(n\) vertices is called a \(P_{\ge n}\)-factor. A graph \(G\) is defined as a \(P_{\ge n}\), \(m\)-factor deleted graph if \(G-E^\prime\) has a \(P_{\ge n}\)-factor for every \(E^\prime\subseteq E(G)\) with \(|E^\prime|=m\). A graph \(G\) is defined as a \((P_{\ge n},k)\)-factor critical graph if \(G-U\) admits a \(P_{\ge n}\)-factor for every \(U\subseteq V(G)\) with \(|U|=k\). In this paper, we verify the following two results: (1) A graph \(G\) with \(\kappa(G)\ge\frac{2m+1}{2}\) is a \((P_{\ge 3},m)\)-factor deleted graph if \(I(G)>\frac{5m+5}{2m+4}\); (2) A graph \(G\) with \(\kappa(G) \ge k+2\) is a \((P_{\ge 3},k)\)-factor critical graph if \(I(G)>\frac{k+7} {4}\). Furthermore, some conditions in main results are sharp.Computing the eccentric connectivity index and eccentric adjacency index of conjugated trees.https://www.zbmath.org/1452.050962021-02-12T15:23:00+00:00"Akhter, Shehnaz"https://www.zbmath.org/authors/?q=ai:akhter.shehnaz"Farooq, Rashid"https://www.zbmath.org/authors/?q=ai:farooq.rashidSummary: Let \(G\) be a connected graph with \(n\) vertices and \(m\) edges. The eccentricity of a vertex \(u\in V(G)\), denoted by \(e_G(u)\), is the maximum distance between \(u\) and any other vertex of \(G\). The degree of a vertex \(u\in V(G)\), denoted by \(d_G(u)\), is the number of incident edges to \(u\). The eccentric connectivity index of \(G\) is defined as \(\xi^c(G)=\sum_{u\in V(G)}d_G(u)e_G(u)\) and the eccentric adjacency index is defined as \(\xi^{ad}(G)=\sum_{u\in V(G)}\frac{S_G(u)} {e_G(u)}\), where \(S_G(u)\) is the sum of degrees of neighbors of the vertex \(u\) in \(G\). In this paper, we determine the smallest and largest eccentric connectivity index of conjugated trees. Also, we find the extremal conjugated trees with respect to the eccentric adjacency index.Some extremal graphs with respect to the zeroth-order general Randić index.https://www.zbmath.org/1452.050922021-02-12T15:23:00+00:00"Su, Guifu"https://www.zbmath.org/authors/?q=ai:su.guifu"Yan, Jingru"https://www.zbmath.org/authors/?q=ai:yan.jingru"Chen, Zhibing"https://www.zbmath.org/authors/?q=ai:chen.zhibing"Rao, Gang"https://www.zbmath.org/authors/?q=ai:rao.gangSummary: For a given graph set \(\mathcal{G}_n\), it is important to find the upper and lower bounds for some graph invariant in \(\mathcal{G}_n\) and characterize the graphs in which the maximal and minimal values are attained, respectively. In this paper, we investigated several upper and lower bounds on the general zeroth-order Randić index of graphs in terms of number of cut edges, independence number and matching number, respectively. The extremal graphs are also completely characterized.Topics in Gallai-Ramsey theory.https://www.zbmath.org/1452.050012021-02-12T15:23:00+00:00"Magnant, Colton"https://www.zbmath.org/authors/?q=ai:magnant.colton"Salehi Nowbandegani, Pouria"https://www.zbmath.org/authors/?q=ai:salehi-nowbandegani.pouriaThis book is an excellent and much sought after material addressing Gallai-Ramsey theory. The contents are quite absorbing and possess the magic band of enticing the focused readers and stimulates them to crave for more.
In Chapter 1, the authors give a very crisp introduction to the topic with adequate explanation to terms and terminologies concerning graphs, coloring and Gallai-Ramsey numbers. For the authors, a graph is a finite simple graph. They put an end card to this chapter with a nice proof of a result on the Gallai-Ramsey number $\operatorname{gr}_k(K_3. P_3)$ for $k \geq1$.
They begin the Chapter 2 with the definition of a Gallai coloring of a complete graph $G$ and prove an interesting lemma viz., ``Every Gallai coloring of a complete graph using at least 3 colors has a color that spans a disconnected graph.'' They introduce rainbow paths, rainbow triangles with a pendant edge and prove a remarkable result: ``There exist no two rainbow triangles sharing most two colors.'' They conclude this chapter with a few more deep theorems related to rainbow graphs.
Chapter 3 is the main fulcrum of the book comprising deep results, illustrations and mind boggling proofs on Gallai-Ramsey numbers for rainbow triangles. It begins with a lower bound for all Gallai-Ramsey numbers when the intended monochromatic graph is bipartite and it continues with an elaborate discussion on sharp results for bipartite and non bipartite graphs with several lemmas, facts and deep proofs. The authors then carry the computation of the Gallai-Ramsey number for complete graphs and other specific graphs such as even cycles, paths, complete bipartite graphs and book graphs.
In Chapter 4, they establish that the computation of the Gallai-Ramsey number $\operatorname{gr}_k(S_3^+ , H)$ is exponential in $k$, if $H$ is non-bipartite or linear if $H$ is bipartite, where $H$ is a fixed graph without isolated vertices and $S_3^+$ is a star graph on 4 vertices with the addition of an extra edge between two of its vertices of degree 1. Again we find here a few more deep results at very advanced level of intensive research.
They conclude this wonderful treasure of Gallai-Ramsey number computation for finite simple graphs with a table of known sharp results and open problems in the form of conjectures. To sum up, this book is meant for very serious researchers in this topic.
Reviewer: V. Yegnanarayanan (Chennai)Total irregularity strength of disjoint union of crossed prism and necklace graphs.https://www.zbmath.org/1452.051612021-02-12T15:23:00+00:00"Jeyanthi, P."https://www.zbmath.org/authors/?q=ai:jeyanthi.pon"Sudha, A."https://www.zbmath.org/authors/?q=ai:sudha.aSummary: A totally irregular total \(k\)-labeling \(f:V\cup E\to\{1,2,3,\dots,k\}\) is a labeling of vertices and edges of \(G\) in such a way that for any two different vertices \(x\) and \(y\) their vertex-weights \(wt_f(x)\ne wt_f(y)\) where the vertex-weight \(wt_f(x)=f(x)+\sum_{xz\in E}f(xz)\) and also for every two different edges \(xy\) and \(x^\prime y^\prime\) of \(G\) their edge-weights \(wt_f(xy)=f(x)+f(xy)+f(y)\) and \(wt_f(x^\prime y^\prime)=f(x^\prime)+f(x^\prime y^\prime)+f(y^\prime)\) are distinct. A total irregularity strength of graph \(G\), denoted by \(ts(G)\) is defined as the minimum \(k\) for which a graph \(G\) has a totally irregular total \(k\)-labeling. In this paper, we investigate the total irregularity strength of the crossed prism, \(m\) copies of crossed prism, necklace and \(m\) copies of necklace.On the spectral radius of bipartite graphs.https://www.zbmath.org/1452.051032021-02-12T15:23:00+00:00"Fan, Dandan"https://www.zbmath.org/authors/?q=ai:fan.dandan"Wang, Guoping"https://www.zbmath.org/authors/?q=ai:wang.guoping"Zao, Yuying"https://www.zbmath.org/authors/?q=ai:zao.yuyingSummary: The adjacency matrix \(A(G)\) of a graph \(G\) is the \(n\times n\) matrix with its \((i,j)\)-entry equal to 1 if \(v_i\) and \(v_j\) are adjacent, and 0 otherwise. The spectral radius of \(G\) is the largest eigenvalue of \(A(G)\). In this paper we determine the graph with maximum spectral radius among all connected bipartite graphs of order \(n\) with a given matching number and a given vertex connectivity, respectively.