Search

Given a hereditary property of graphs $\mathcal{H}$ and a $p\in [0,1]$ , the edit distance function $\textrm{ed}_{\mathcal{H}}(p)$ is asymptotically the maximum proportion of edge additions plus edge deletions applied to a graph of edge density p sufficient to ensure that the resulting graph satisfies $\mathcal{H}$ . The edit distance function is directly related to other well-studied quantities such as the speed function for $\mathcal{H}$ and the $\mathcal{H}$ -chromatic number of a random graph.Let $\mathcal{H}$ be the property of forbidding an Erdős–Rényi random graph $F\sim \mathbb{G}(n_0,p_0)$ , and let $\varphi$ represent the golden ratio. In this paper, we show that if $p_0\in [1-1/\varphi,1/\varphi]$ , then a.a.s. as $n_0\to\infty$ , \begin{align*} {\textrm{ed}}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $p\in [1/3,2/3]$ for any $p_0\in (0,1)$ .A primary tool in the proof is the categorization of p-core coloured regularity graphs in the range $p\in[1-1/\varphi,1/\varphi]$ . Such coloured regularity graphs must have the property that the non-grey edges form vertex-disjoint cliques.

A rectangular floorplan (RFP) is a partition of a rectangle R into rectangles R 1 , R 2 , … , R n such that no four of them meet at a point. Rectangular floorplans find their applications in VLSI circuits floorplanning and architectural floorplanning. Let G represent the graph of a rectangular floorplan RFP 1 ( n ) and H be a subgraph of G , where n denotes the number of rectangles in RFP 1 ( n ) . It is well known that every subgraph of G may not admit an RFP, i.e., G does not have a hereditary property. Hence, in this paper, we first derive a necessary and sufficient condition for H to admit a rectangular floorplan RFP 2 ( n ) . Further, if H admits an RFP, we present a linear time transformation algorithm for deriving RFP 2 ( n ) from RFP 1 ( n ) .

Balogh, Bollobas and Weinreich showed that a parameter that has since been termed the distinguishing number can be used to identify a jump in the possible speeds of hereditary classes of graphs at the sequence of Bell numbers. We prove that every hereditary class that lies above the Bell numbers and has finite distinguishing number contains a boundary class for well-quasi-ordering. This means that any such hereditary class which in addition is defined by finitely many minimal forbidden induced subgraphs must contain an infinite antichain. As all hereditary classes below the Bell numbers are well-quasi-ordered, our results complete the answer to the question of well-quasi-ordering for hereditary classes with finite distinguishing number. We also show that the decision procedure of Atminas, Collins, Foniok and Lozin to decide the Bell number (and which now also decides well-quasi-ordering for classes of finite distinguishing number) has run time bounded by an explicit (quadruple exponential) function of the order of the largest minimal forbidden induced subgraph of the class., 21 pages, 1 figure

It was recently proved in Alon et al. (2017) that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing the following ordered matrix removal lemma: For any finite alphabet Γ, any hereditary property $\mathcal {P}$ of matrices over Γ, and any 𝜖 > 0, there exists $f_{\mathcal {P}}(\epsilon )$ such that for any matrix M over Γ that is 𝜖-far from satisfying $\mathcal {P}$, most of the $f_{\mathcal {P}}(\epsilon ) \times f_{\mathcal {P}}(\epsilon )$ submatrices of M do not satisfy $\mathcal {P}$. Here being 𝜖-far from $\mathcal {P}$ means that one needs to modify at least an 𝜖-fraction of the entries of M to make it satisfy $\mathcal {P}$. However, in the above general removal lemma, $f_{\mathcal {P}}(\epsilon )$ grows very quickly as a function of 𝜖− 1, even when $\mathcal {P}$ is characterized by a single forbidden submatrix. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following, which can be seen as an efficient binary matrix analogue of the triangle removal lemma: For any fixed s × t binary matrix A and any 𝜖 > 0 there exists δ > 0 polynomial in 𝜖, such that for any binary matrix M in which less than a δ-fraction of the s × t submatrices are equal to A, there exists a set of less than an 𝜖-fraction of the entries of M that intersects every copy of A in M. We generalize the work of Alon et al. (2007) and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas.

