On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

Strengthening Erdös–Pósa property for minor‐closed graph classes

Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

Rank‐tolerance graph classes

In this article we introduce certain classes of graphs that generalize ?‐tolerance chain graphs. In a rank‐tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if and only if their joint rank exceeds (or equals) their joint tolerance. This article is concerned with investigating the graph classes that arise from a variety of functions, such as min, max, sum, and prod (product), that may be used as the coupling functions ? and ρ to define the joint tolerance and the joint rank. Our goal is to obtain basic properties of the graph classes from basic properties of the coupling functions. We prove a skew symmetry result that when either ? or ρ is continuous and weakly increasing, the (?,ρ)‐representable graphs equal the complements of the (ρ,?)‐representable graphs. In the case where either ? or ρ is Archimedean or dual Archimedean, the class contains all threshold graphs. We also show that, for min, max, sum, prod (product) and, in fact, for any piecewise polynomial ?, there are infinitely many split graphs which fail to be representable. In the reflexive case (where ? = ρ), we show that if ? is nondecreasing, weakly increasing and associative, the class obtained is precisely the threshold graphs. This extends a result of Jacobson, McMorris, and Mulder [10] for the function min to a much wider class, including max, sum, and prod. We also give results for homogeneous functions, powers of sums, and linear combinations of min and max. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Circular choosability

We study circular choosability, a notion recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch(G)=O(ch(G)+ln|V(G)|) for every graph G. We investigate a generalization of circular choosability, the circular f‐choosability, where f is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of τ ? sup{cch(G) : G is planar}, and we prove that 6≤τ≤8, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 241–270, 2009     

Excluding Induced Subdivisions of the Bull and Related Graphs

For any graph H, let Forb*(H) be the class of graphs with no induced subdivision of H. It was conjectured in [J Graph Theory, 24 (1997), 297–311] that, for every graph H, there is a function f_H: ?→? such that for every graph G∈Forb*(H), χ(G)≤f_H(ω(G)). We prove this conjecture for several graphs H, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex‐disjoint pendant edges), and what we call a “necklace,” that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:49–68, 2012     

Anti‐periodic solutions for evolution equations with mappings in the class (S+)

