Search

We investigate a special case of hereditary property in graphs, referred to as {\em robustness}. A property (or structure) is called robust in a graph $G$ if it is inherited by all the connected spanning subgraphs of $G$. We motivate this definition using two different settings of dynamic networks. The first corresponds to networks of low dynamicity, where some links may be permanently removed so long as the network remains connected. The second corresponds to highly-dynamic networks, where communication links appear and disappear arbitrarily often, subject only to the requirement that the entities are temporally connected in a recurrent fashion ({\it i.e.} they can always reach each other through temporal paths). Each context induces a different interpretation of the notion of robustness. We start by motivating the definition and discussing the two interpretations, after what we consider the notion independently from its interpretation, taking as our focus the robustness of {\em maximal independent sets} (MIS). A graph may or may not admit a robust MIS. We characterize the set of graphs \forallMIS in which {\em all} MISs are robust. Then, we turn our attention to the graphs that {\em admit} a robust MIS (\existsMIS). This class has a more complex structure; we give a partial characterization in terms of elementary graph properties, then a complete characterization by means of a (polynomial time) decision algorithm that accepts if and only if a robust MIS exists. This algorithm can be adapted to construct such a solution if one exists.

Let k be a positive integer and let G be a graph with vertex set V(G). A subset D subset of V(G) is a k-dominating set if every vertex outside D is adjacent to at least k vertices in D. the k-domination number gamma(k)(G) is the minimum cardinality of a k-dominating set in G. For any graph G, we know that gamma(k)(G) >= gamma(G) + k - 2 where Delta(G) >= k >= 2 and this bound is sharp for every k >= 2. in this paper, we characterize bipartite graphs satisfying the equality for k >= 3 and present a necessary and sufficient condition for a bipartite graph to satisfy the equality hereditarily when k = 3. We also prove that the problem of deciding whether a graph satisfies the given equality is NP-hard in general., TUBITAK under the grant BIDEB 2221Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [1059B211800686]; Slovenian Research AgencySlovenian Research Agency - Slovenia [N1-0108], This research was started when Csilla Bujtas visited the Ege University in Izmir, Turkey; the authors thank the financial support of TUBITAK under the grant BIDEB 2221 (1059B211800686). Csilla Bujtas also acknowledges the financial support from the Slovenian Research Agency under the project N1-0108.

The Vapnik–Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least $$e^{(\log n)^{1 - o(1)}}$$ . The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, $$e^{c\sqrt{\log n}}$$ , due to Erdős and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdős–Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $$e^{\Omega (\log n)}$$ . Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovasz–Szegedy and Alon–Fischer–Newman, which is called the “ultra-strong regularity lemma” for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be $$(1/\varepsilon )^{O(d)}$$ , improving the original bound of $$(1/\varepsilon )^{O(d^2)}$$ in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an $$O(n^k)$$ -time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey–Turan numbers for graphs with bounded VC-dimension.

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

In breakthrough results, Saxton-Thomason and Balogh-Morris-Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simp ...

In general the stability of normed algebras is a non hereditary property. We shall prove that second conjugate Banach algebras may be non stable even if the underlying Banach algebra is stable. We shall characterize stability of second conjugate Banach algebras. Finally, we shall study kinds of stability induced on an algebra with an stable second conjugate algebra.

The paper studies the open-hereditary property of semi-separation axioms and applies it to the study of digital topological spaces such as an n-dimensional Khalimsky topological space, a Marcus-Wyse topological space and so on. More precisely, we study various properties of digital topological spaces related to low-level and semi-separation axioms such as T1/2 , semi-T1/2 , semi-T1, semi-T2, etc. Besides, using the finite or the infinite product property of the semi-Ti-separation axiom, i ? {1,2}, we prove that the n-dimensional Khalimsky topological space is a semi-T2-space. After showing that not every subspace of the digital topological spaces satisfies the semi-Ti-separation axiom, i ?{1,2}, we prove that the semi-Tiseparation property is open-hereditary, i ? {1,2}. All spaces in the paper are assumed to be nonempty and connected.