We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph G, a non-trivial hereditary property \(\varPi \) and an integer parameter k, the general problem \(P(G,\varPi ,k)\) asks whether there exists k vertices of G that induce a subgraph satisfying property \(\varPi \). This problem, \(P(G,\varPi ,k)\) has been proved to be \(\mathsf {NP}\)-complete by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be \(\mathsf {W}[1]\)-complete by Khot and Raman, if \(\varPi \) includes all trivial graphs (graphs with no edges) but not all complete graphs and vice versa; and is fixed-parameter tractable, otherwise. As the problem is \(\mathsf {W}[1]\)-complete on general graphs when \(\varPi \) includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes.

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.

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

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

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.

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.

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.

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.

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.

A subset S of the vertex set of a hypergraph H is called a dominating set of H if for every vertex v not in S there exists u@?S such that u and v are contained in an edge in H. The minimum cardinality of a dominating set in H is called the domination number of H and is denoted by @c(H). A transversal of a hypergraph H is defined to be a subset T of the vertex set such that T@?E 0@? for every edge E of H. The transversal number of H, denoted by @t(H), is the minimum number of vertices in a transversal. A hypergraph is of rank k if each of its edges contains at most k vertices. The inequality @t(H)>=@c(H) is valid for every hypergraph H without isolated vertices. In this paper, we investigate the hypergraphs satisfying @t(H)=@c(H), and prove that their recognition problem is NP-hard already on the class of linear hypergraphs of rank 3, while on unrestricted problem instances it lies inside the complexity class @Q"2^p. Structurally we focus our attention on hypergraphs in which each subhypergraph H^' without isolated vertices fulfills the equality @t(H^')=@c(H^'). We show that if each induced subhypergraph satisfies the equality then it holds for the non-induced ones as well. Moreover, we prove that for every positive integer k, there are only a finite number of forbidden subhypergraphs of rank k, and each of them has domination number at most k.

In the paper we introduce the new game--the unilateral $${\mathcal{P}}$$ -colouring game which can be used as a tool to study the r-colouring game and the (r, d)-relaxed colouring game. Let be given a graph G, an additive hereditary property $${\mathcal {P}}$$ and a set C of r colours. In the unilateral $${\mathcal {P}}$$ -colouring game similarly as in the r-colouring game, two players, Alice and Bob, colour the uncoloured vertices of the graph G, but in the unilateral $${\mathcal {P}}$$ -colouring game Bob is more powerful than Alice. Alice starts the game, the players play alternately, but Bob can miss his move. Bob can colour the vertex with an arbitrary colour from C, while Alice must colour the vertex with a colour from C in such a way that she cannot create a monochromatic minimal forbidden subgraph for the property $${\mathcal {P}}$$ . If after |V(G)| moves the graph G is coloured, then Alice wins the game, otherwise Bob wins. The $${\mathcal {P}}$$ -unilateral game chromatic number, denoted by $${\chi_{ug}^\mathcal {P}(G)}$$ , is the least number r for which Alice has a winning strategy for the unilateral $${\mathcal {P}}$$ -colouring game with r colours on G. We prove that the $${\mathcal {P}}$$ -unilateral game chromatic number is monotone and is the upper bound for the game chromatic number and the relaxed game chromatic number. We give the winning strategy for Alice to play the unilateral $${\mathcal {P}}$$ -colouring game. Moreover, for k ≥ 2 we define a class of graphs $${\mathcal {H}_k =\{G|{\rm every \;block \;of\;}G \; {\rm has \;at \;most}\; k \;{\rm vertices}\}}$$ . The class $${\mathcal {H}_k }$$ contains, e.g., forests, Husimi trees, line graphs of forests, cactus graphs. Let $${\mathcal {S}_d}$$ be the class of graphs with maximum degree at most d. We find the upper bound for the $${\mathcal {S}_2}$$ -unilateral game chromatic number for graphs from $${\mathcal {H}_3}$$ and we study the $${\mathcal {S}_d}$$ -unilateral game chromatic number for graphs from $${\mathcal {H}_4}$$ for $${d \in \{2,3\}}$$ . As the conclusion from these results we obtain the result for the d-relaxed game chromatic number: if $${G \in \mathcal {H}_k}$$ , then $${\chi_g^{(d)}(G) \leq k + 2-d}$$ , for $${k \in \{3, 4\}}$$ and $${d \in \{0, \ldots, k-1\}}$$ . This generalizes a known result for trees.

