Recent zbMATH articles in MSC 05C75 https://zbmath.org/atom/cc/05C75 2022-06-24T15:10:38.853281Z Werkzeug Extremal results for directed tree connectivity https://zbmath.org/1485.05028 2022-06-24T15:10:38.853281Z "Sun, Yuefang" https://zbmath.org/authors/?q=ai:sun.yuefang|sun.yuefang.1 Summary: For a digraph $$D=(V(D)$$, $$A(D))$$, and a set $$S\subseteq V(D)$$ with $$r\in S$$ and $$|S|\ge 2$$, an $$(S, r)$$-tree is an out-tree $$T$$ rooted at $$r$$ with $$S\subseteq V(T)$$. Two $$(S, r)$$-trees $$T_1$$ and $$T_2$$ are said to be arc-disjoint if $$A(T_1)\cap A(T_2)=\emptyset$$. Two arc-disjoint $$(S, r)$$-trees $$T_1$$ and $$T_2$$ are said to be internally disjoint if $$V(T_1)\cap V(T_2)=S$$. Let $$\kappa_{S,r}(D)$$ and $$\lambda_{S,r}(D)$$ be the maximum number of internally disjoint and arc-disjoint $$(S, r)$$-trees in $$D$$, respectively. The generalized $$k$$-vertex-strong connectivity of $$D$$ is defined as $\kappa_k(D)= \min \{\kappa_{S,r}(D)\mid S\subseteq V(D), \, |S|=k, r\in S\}.$ Similarly, the generalized $$k$$-arc-strong connectivity of $$D$$ is defined as $\lambda_k(D)= \min \{\lambda_{S,r}(D)\mid S\subseteq V(D), \, |S|=k, r\in S\}.$ The generalized $$k$$-vertex-strong connectivity and generalized $$k$$-arc-strong connectivity are also called directed tree connectivity which could be seen as a generalization of classical connectivity of digraphs and a natural extension of undirected tree connectivity. A digraph $$D=(V(D)$$, $$A(D))$$ is called minimally generalized $$(k, \ell)$$-vertex (respectively, arc)-strongly connected if $$\kappa_k(D)\ge \ell$$ (respectively, $$\lambda_k(D)\ge \ell)$$ but for any arc $$e\in A(D)$$, $$\kappa_k(D-e)\le \ell -1$$ (respectively, $$\lambda_k(D-e)\le \ell -1)$$. In this paper, we study the minimally generalized $$(k, \ell)$$-vertex (respectively, arc)-strongly connected digraphs. We compute the minimum and maximum sizes of these digraphs and give characterizations of such digraphs for some pairs of $$k$$ and $$\ell$$. Relation between the inertia indices of a complex unit gain graph and those of its underlying graph https://zbmath.org/1485.05034 2022-06-24T15:10:38.853281Z "Zaman, Shahid" https://zbmath.org/authors/?q=ai:zaman.shahid "He, Xiaocong" https://zbmath.org/authors/?q=ai:he.xiaocong Summary: A $$\mathbb T$$-gain graph is a triple $$\Phi = (G, \mathbb T, \varphi)$$ consisting of an underlying graph $$G = (V(G),E(G))$$, the circle group $$\mathbb T = \{ z \in \mathbb C : |z| = 1 \}$$ and a gain function $$\varphi : \vec{E} \to \mathbb T$$, such that $$\varphi(e_{ij}) = \varphi(e_{ij})^{-1} = \overline{\varphi(e_{ij})}$$. In this paper, we focus our attention on the relations between the inertia indices of $$\mathbb T$$-gain graph $$\Phi$$ and the inertia indices of its underlying graph $$G$$. We obtain sharp lower and upper bounds on $$p(\Phi)$$ (resp., $$n(\Phi))$$ in terms of $$p(G)$$ (resp., $$n(G))$$ and characterize those corresponding extremal $$\mathbb T$$-gain graphs, respectively. As a corollary, we also characterize those signed graphs whose inertia indices obtaining the sharp bounds, respectively. Describing minor 5-stars in 3-polytopes with minimum degree 5 and no vertices of degree 6 or 7 https://zbmath.org/1485.05036 2022-06-24T15:10:38.853281Z "Batueva, Ts. Ch-D." https://zbmath.org/authors/?q=ai:batueva.tsyndyma-chemit-dorzhievna "Borodin, O. V." https://zbmath.org/authors/?q=ai:borodin.oleg-veniaminovich "Ivanova, A. O." https://zbmath.org/authors/?q=ai:ivanova.anna-olegovna "Nikiforov, D. V." https://zbmath.org/authors/?q=ai:nikiforov.dmitrii-vladislavovich Summary: In 1940, in attempts to solve the Four Color Problem, \textit{H. Lebesgue} [J. Math. Pures Appl. (9) 19, 27--43 (1940; Zbl 0024.28701)] gave an approximate description of the neighborhoods of 5-vertices in the class $$\mathcal{P}_5$$ of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. $(6,6,7,7,7), (6,6,6,7,9), (6,6,6,6,11)$ $(5,6,7,7,8), (5,6,6,7,12), (5,6,6,8,10), (5,6,6,6,17)$ $(5,5,7,7,13),(5,5,7,8,10),(5,5,6,7,27)$ $(5,5,6,6,\infty),(5,5,6,8,15),(5,5,6,9,11)$ $(5,5,5,7,41),(5,5,5,8,23),(5,5,5,9,17)$ $(5,5,5,10,14),(5,5,5,11,13).$ Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in $$\mathcal{P}_5$$. \textit{O. V. Borodin} et al. [Discuss. Math., Graph Theory 38, No. 3, 615--625 (2018; Zbl 1391.05101)] proved that every forbidding vertices of degree from 7 to 11 results in a tight description $$(5, 5, 6, 6, \infty )$$, $$(5, 6, 6, 6, 15)$$, $$(6, 6, 6, 6, 6)$$. Recently, \textit{O. V. Borodin} et al. [Discrete Math. 342, No. 8, 2439--2444 (2019; Zbl 1418.05057] proved every 3-polytope in $$\mathcal{P}_5$$ with no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences $$(5, 5, 5, 5, \infty )$$ and $$(5, 5, 10, 5, 12)$$, which is tight and improves a corresponding description $$(5, 5, 5, 5, \infty )$$, $$(5, 5, 9, 5, 17)$$, $$(5, 5, 10, 5, 14)$$, $$(5, 5, 11, 5, 13)$$ that follows from the Lebesgue theorem. The purpose of this paper is to prove that every 3-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a 5-vertex whose neighborhood is majorized by one of the ordered sequences $$(5, 5, 5, 5, \infty )$$, $$(5, 5, 8, 5, 14)$$, or $$(5, 5, 10, 5, 12)$$. Minimum algebraic connectivity of graphs whose complements are bicyclic with two cycles https://zbmath.org/1485.05090 2022-06-24T15:10:38.853281Z "Javaid, M." https://zbmath.org/authors/?q=ai:javaid.muhammad "Raza, M." https://zbmath.org/authors/?q=ai:raza.muhammad-taskeen|raza.mian-f|raza.muhammad-hassan|raza.mohsin|raza.mohammad|raza.michelle-n|raza.muhammad-ali|raza.muhammad-summair|raza.mahdi-saber|raza.mohd-arif|raza.mohsan|raza.malik-ali|raza.mohamed "Rehman, Masood Ur" https://zbmath.org/authors/?q=ai:rehman.masood-ur "Teh, W. C." https://zbmath.org/authors/?q=ai:teh.wen-chean "Cao, J." https://zbmath.org/authors/?q=ai:cao.jinde Given a graph $$\Gamma$$ with $$n$$ vertices and $$m$$ edges, the Laplacian matrix is $$L = D - A$$, where $$D$$ is the diagonal matrix of degrees, and $$A$$ is the adjacency matrix. The second smallest eigenvalue is called the algebraic connectivity, and denoted $$a$$. This paper investigates the algebraic connectivity for some special classes of graphs. In particular, a connected graph is called unicyclic if $$m = n$$; bicyclic if $$m = n + 1$$; and tricyclic if $$m = n + 2$$, and so forth. Note that a bicyclic graph can have more than two cycles, and a tricyclic graph can have more than three cycles, etc. By making use of the eigenvector associated with $$a$$, the extremal graphs with the minimum algebraic connectivity whose complements are bicyclic graphs with exactly two cycles are characterized. There are some significant typos in the paper. For example, the formula $$m = m - 1 + k$$ in Section 2 should read $$m = n - 1 + k$$. Reviewer: William Kocay (Howden) A condition on Hamilton-connected line graphs https://zbmath.org/1485.05096 2022-06-24T15:10:38.853281Z "Lei, Lan" https://zbmath.org/authors/?q=ai:lei.lan "Wei, Jia" https://zbmath.org/authors/?q=ai:wei.jia "Xie, Yikang" https://zbmath.org/authors/?q=ai:xie.yikang "Zhan, Mingquan" https://zbmath.org/authors/?q=ai:zhan.mingquan "Lai, Hong-Jian" https://zbmath.org/authors/?q=ai:lai.hong-jian Summary: A graph $$G$$ is Hamilton-connected if for any pair of distinct vertices $$u, v \in V(G), G$$ has a spanning $$(u, v)$$-path; $$G$$ is 1-hamiltonian if for any vertex subset $$S \subseteq{V(G)}$$ with $$|S| \le 1$$, $$G - S$$ has a spanning cycle. Let $$\delta (G)$$, $$\alpha^\prime(G)$$ and $$L(G)$$ denote the minimum degree, the matching number and the line graph of a graph $$G$$, respectively. The following result is obtained. Let $$G$$ be a simple graph with $$|E(G)| \ge 3$$. If $$\delta (G) \ge \alpha^\prime(G)$$, then each of the following holds. (i) $$L(G)$$ is Hamilton-connected if and only if $$\kappa (L(G))\ge 3$$. (ii) $$L(G)$$ is 1-hamiltonian if and only if $$\kappa (L(G))\ge 3$$. Some algebraic properties of Sierpiński-type graphs https://zbmath.org/1485.05101 2022-06-24T15:10:38.853281Z "Ghouchan, Mohammad Farrokhi Derakhshandeh" https://zbmath.org/authors/?q=ai:ghouchan.mohammad-farrokhi-derakhshandeh "Ghorbani, Ebrahim" https://zbmath.org/authors/?q=ai:ghorbani.ebrahim "Maimani, Hamid Reza" https://zbmath.org/authors/?q=ai:maimani.hamid-reza "Mahid, Farhad Rahimi" https://zbmath.org/authors/?q=ai:rahimi-mahid.farhad Summary: This paper deals with some of the algebraic properties of Sierpiński graphs and a family of regular generalized Sierpiński graphs. For the family of regular generalized Sierpiński graphs, we obtain their spectrum and characterize those graphs that are Cayley graphs. As a by-product, a new family of non-Cayley vertex-transitive graphs, and consequently, a new set of non-Cayley numbers are introduced. We also obtain the Laplacian spectrum of Sierpiński graphs in some particular cases, and make a conjecture on the general case. Meyniel extremal families of abelian Cayley graphs https://zbmath.org/1485.05115 2022-06-24T15:10:38.853281Z "Hasiri, Fatemeh" https://zbmath.org/authors/?q=ai:hasiri.fatemeh "Shinkar, Igor" https://zbmath.org/authors/?q=ai:shinkar.igor Summary: We study the game of Cops and Robbers, where cops try to capture a robber on the vertices of a graph. Meyniel's conjecture states that for every connected graph $$G$$ on $$n$$ vertices, the cop number of $$G$$ is upper bounded by $$O(\sqrt{n})$$. That is, for every graph $$G$$ on $$n$$ vertices $$O(\sqrt{n})$$ cops suffice to catch the robber. We present several families of abelian Cayley graphs that are Meyniel extremal, i.e., graphs whose cop number is $$O(\sqrt{n})$$. This proves that the $$O(\sqrt{n})$$ upper bound for Cayley graphs proved by \textit{P. Bradshaw} [Discrete Math. 343, No. 1, Article ID 111546, 5 p. (2020; Zbl 1429.05088)] is tight. In particular, this shows that Meyniel's conjecture, if true, is tight even for abelian Cayley graphs. In order to prove the result, we construct Cayley graphs on $$n$$ vertices with $$\Omega (\sqrt{n})$$ generators that are $$K_{2,3}$$-free. This shows that the Kövári, Sós, and Turán theorem [\textit{T. Kövári} et al., Colloq. Math. 3, 50--57 (1954; Zbl 0055.00704)], stating that any $$K_{2,3}$$-free graph of $$n$$ vertices has at most $$O(n^{3/2})$$ edges, is tight up to a multiplicative constant even for abelian Cayley graphs. Rainbow independent sets on dense graph classes https://zbmath.org/1485.05140 2022-06-24T15:10:38.853281Z "Kim, Jinha" https://zbmath.org/authors/?q=ai:kim.jinha "Kim, Minki" https://zbmath.org/authors/?q=ai:kim.minki "Kwon, O-joung" https://zbmath.org/authors/?q=ai:kwon.ojoung Summary: Given a family $$\mathcal{I}$$ of independent sets in a graph, a rainbow independent set is an independent set $$I$$ such that there is an injection $$\phi : I \to \mathcal{I}$$ where for each $$v \in I$$, $$v$$ is contained in $$\phi (v)$$. \textit{R. Aharoni} et al. [Eur. J. Comb. 79, 222--227 (2019; Zbl 1414.05235)] determined for various graph classes $$\mathcal{C}$$ whether $$\mathcal{C}$$ satisfies a property that for every $$n$$, there exists $$N = N (\mathcal{C}, n)$$ such that every family of $$N$$ independent sets of size $$n$$ in a graph in $$\mathcal{C}$$ contains a rainbow independent set of size $$n$$. In this paper, we add two dense graph classes satisfying this property, namely, the class of graphs of bounded neighborhood diversity and the class of $$r$$-powers of graphs in a bounded expansion class. The micro-world of cographs https://zbmath.org/1485.05154 2022-06-24T15:10:38.853281Z "Alecu, Bogdan" https://zbmath.org/authors/?q=ai:alecu.bogdan "Lozin, Vadim" https://zbmath.org/authors/?q=ai:lozin.vadim-v "de Werra, Dominique" https://zbmath.org/authors/?q=ai:de-werra.dominique Summary: Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of cographs and create a hierarchy of graph parameters grounded on these milestones. Note on structural properties of graphs https://zbmath.org/1485.05155 2022-06-24T15:10:38.853281Z "Arreola-Bautista, Luis D." https://zbmath.org/authors/?q=ai:arreola-bautista.luis-d "Reyna, Gerardo" https://zbmath.org/authors/?q=ai:reyna.gerardo "Romero-Valencia, Jesús" https://zbmath.org/authors/?q=ai:romero-valencia.jesus "Sigarreta, José M." https://zbmath.org/authors/?q=ai:sigarreta-almira.jose-maria (no abstract) Cyclability in graph classes https://zbmath.org/1485.05156 2022-06-24T15:10:38.853281Z "Crespelle, Christophe" https://zbmath.org/authors/?q=ai:crespelle.christophe "Golovach, Petr A." https://zbmath.org/authors/?q=ai:golovach.petr-a Summary: A subset $$T\subseteq V(G)$$ of vertices of a graph $$G$$ is said to be cyclable if $$G$$ has a cycle $$C$$ containing every vertex of $$T$$, and for a positive integer $$k$$, a graph $$G$$ is $$k$$-cyclable if every set of vertices of size at most $$k$$ is cyclable. The Terminal Cyclability problem asks, given a graph $$G$$ and a set $$T$$ of vertices, whether $$T$$ is cyclable, and the $$k$$-Cyclability problem asks, given a graph $$G$$ and a positive integer $$k$$, whether $$G$$ is $$k$$-cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is a cycle, or output a graph separator that certifies a no-answer. We use these results to show that $$k$$-Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes. On split $$B_1$$-EPG graphs https://zbmath.org/1485.05157 2022-06-24T15:10:38.853281Z "Deniz, Zakir" https://zbmath.org/authors/?q=ai:deniz.zakir "Nivelle, Simon" https://zbmath.org/authors/?q=ai:nivelle.simon "Ries, Bernard" https://zbmath.org/authors/?q=ai:ries.bernard "Schindl, David" https://zbmath.org/authors/?q=ai:schindl.david Summary: In this paper, we are interested in edge intersection graphs of paths in a grid, such that each such path has at most one bend. These graphs were introduced in [\textit{M. C. Golumbic} et al., Networks 54, No. 3, 130--138 (2009; Zbl 1208.05090)] and they are called $$B_1$$-EPG graphs. In particular, we focus on split graphs and characterise those that are $$B_1$$-EPG. This characterisation allows us to disprove a conjecture of \textit{K. Cameron} et al. [Discrete Appl. Math. 210, 185--194 (2016; Zbl 1339.05381)]. The existence of polynomial-time recognition algorithm for this graph class is still unknown. We furthermore investigate inclusion relationships among subclasses of split graphs that are $$B_1$$-EPG. For the entire collection see [Zbl 1428.68007]. Unitary Cayley graphs whose Roman domination numbers are at most four https://zbmath.org/1485.13019 2022-06-24T15:10:38.853281Z "Chin, A. Y. M." https://zbmath.org/authors/?q=ai:chin.angelina-yan-mui "Maimani, H. R." https://zbmath.org/authors/?q=ai:maimani.hamid-reza "Pournaki, M. R." https://zbmath.org/authors/?q=ai:pournaki.mohammad-reza "Sivagami, M." https://zbmath.org/authors/?q=ai:sivagami.m "Tamizh Chelvam, T." https://zbmath.org/authors/?q=ai:tamizh-chelvam.thirugnanam Summary: Let $$R$$ be a finite commutative ring with nonzero identity. The unitary Cayley graph of $$R$$ is the graph obtained by letting all the elements of $$R$$ to be the vertices and defining distinct vertices $$x$$ and $$y$$ to be adjacent if and only if $$x - y$$ is a unit element of $$R$$. In this paper, we characterize all unitary Cayley graphs with Roman domination number at most four.