In this paper, we study the existence of anti‐periodic solutions for the first order evolution equation in a Hilbert space H, where G : H → ? is an even function such that ?G is a mapping of class (S₊) and f : ? → ? satisfies f(t + T) = –f(t) for any t ∈ ? with f(·) ∈ L²(0, T; H). (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimal Error Estimates for Analytic Continuation in the Upper Half‐Plane

Analytic functions in the Hardy class H² over the upper half‐plane ?₊ are uniquely determined by their values on any curve Γ lying in the interior or on the boundary of ?₊ . The goal of this paper is to provide a sharp quantitative version of this statement. We answer the following question: Given f of a unit H² ‐norm that is small on Γ (say, its L² ‐norm is of order ? ), how large can f be at a point z away from the curve? When Γ ? ??₊ , we give a sharp upper bound on ∣f(z)∣ of the form ?^γ , with an explicit exponent γ = γ(z) ∈ (0, 1) and explicit maximizer function attaining the upper bound. When Γ ? ?₊ we give an implicit sharp upper bound in terms of a solution of an integral equation on Γ . We conjecture and give evidence that this bound also behaves like ?^γ for some γ = γ(z) ∈ (0, 1) . These results can also be transplanted to other domains conformally equivalent to the upper half‐plane. © 2020 Wiley Periodicals, Inc.     

hp‐FEM for second moments of elliptic PDEs with stochastic data. I. Analytic regularity

For a linear second order elliptic partial differential operator A : V → V′, we consider the boundary value problems Au = f with stationary Gaussian random data f over the dual V′ of the separable Hilbert space V in which the solution u is sought. The operator A is assumed to be deterministic and bijective. The unique solution u = A^?1f is a Gaussian random field over V. It is characterized by its mean field E_u and its covariance C_u ∈ V ? V. For a class of Gaussian data f with piecewise analytic covariance kernels C_f ∈ V′ ? V′, we characterize analytic regularity of the covariance C_u of the Gaussian solution u in families of countably normed, weighted Sobolev spaces. To this end, we investigate shift theorems for the (nonhypoelliptic) deterministic tensor PDEs (A ? A)C_u = C_f proposed by Schwab and Todor, (Numer Math 95 (2003), 707–734) for the computation of covariance C_u of the random solution u. The nonhypoelliptic nature of A ? A implies that sing supp(C_u) is in general strictly larger than sing supp(C_f). For a model problem, analyticity and singular support of the solution is characterized completely. Based on our regularity results, we outline an hp‐finite element strategy (Pentenrieder, Ph.D thesis, ETHZurich, Dissertation No. 18729, 2009; Pentenrieder and Schwab, Research Report 2010‐08, Seminar for Applied Mathematics, ETH Zürich, Submitted) to approximate C_u stemming from covariances of stationary Gaussian data f. In the second part (Pentenrieder and Schwab, Research Report 2010–08, Seminar for Applied Mathematics, ETH Zürich, Submitted) of this work, we prove that this discretization gives exponential rates of convergence of the FE approximations, in terms of the number of degrees of freedom. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2012     

On the structure of graphs with a unique k‐factor

In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000     

A characterization of diameter-2-critical graphs with no antihole of length four

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n ²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.     

On similarity solutions for boundary layer flows with prescribed heat flux

This paper is concerned with existence, uniqueness and behaviour of the solutions of the autonomous third‐order non‐linear differential equation f?+(m+2)f f″?(2m+1)f′²=0 on ?⁺ with the boundary conditions f(0)=?γ, f′(∞)=0 and f″(0)=?1. This problem arises when looking for similarity solutions for boundary layer flows with prescribed heat flux. To study solutions we use some direct approach as well as blowing‐up co‐ordinates to obtain a plane dynamical system. Copyright © 2004 John Wiley & Sons, Ltd.     

Radius two trees specify χ-bounded classes

A class of graphs χ is said to be χ-bounded, with χ-binding function f, if for all G ? Γ, χ (G) ≦ f (ω(G)), where χ(G) is the chromatic number of G and ω(G) is the clique number of G. It has been conjectured that for every tree T, the class of graphs that do not induce T is χ-bounded. We show that this is true in the case where T is a tree of radius two.     

Some properties of entire functions with nonnegative Taylor coefficients

If f is an entire function of arbitrary finite order and with nonnegative Taylor coefficients, then we prove that its restriction to the positive part of the real axis belongs to de Haan’s class Γ. We also show that f/f′ is a Beurling slowly varying function.     

Convex labelings of trees

A convex labeling of a tree T of order n is a one-to-one function f from the vertex set of T into the nonnegative integers, so that f(y) ? (f(x) + f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f(v) ? n ? 1 for every vertex v of T, then f is a perfect convex labeling and T is called a perfectly convex tree. Jamison introduced this concept and conjectured that every tree is perfectly convex. We show that there exists an infinite class of trees, none of which is perfectly convex, and in fact prove that for every n there exists a tree of order n which requires a convex labeling with maximum value at least 6n/5 – 22. We also prove that every tree of order n admits a convex labeling with maximum label no more than n²/8 + 2. In addition, we present some constructive methods for obtaining perfect convex labelings of large classes of trees.     

Nowhere-zero flows in low genus graphs

A nowhere-zero k-flow is an assignment of edge directions and integer weights in the range 1,…, k ? 1 to the edges of an undirected graph such that at every vertex the flow in is equal to the flow out. Tutte has conjectured that every bridgeless graph has a nowhere-zero 5-flow. We show that a counterexample to this conjecture, minimal in the class of graphs embedded in a surface of fixed genus, has no face-boundary of length <7. Moreover, in order to prove or disprove Tutte's conjecture for graphs of fixed genus γ, one has to check graphs of order at most 28(γ ? 1) in the orientable case and 14(γ ? 2) in the nonorientable case. So, in particular, it follows immediately that every bridgeless graph of orientable genus ?1 or nonorientable genus ?2 has a nowhere-zero 5-flow. Using a computer, we checked that all graphs of orientable genus ?2 or nonorientable genus ?4 have a nowhere-zero 5-flow.     

Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

Note on vertex degrees of planar graphs

In this note the second moment of the vertex degree sequence of planar graphs is considered. We prove that

• 1 If G is an outerplanar graph of order n ? 3 then

• 2 If G is a planar graph of order n ? 4 then

where d₁,…,d_n is the vertex degree sequence of G. We exhibit all graphs for which these upper bounds are attained.     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.