In this paper, we study constant-time algorithms on complex networks. In a recent work presented in ESA~2016, the author introduced a natural class of multigraphs called hierarchical-scale-free (HSF) multigraphs and showed that a very wide subclass of HSF is hyperfinite. Based on this result, a surprising result such that every property is constant-time testable for the subclass was obtained. However, this result is theoretical, and the algorithm obtained directly from it may not be practical. In this paper, first we present the result of our paper of ESA~2016, and next we consider what kind of properties are "efficiently" testable in practice. For this purpose, we consider hereditary properties. We show that for hyperfinite graph class, e.g., HSF, any hereditary property can be represented by the forbidden graph subset such that the number of graphs in the subset is bounded by a constant. From this result, it can be considered that to test a hereditary property is relatively easy.

The now famous inequality chain ir≤γ≤i≤β ≤ Γ ≤ IR, where ir and IR denote the lower and upper irredundance numbers of a graph, γ and Γ the lower and upper domination numbers, i the independent domination number and β the independence number of a graph, may be seen as the culmination of a process by which we start with independence (a hereditary property of vertex sets); we characterize maximal independence by domination (a superhereditary property of vertex sets), and then characterize minimal domination by irredundance (again a hereditary property). In this paper we generalize independent, dominating and irredundant sets of a graph G to what we will call s-dominating, s-independent and s-irredundant functions (for s a positive integer), which are functions of the type f : V (G) → N, in such a way that the maximal 1-independent, the minimal 1- dominating and the maximal 1-irredundant functions are the characteristic functions of the maximal independent, the minimal dominating and the maximal irred...

For a class of graphs $$\mathcal {P}$$, the Bounded $$\mathcal {P}$$-Block Vertex Deletion problem asks, given a graphi¾?G on n vertices and positive integersi¾?k andi¾?d, whether there is a seti¾?S of at most k vertices such that each block of $$G-S$$ has at most d vertices and is in $$\mathcal {P}$$. We show that when $$\mathcal {P}$$ satisfies a natural hereditary property and is recognizable in polynomial time, Bounded $$\mathcal {P}$$-Block Vertex Deletion can be solved in time $$2^{\mathcal {O}k \log d}n^{\mathcal {O}1}$$, and this running time cannot be improved to $$2^{ok \log d}n^{\mathcal {O}1}$$, in general, unless the Exponential Time Hypothesis fails. On the other hand, if $$\mathcal {P}$$ consists of only complete graphs, or only $$K_1, K_2$$, and cycle graphs, then Bounded $$\mathcal {P}$$-Block Vertex Deletion admits a $$c^{k}n^{\mathcal {O}1}$$-time algorithm for some constant c independent of d. We also show that Bounded $$\mathcal {P}$$-Block Vertex Deletion admits a kernel with $$\mathcal {O}k^2 d^7$$ vertices.

The range inclusion criterion for posinormality is studied in order to classify more examples of lower triangular factorable matrices as posinormal operators or not. Also, coposinormality is shown to be a hereditary property for lower triangular operators on ' 2 , and this leads to some results involving the posispectrum. Finally, sucient conditions are given for lower triangular factorable matrices to be supraposinormal, and an example is given of a lower triangular factorable matrix that is supraposinormal but neither posinormal nor coposinormal. The last two sections also contain more general results that apply to operators on abstract Hilbert spaces.

This paper defined the hereditary property (or constant property) concerning graph operation, and discussed various forms of the hereditary property under the circumstance of Cartesian product graph operation. The main conclusions include: The non-planarity and Hamiltonicity of graph are hereditary concerning the Cartesian product, but planarity of graph is not, Euler characteristic and non-hamiltonicity of graph are not hereditary as well. Therefore, when we applied this principle into practice, we testified that Hamilton cycle does exist in hypercube.