We study a hereditary starlikeness property for planar harmonic mappings on a disk and on an annulus. While such a property is a common trait of conformal mappings, it may be absent in harmonic mappings. It turns out that a sufficient condition for a harmonic mapping f to possess this hereditary property is to have a harmonic argument — a striking feature of conformal mappings that does not extend to all harmonic mappings.

We study various operator homological properties of the Fourier algebra $A(G)$ of a locally compact group $G$. Establishing the converse of two results of Ruan and Xu, we show that $A(G)$ is relatively operator 1-projective if and only if $G$ is IN, and that $A(G)$ is relatively operator 1-flat if and only if $G$ is inner amenable. We also exhibit the first known class of groups for which $A(G)$ is not relatively operator $C$-flat for any $C\geq1$. As applications of our techniques, we establish a hereditary property of inner amenability, answer an open question of Lau and Paterson, and answer an open question of Anantharaman--Delaroche on the equivalence of inner amenability and Property (W). In the bimodule setting, we show that relative operator 1-biflatness of $A(G)$ is equivalent to the existence of a contractive approximate indicator for the diagonal $G_\Delta$ in the Fourier--Stieltjes algebra $B(G\times G)$, thereby establishing the converse to a result of Aristov, Runde, and Spronk. We conjecture that relative $1$-biflatness of $A(G)$ is equivalent to the existence of a quasi-central bounded approximate identity in $L^1(G)$, that is, $G$ is QSIN, and verify the conjecture in many special cases. We finish with an application to the operator homology of $A_{cb}(G)$, giving examples of weakly amenable groups for which $A_{cb}(G)$ is not operator amenable., Comment: v3: final version, 22 pages

We define the \emph{occurrence graph} $G_p(\pi$) of a pattern $p$ in a permutation $\pi$ as the graph with the occurrences of $p$ in $\pi$ as vertices and edges between the vertices if the occurrences differ by exactly one element. We then study properties of these graphs. The main theorem in this paper is that every \emph{hereditary property} of graphs gives rise to a \emph{permutation class}., Comment: 19 pages, 15 figures

While topology given by a linear order has been extensively studied, this cannot be said about the case when the order is given only locally. The aim of this paper is to fill this gap. We consider relation between local orderability and separation axioms and give characterisation of those regularly locally ordered spaces which are connected, locally connected or Lindel¨of. We prove that local orderability is hereditary on open, connected or compact subsets. A collection of interesting examples is also offered.

We study limits of convergent sequences of string graphs, that is graphs with an intersection representation consisting of curves in the plane. We use these results to study the limiting behavior of a sequence of random string graphs. We also prove similar results for several related graph classes.

We introduce the notion of a hereditary property for rooted real trees and we also consider reduction of trees by a given hereditary property. Leaf-length erasure, also called trimming, is included as a special case of hereditary reduction. We only consider the metric structure of trees, and our framework is the space $\bT$ of pointed isometry classes of locally compact rooted real trees equipped with the Gromov-Hausdorff distance. Some of the main results of the paper are a general tightness criterion in $\bT$ and limit theorems for growing families of trees. We apply these results to Galton-Watson trees with exponentially distributed edge lengths. This class is preserved by hereditary reduction. Then we consider families of such Galton-Watson trees that are consistent under hereditary reduction and that we call growth processes. We prove that the associated families of offspring distributions are completely characterised by the branching mechanism of a continuous-state branching process. We also prove that such growth processes converge to Levy forests. As a by-product of this convergence, we obtain a characterisation of the laws of Levy forests in terms of leaf-length erasure and we obtain invariance principles for discrete Galton-Watson trees, including the super-critical cases., Comment: 44 pages

By considering ech fuzzy soft closure spaces , we provide a basic structure of a fuzzy soft topological space associated with ech fuzzy soft closure space . Separation axioms, namely,Tİ ( i = 1,2,3 ), semi- (respectively, pseudo and Uryshon) T2 are studied in both ech fuzzy soft closure spaces and its associative fuzzy soft topological spaces. It is shown that hereditary property is satisfied for Tİ i = 0,1 , with respect to ech fuzzy soft closure space but for other mentioned types of separations axioms, hereditary property satisfies for closed subspaces of ech fuzzy soft closure space. Several examples are given to illustrate each type of the separation axioms and to study the relationship between them.

