Detecting an induced subdivision of K4

In this article, we propose a polynomial-time algorithm to test whether a given graph contains a subdivision of K₄ as an induced subgraph. This continues the study of detecting an induced subdivision of H for some fixed graph H, which is still far from being complete. Our result answers a question by Chudnovsky et al. and Lévêque et al.     

Triangle-free graphs with no six-vertex induced path

The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication).     

Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable

We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of are 3-colorable. This proves a conjecture of Trotignon and Vušković [J. Graph Theory. 84 (2017), no. 3, pp. 233–248].     

Large induced subgraphs with equated maximum degree

For a graph G, denote by f_k(G) the smallest number of vertices that must be deleted from G so that the remaining induced subgraph has its maximum degree shared by at least k vertices. It is not difficult to prove that there are graphs for which already , where n is the number of vertices of G. It is conjectured that for every fixed k. We prove this for k=2,3. While the proof for the case k=2 is easy, already the proof for the case k=3 is considerably more difficult. The case k=4 remains open.A related parameter, s_k(G), denotes the maximum integer m so that there are k vertex-disjoint subgraphs of G, each with m vertices, and with the same maximum degree. We prove that for every fixed k, s_k(G)≥n/k−o(n). The proof relies on probabilistic arguments.     

Large induced subgraphs with three repeated degrees

For any positive integer k, let $C(k)$ denote the least integer such that any n-vertex graph has an induced subgraph with at least $n?C(k)$ vertices, in which at least $\min ?\{k,n?C(k)\}$ vertices are of the same degree. Caro, Shapira and Yuster initially studied this parameter and showed that $\mathrm{\Omega }(k\log ?k)\le C(k)\le {(8k)}^k$. For the first nontrivial case, the authors proved that $3\le C(3)\le 6$, and the exact value was left as an open problem. In this paper, we first show that $3\le C(3)\le 4$, improving the former result as well as a recent result of Kogan. For special families of graphs, we prove that $C(3)=3$ for $K_5$-free graphs, and $C(3)=1$ for large $C_{2s+1}$-free graphs. In addition, extending a result of Erd?s, Fajtlowicz and Staton, we assert that every $K_r$-free graph is an induced subgraph of a $K_r$-free graph in which no degree occurs more than three times.     

Detecting induced subgraphs

An s-graph is a graph with two kinds of edges: subdivisible edges and real edges. A realisation of an s-graph B is any graph obtained by subdividing subdivisible edges of B into paths of arbitrary length (at least one). Given an s-graph B, we study the decision problem Π_B whose instance is a graph G and question is “Does G contain a realisation of B as an induced subgraph?”. For several B’s, the complexity of Π_B is known and here we give the complexity for several more.Our NP-completeness proofs for Π_B’s rely on the NP-completeness proof of the following problem. Let be a set of graphs and d be an integer. Let be the problem whose instance is (G,x,y) where G is a graph whose maximum degree is at most d, with no induced subgraph in and x,yV(G) are two non-adjacent vertices of degree 2. The question is “Does G contain an induced cycle passing through x,y?”. Among several results, we prove that is NP-complete. We give a simple criterion on a connected graph H to decide whether is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.     

Two forbidden induced subgraphs and well-quasi-ordering

It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P₄. However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.     

Scalar and Hermite subdivision schemes

A criterion of convergence for stationary nonuniform subdivision schemes is provided. For periodic subdivision schemes, this criterion is optimal and can be applied to Hermite subdivision schemes which are not necessarily interpolatory. For the Merrien family of Hermite subdivision schemes which involve two parameters, we are able to describe explicitly the values of the parameters for which the Hermite subdivision scheme is convergent.     

Reconstructing graphs from size and degree properties of their induced k-subgraphs

As a variant of the famous graph reconstruction problem we characterize classes of graphs of order n such that all their induced subgraphs on k?n vertices satisfy some property related to the number of edges or to the vertex degrees.We give complete solutions for the properties (i) to be regular, (ii) to be regular modulo m?2 or (iii) to have one of two possible numbers of edges. Furthermore, for an order n large enough, we give solutions for the properties (iv) to be bi-regular or (v) to have a bounded difference between the maximum and the minimum degree.     

Estimating error bounds for quaternary subdivision schemes

This paper deals with the error estimation techniques of quaternary subdivision schemes. The estimation is expressed in terms of initial control point sequences and constants. It is independent of subdivision process and parametrization therefore its evaluation is straightforward.     

Parameterized graph cleaning problems

We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference |V(G)|−|V(H)| with H and G being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We show fixed-parameter tractability of the cases where both H and G are planar and H is 3-connected, or H is a tree and G is arbitrary. We also prove that the problem when H and G are both 3-connected planar graphs is NP-complete without parameterization.     

Totally positive functions through nonstationary subdivision schemes

In this paper a new class of nonstationary subdivision schemes is proposed to construct functions having all the main properties of B-splines, namely compact support, central symmetry and total positivity. We show that the constructed nonstationary subdivision schemes are asympotically equivalent to the stationary subdivision scheme associated with a B-spline of suitable degree, but the resulting limit function has smaller support than the B-spline although keeping its regularity.     

Multiresolution analyses originated from nonstationary subdivision schemes

We analyze the properties of a new class of totally positive refinable functions obtained from nonstationary subdivision schemes. We show that the corresponding system of the integer translates is linearly independent, satisfies a Whitney–Schoenberg condition, reproduces polynomials up to a certain degree and generates a multiresolution analysis. Finally, pre-wavelets and bases on the interval are constructed.     

Finiteness conjecture and subdivision

The finiteness conjecture by J.C. Lagarias and Y. Wang states that the joint spectral radius of a finite set of square matrices is attained on some finite product of such matrices. This conjecture is known to be false in general. Nevertheless, we show that this conjecture is true for a big class of finite sets of square matrices used for the smoothness analysis of scalar univariate subdivision schemes with finite masks.     

From symmetric subdivision masks of Hurwitz type to interpolatory subdivision masks

In this paper we present a general strategy to deduce a family of interpolatory masks from a symmetric Hurwitz non-interpolatory one. This brings back to a polynomial equation involving the symbol of the non-interpolatory scheme we start with. The solution of the polynomial equation here proposed, tailored for symmetric Hurwitz subdivision symbols, leads to an efficient procedure for the computation of the coefficients of the corresponding family of interpolatory masks. Several examples of interpolatory masks associated with classical approximating masks are given.     

Spectral radii and eigenvalues of subdivision operators

This paper discusses the spectra of matrix subdivision operators. We establish some formulas for spectral radii of subdivision operators on various invariant subspaces in . A formula for the spectral radius of a subdivision operator, in terms of the moduli of eigenvalues, is derived under a mild condition. The results are even new in the scalar case. In this case, we show that the subdivision operator has no eigenvector in if the corresponding subdivision scheme converges for some .

     

Spectra of subdivision operators

Let be a sequence of complex numbers and except for finitely many . The subdivision operator associated with is the bi-infinite matrix . This operator plays an important role in wavelet analysis and subdivision algorithms. As the adjoint it is closely related to the well-known transfer operators (also called Ruelle operator).

In this paper we show that for any , the spectrum of in is always a closed disc centered at the origin. Moreover, except for finitely many points, all the points in the open disc of the spectrum lie in the residual spectrum.