Isoperimetric inequalities have been studied since antiquity, and in recent decades they have been studied extensively on discrete objects, such as the hypercube. An important special case of this problem involves bounding the size of the shadow of a set system, and the basic question was solved by Kruskal (in 1963) and Katona (in 1968). In this paper we introduce the concept of the shadow \d\G of a collection \G of ordered graphs, and prove the following, simple-sounding statement: if n \in \N is sufficiently large, |V(G)| = n for each G \in \G, and |\G| < n, then |\d \G| \ge |\G|. As a consequence, we substantially strengthen a result of Balogh, Bollob��s and Morris on hereditary properties of ordered graphs: we show that if ��is such a property, and |��_k| < k for some sufficiently large k \in \N, then |��_n| is decreasing for k \le n < \infty., 23 pages

In “The structure of hereditary properties and colourings of random graphs” [Combinatorica 20(2) (2000), 173–202], Bollobas and the second author studied the probability of a hereditary property P in the probability space G(n,p). They found simple properties that closely approximate P in this space, and using these simple properties they determined the P-chromatic number of random graphs. In this note we point out that the analysis of hereditary properties in G(n,p) can be made more exact by means of the extremal properties of 2-coloured multigraphs, and we illustrate some cases in which the probability of P can thereby be calculated. At the same time we correct a mistake in the cited paper.

A new operation of product of groups, the n-periodic product of groups for odd exponent n ≥ 665, was proposed by the author in 1976 in the paper [1]. This operation is described on the basis of the Novikov-Adyan theory introduced in the monograph [2] of the author. It differs from the classic operations of direct and free products of groups, but has all of the natural properties of these operations, including the so-called hereditary property for subgroups. Thus, the well-known problem of A. I. Mal’tsev on the existence of such new operations was solved. Unfortunately, in the paper [1], the case where the initial groups contain involutions, was not analyzed in detail. It is shown that, in the case where the initial groups contain involutions, this small gap is easily removed by an additional restriction on the choice of defining relations for the periodic product. It suffices to simply exclude products of two involutions of previous ranks from the inductive process of defining new relations for any given rank α. It is suggested that the adequacy of the given restriction follows easily from the proof of the key Lemma II.5.21 in the monograph [2]. We also mention that, with this additional restriction, all the properties of the periodic product given in [1] remain true with obvious corrections of their formulation. Moreover, under this restriction, one can consider n-periodic products for any period n ≥ 665, including even periods.

A collection of a nonempty subsets of is called hereditary class if it is closed under hereditary property. In this work, we define and study the notion of some generalizations of -Lindelöf generalized topological spaces with respect to a hereditary class, namely; -Lindelöf hereditary generalized topological spaces. Moreover, investigate basic properties of the concepts, its relation to known concepts and its preservation by functions properties.

A hereditary property P^(^k^) is a class of k-graphs closed under isomorphism and taking induced sub-hypergraphs. Let P"n^(^k^) denote those k-graphs of P^(^k^) on vertex set {1,...,n}. We prove an asymptotic formula for log"2|P"n^(^k^)| in terms of a Turan-type function concerning forbidden induced sub-hypergraphs. This result complements several existing theorems for hereditary and monotone graph and hypergraph properties.

Given an independence system (E,P), the Minimum Partition Problem (MPP) seeks a partition of E into the least number of independent sets. This notion provides a unifying framework for a number of combinatorial optimisation problems, including various conditional colouring problems for graphs. The smallest integer n such that E can be partitioned into n independent sets is called the P-chromatic number of E. In this article we study MPP and the P-chromatic number with emphasis on connections with a few other well-studied optimisation problems. In particular, we show that the P-chromatic number of E is equal to the domination number of a split graph associated with (E,P). With the help of this connection we give a few upper bounds on the P-chromatic number of E in terms of some basic invariants of (E,P).