В статье исследуются правовые особенности реализации права на принятие наследства в современный период. Определены юридические признаки, характерные для акта принятия наследства, исследованы и проанализированы различные доктринальные позиции по существу теоретических и практических аспектов реализации права на принятие наследства. Выявлены актуальные проблемы реализации права на принятие наследства в современный период, сформулированы конкретные предложения и рекомендации, направленные на развитие гражданского законодательства, регламентирующего особенности реализации права на принятие наследства., The article examines the legal features of implementation of the right to accept the inheritance in the modern period. Legal features characteristic of the act of accepting inheritance are defined, various doctrinal positions on the essence of theoretical and practical aspects of implementation of the right to inheritance are examined and analyzed. The actual problems of implementation of the right to accept the inheritance in the modern period are revealed, concrete proposals and recommendations are formulated aimed at development of the civil legislation regulating the features of implementation of the right to inheritance., №2(43) (2018)

We study failure rate monotonicity and generalised convex transform stochastic ordering properties of random variables, with an emphasis on applications. We are especially interested in the effect of a tail-weight iteration procedure to define distributions, which is equivalent to the characterisation of moments of the residual lifetime at a given instant. For the monotonicity properties, we are mainly concerned with hereditary properties with respect to the iteration procedure providing counterexamples showing either that the hereditary property does not hold or that inverse implications are not true. For the stochastic ordering, we introduce a new criterion, based on the analysis of the sign variation of a suitable function. This criterion is then applied to prove ageing properties of parallel systems formed with components that have exponentially distributed lifetimes.

For a set of graphs ? , the Stable- ? problem asks whether, given a graph G , we can find an independent set S in G , such that G - S ? ? . For instance, if ? is the set of all bipartite graphs, Stable- ? coincides with vertex 3-colourability, and if ? is the set of 1-regular graphs, the problem is known as efficient edge domination. Numerous other examples of the Stable- ? problem have been studied in the literature. In the present contribution, we systematically study the Stable- ? problem with respect to the speed (a term meaning size) of ? . In particular, we show that for all hereditary classes ? with a subfactorial speed of growth, Stable- ? is solvable in polynomial time. We then explore the problem for minimal hereditary factorial classes ? . Contrary to the conjecture proposed in Lozin (2005)? [18], the complexity of Stable- ? turns out to be polynomial for nearly all minimal hereditary factorial classes ? . On the other hand, if we do not require ? to be hereditary, the complexity of the problem can jump to NP-completeness.

This work further explores the applications of co-nondeterminism for showing kernelization lower bounds. The only known example prior to this work excludes polynomial kernelizations for the so-called Ramsey problem of finding an independent set or a clique of at least k vertices in a given graph [Kratsch 2012]. We study the more general problem of finding induced subgraphs on k vertices fulfilling some hereditary property Π, called Π-Induced Subgraph. The problem is NP-hard for all nontrivial choices of Π by a classic result of Lewis and Yannakakis [1980]. The parameterized complexity of this problem was classified by Khot and Raman [2002] depending on the choice of Π. The interesting cases for kernelization are for Π containing all independent sets and all cliques, since the problem is trivially polynomial time solvable or W[1]-hard otherwise. Our results are twofold. Regarding Π-Induced Subgraph, we show that for a large choice of natural graph properties Π, including chordal, perfect, cluster, and cograph, there is no polynomial kernel with respect to k . This is established by two theorems, each one capturing different (but not necessarily exclusive) sets of properties: one using a co-nondeterministic variant of OR-cross-composition and one by a polynomial parameter transformation from Ramsey. Additionally, we show how to use improvement versions of NP-hard problems as source problems for lower bounds, without requiring their NP-hardness. For example, for Π-Induced Subgraph our compositions may assume existing solutions of size k--1. This follows from the more general fact that source problems for OR-(cross-)compositions need only be NP-hard under co-nondeterministic reductions. We believe this to be useful for further lower-bound proofs, for example, since improvement versions simplify the construction of a disjunction (OR) of instances required in compositions. This adds a second way of using co-nondeterminism for lower bounds.