A property of graphs is a collection P of graphs closed under isomorphism; we call Phereditary if it is closed under taking induced subgraphs. Given a property P, we write P^n for the set of graphs in P with vertex set [n]={1,...,n}, and P"n for the isomorphism classes of graphs of order n that are in P. The cardinality |P^n| is the labelled speed of P and |P"n| is the unlabelled speed. In the last decade numerous results have been proved about the labelled speeds of hereditary properties, with emphasis on the striking phenomenon that only certain speeds are possible: there are various pairs of functions (f(n),F(n)), with F(n)much larger than f(n), such that if the labelled speed is infinitely often larger than f(n) then it is also larger than F(n) for all sufficiently large values of n. Putting it concisely: the speed jumps from f(n) to F(n). Recent work on hereditary graph properties has shown that ''large'' and ''small'' labelled speeds of hereditary graph properties do jump. The aim of this paper is to study the unlabelled speed of a hereditary property, with emphasis on jumps. Among other results, we shall show that the unlabelled speed of a hereditary graph property is either of polynomial order or at least S(n), the number of ways of partitioning a set with n indistinguishable elements.

Monotone normality is usually defined in the class of T1 spaces. In this paper new characterizations of monotone normality, free of T1 axiom, are provided and it is shown that in this context it is not a hereditary property. Also, a Tietze-type extension theorem for lattice-valued functions for this class of spaces is given.

Let P be a hereditary property. Let k"P(G) denote the number of forbidden subgraphs, which are contained in G. A graph G is said to be weaklyP-saturated, if G@?P and the edges of the complement of G can be labelled e"1,e"2,...,e"l in such way that for i=0,1,...,l-1 the inequality k"P(G"i"+"1)>k"P(G"i) holds, where G"0=G,G"i"+"1=G"i+e"i and G"l=K"n. The minimum possible size of weakly P-saturated graphs is denoted by wsat(n,P). In this paper we shall investigate some properties of weakly saturated graphs. We provide some estimations for the minimum size of weakly P-saturated graphs.

Given non-negative integers r, s, and t, an [r,s,t]-coloring of a graph G=(V(G),E(G)) is a mapping c from V(G)@?E(G) to the color set {0,1,...,k-1}, k@?N, such that |c(v"i)-c(v"j)|>=r for every two adjacent vertices v"i,v"j, |c(e"i)-c(e"j)|>=s for every two adjacent edges e"i,e"j, and |c(v"i)-c(e"j)|>=t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number@g"r","s","t(G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We characterize the properties O(r,s,t,k)={G:@g"r","s","t(G)==3 and max{r,s,t}=1 using well-known hereditary properties. The main results for k>=3 are summarized in a diagram.

If T = ( V , E ) is a tree then – T denotes the additive hereditary property consisting of all graphs that does not contain T as a subgraph. For an arbitrary vertex v of T we deal with a partition of T into two trees T 1 , T 2 , so that V ( T 1 ) ∩ V ( T 2 ) = { v } , V ( T 1 ) ∪ ( T 2 ) = V ( T ) , E ( T 1 ) ∩ E ( T 2 ) = ∅ , E ( T 1 ) ∪ E ( T 2 ) = E ( T ) , T [ V ( T 1 ) \ { v } ] ⊆ E ( T 1 ) and T [ V ( T 2 ) \ { v } ] ⊆ E ( T 2 ) . We call such a partition a T v − p a r t i t i o n of T. We study the following em: Given a graph G belonging to –T. Is it true that for any T v -partition T 1 , T 2 of T there exists a partition { V 1 , V 2 } of the vertices of G such that G [ V 1 ] ∈ − T 1 and G [ V 2 ] ∈ − T 2 ? This problem provides a natural generalization of Δ-partition problem studied by L. Lovasz ([L. Lovasz, On decomposition of graphs. Studia Sci. Math. Hungar. 1 (1966) 237–238]) and Path Partition Conjecture formulated by P. Mihok ([P. Mihok, Problem 4, in: M. Borowiecki, Z. Skupien (Eds.), Graphs, Hypergraphs and Matroids, Zielona Gora, 1985, p. 86]). We present some partial results and a contribution to the Path Kernel Conjecture that was formulated with connection to Path Partition Conjecture.