We study hereditary properties of convexity for planar harmonic homeomorphisms on a disk and an annulus. A noteworthy class of examples with the hereditary property arises fromenergy-minimal diffeomorphismsof an annulus, whoseex- istence was established in (9,11). An extension of a result by Hengartner and Schober (8) to an annulus is used to deduce the boundary behavior of a harmonic mapping from an annulus into a doubly-connected region bounded by two convex Jordan curves.

Korpelainen, Lozin, and Razgon conjectured that a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by only finitely many minimal forbidden induced subgraphs is labelled well-quasi-ordered, a notion stronger than that of n-well-quasi-order introduced by Pouzet in the 1970s. We present a counterexample to this conjecture. In fact, we exhibit a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by finitely many minimal forbidden induced subgraphs yet is not 2-well-quasi-ordered. This counterexample is based on the widdershins spiral, which has received some study in the area of permutation patterns.

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of $2$-dimensional matrices over a finite alphabet (where row and column order is not ignored) is strongly testable. The first result generalizes the result of Alon and Shapira [FOCS'05, SICOMP'08], who showed that any hereditary graph property (without vertex order) is strongly testable. The second result answers and generalizes a conjecture of Alon, Fischer and Newman [SICOMP'07] concerning testing of matrix properties. The testability is proved by establishing a removal lemma for vertex-ordered graphs. It states that for any finite or infinite family $\mathcal{F}$ of forbidden vertex-ordered graphs, and any $\epsilon > 0$, there exist $\delta > 0$ and $k$ so that any vertex-ordered graph which is $\epsilon$-far from being $\mathcal{F}$-free contains at least $\delta n^{|F|}$ copies of some $F\in\mathcal{F}$ (with the correct vertex order) where $|F|\leq k$. The proof bridges the gap between techniques related to the regularity lemma, used in the long chain of papers investigating graph testing, and string testing techniques. Along the way we develop a Ramsey-type lemma for $k$-partite graphs with "undesirable" edges, stating that one can find a Ramsey-type structure in such a graph, in which the density of the undesirable edges is not much higher than the density of those edges in the graph.

Multi-layer graphs consist of several graphs (layers) over the same vertex set. They are motivated by real-world problems where entities (vertices) are associated via multiple types of relationships (edges in different layers). We chart the border of computational (in)tractability for the class of subgraph detection problems on multi-layer graphs, including fundamental problems such as maximum matching, finding certain clique relaxations (motivated by community detection), or path problems. Mostly encountering hardness results, sometimes even for two or three layers, we can also spot some islands of tractability.

Sumační graf je graf G se zobrazením uzlové množiny na podmnožinu množiny přirozených čísel S takovým, že dva uzly jsou sousední, právě když suma jejich ohodnocení je prvkem S. V exkluzivním sumačním grafu ty prvky S, které jsou sumou dvou dalších prvků S, ohodnocují množinu izolovaných uzlů, asociovanou s grafem. Graf má exkluzivní sumační k-ohodnocení (zkráceně k-ESL), jestliže množina izolovaných uzlů má k prvků. V tomto článku využíváme skutečnosti, že vlastnost ‘mít k-ESL‘ je dědičná, a dáváme úplnou charakterizaci grafů, majících k-ESL, tím, že dáváme plný popis univerzálního grafu pro danou vlastnost. IA sum graph G is a graph with a mapping of the vertex set of G onto a set of positive integers S in such a way that two vertices of G are adjacent if and only if the sum of their labels is an element of S. In an exclusive sum graph the integers of S that are the sum of two other integers of S form a set of integers that label a collection of isolated vertices associated with the graph G. A graph bears a k-exclusive sum labelling (abbreviated k-ESL), if the set of isolated vertices is of cardinality k. In this paper, observing that the property of having a k-ESL is hereditary, we provide a characterisation of graphs that have a k-exclusive sum labelling, for any positive integer k, in terms of describing a universal graph for the property.

The edit distance function of a hereditary property $\mathscr{H}$ is the asymptotically largest edit distance between a graph of density $p\in[0,1]$ and $\mathscr{H}$. Denote by $P_n$ and $C_n$ the path graph of order $n$ and the cycle graph of order $n$, respectively. Let $C_{2n}^*$ be the cycle graph $C_{2n}$ with a diagonal, and $\widetilde{C_n}$ be the graph with vertex set $\{v_0, v_1, \ldots, v_{n-1}\}$ and $E(\widetilde{C_n})=E(C_n)\cup \{v_0v_2\}$. Marchant and Thomason determined the edit distance function of $C_6^{*}$. Peck studied the edit distance function of $C_n$, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of $C_8^{*}$, $\widetilde{C_n}$ and $P_n$, respectively., Comment: to appear in Discuss. Math. Graph Theory

A graph \(G=(V,E)\) is called equidominating if there exists a value Open image in new window and a weight function Open image in new window such that the total weight of a subset \(D\subseteq V\) is equal to t if and only if D is a minimal dominating set. To decide whether or not a given graph is equidominating is referred to as the Equidomination problem.

Let $\Lambda$ be a finite dimensional algebra and $G$ be a finite group whose elements act on $\Lambda$ as algebra automorphisms. Under the assumption that $\Lambda$ has a complete set $E$ of primitive orthogonal idempotents, closed under the action of a Sylow $p$-subgroup $S \leqslant G$. If the action of $S$ on $E$ is free, we show that the skew group algebra $\Lambda G$ and $\Lambda$ have the same finitistic dimension, and have the same strong global dimension if the fixed algebra $\Lambda^S$ is a direct summand of the $\Lambda^S$-bimodule $\Lambda$. Using a homological characterization of piecewise hereditary algebras proved by Happel and Zacharia, we deduce a criterion for $\Lambda G$ to be piecewise hereditary., Comment: A technical mistake was corrected

A k-colouring (not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given (hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree 4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) ⩽ 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.

Monotone normality is usually defined in the class of T 1 spaces. In this paper we study it under the weaker condition of subfitness, a separation condition that originates in pointfree topology. In particular, we extend some well known characterizations of these spaces to the subfit context (notably, their hereditary property and the preservation under surjective continuous closed maps) and present a similar study for stratifiable spaces, an important subclass of monotonically normal spaces. In the second part of the paper, we extend further these ideas to the lattice theoretic setting. In particular, we give the pointfree analogues of the previous results on monotonically normal spaces and introduce and investigate the natural pointfree counterpart of stratifiable spaces.

In this work, we consider a class of risk-averse maximum weighted subgraph problems (R-MWSP). Namely, assuming that each vertex of the graph is associated with a stochastic weight, such that the joint distribution is known, the goal is to obtain a subgraph of minimum risk satisfying a given hereditary property. We employ a stochastic programming framework that is based on the formalism of modern theory of risk measures in order to find minimum-risk hereditary structures in graphs with stochastic vertex weights. The introduced form of risk function for measuring the risk of subgraphs ensures that optimal solutions of R-MWS problems represent maximal subgraphs. A graph-based branch-and-bound (BnB) algorithm for solving the proposed problems is developed and illustrated on a special case of risk-averse maximum weighted clique problem. Numerical experiments on randomly generated Erdos-Renyi graphs demonstrate the computational performance of the developed BnB.

In this paper we will introduced soft disjoint sets, soft separated sets ,soft connected space , soft disconnected space ,and study the relation between soft disjoint sets and soft separated sets, define soft hereditary property and study soft hereditary property on soft connected spaces , study the product of two soft disconnected spaces and the product of soft connected with soft disconnected .

We investigate the computational complexity of Disjoint Π-Vertex Deletion. Here, given an input graph G = (V,E) and a vertex set S ⊆ V, called a solution set, whose removal results in a graph satisfying a non-trivial, hereditary property Π, we are asked to find a solution set S′ with |S′| < |S| and S′ ∩ S = ∅. This problem is partially motivated by the “compression task” occurring in the iterative compression technique. The complexity of this problem has already been studied, with the restriction that Π is satisfied by a graph G iff Π is satisfied by each connected component of G [7]. In this work, we remove this restriction and show that, except for few cases which are polynomial-time solvable, almost all other cases of Disjoint Π-Vertex Deletion are \(\mathcal{NP}\)-hard.