A sequence of integers { n i : i = 0, 1…} is an exhaustive weakly wandering sequence for a transformation T if for some measurable set W, X =⋃ ∞ i =0 T ni W ( disj . We introduce a hereditary Property (H) for a sequence of integers associated with an infinite ergodic transformation T , and show that it is a sufficient condition for the sequence to be an exhaustive weakly wandering sequence for T . We then show that every infinite ergodic transformation admits sequences that possess Property (H), and observe that Property (H) is inherited by all subsequences of a sequence that possess it. As a corollary, we obtain an application to tiling the set of integers ℤ with infinite subsets.

The edit distance between two graphs on the same labeled vertex set is defined to be the size of the symmetric difference of the edge sets. The edit distance function of a hereditary property $\mathcal{H}$ is a function of $p\in [0,1]$ that measures, in the limit, the maximum normalized edit distance between a graph of density $p$ and $\mathcal{H}$. In this paper, we address the edit distance function for $\mbox{Forb}(H)$, where $H=C_h^t$, the $t^{\rm th}$ power of the cycle of length $h$. For $h\geq 2t(t+1)+1$ and $h$ not divisible by $t+1$, we determine the function for all values of $p$. For $h\geq 2t(t+1)+1$ and $h$ divisible by $t+1$, the function is obtained for all but small values of $p$. We also obtain some results for smaller values of $h$., Comment: 21 pages, 1 figure

In this paper we study Banakh’s quarter-stratifiability among generalized ordered (GO)-spaces. All quarter-stratifiable GO-spaces have a σ \sigma -closed-discrete dense set and therefore are perfect, and have a G δ G_\delta -diagonal. We characterize quarter-stratifiability among GO-spaces and show that, unlike the situation in general topological spaces, quarter-stratifiability is a hereditary property in GO-spaces. We give examples showing that a separable perfect GO-space with a G δ G_\delta -diagonal can fail to be quarter-stratifiable and that any GO-space constructed on a Q-set in the real line must be quarter-stratifiable.

We first study the competitive ratio for the on-line version of the problem of finding a maximum-order induced subgraph satisfying some hereditary property, under the hypothesis that the input graph is revealed by clusters. Next, we focus ourselves on two of the most known instantiations of this problem: the maximum independent set and the maximum clique. Finally, we study a variant of the on-line maximum-weight induced hereditary subgraph problem. Our results can also be seen as general reductions, either from off-line problems to the corresponding on-line versions, or between on-line problems. The concept of reduction was absent, until now, from the on-line computation.

Let P be a hereditary property of words, i.e. , an infinite class of finite words such that every subword (block) of a word belonging to P is also in P . Extending the classical Morse-Hedlund theorem, we show that either P contains at least n+1 words of length n for every n or, for some N , it contains at most N words of length n for every n . More importantly, we prove the following quantitative extension of this result: if P has m ≤ n words of length n then, for every k ≥ n + m , it contains at most ⌈( m + 1)/2⌉⌈( m + 1)/2⌈ words of length k .

For a given graph G a subset X of vertices of G is called a dominating (irredundant) set with respect to additive induced-hereditary property P, if the subgraph induced by X has the property P and X is a dominating (an irredundant) set. A set S is independent with respect to P, if [S]∈P.We give some properties of dominating, irredundant and independent sets with respect to P and some relations between corresponding graph invariants. This concept of domination and irredundance generalizes acyclic domination and acyclic irredundance given by Hedetniemi et al. (Discrete Math. 222 (2000) 151).

We deal with MAXH"0-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (@d"0+1)/(B+2+@n"0), where B=max"v"@?"Vd"G(v), @d"0=min"v"@?"V"("H"""0")d"H"""0(v) and @n"0=(|V(H"0)|+1)/@d"0. Next, we show that this ratio rises up to 3/(B+1) when H"0=K"3. Finally, we provide hardness results for MAXK"3-FREE PARTIAL SUBGRAPH.

We describe a simple representation for the modules of a graph G. We show that the modules of G are in one-to-one correspondence with the ideals of certain posets. These posets are characterized and shown to be layered posets, that is, transitive closures of bipartite tournaments. Additionaly, we describe applications of the representation. Employing the above correspondence, we present methods for solving the following problems: (i) generate all modules of G, (ii) count the number of modules of G, (iii) find a maximal module satisfying some hereditary property of G and (iv) find a connected non-trivial module of G.