Transforming trees by successive local complementations

A local complementation of a simple graph G at a vertex v consists in replacing the subgraph induced by G on the neighborhood of v by the complementary graph. Two graphs are locally equivalent if they are related by a sequence of local complementations. H. M. Mulder conjectured that any two locally equivalent trees are isomorphic. We prove this conjecture and we characterize those graphs that are locally equivalent to trees.     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

Locally semicomplete digraphs: A generalization of tournaments

In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex x the vertices dominated by x induce a semicomplete digraph and the vertices that dominate x induce a semicomplete digraph. (A digraph is semicomplete if for any two distinct vertices u and ν, there is at least one arc between them.) This class contains the class of semicomplete digraphs, but is much more general. In fact, the class of underlying graphs of the locally semi-complete digraphs is precisely the class of proper circular-arc graphs (see [13], Theorem 3). We show that many of the classic theorems for tournaments have natural analogues for locally semicomplete digraphs. For example, every locally semicomplete digraph has a directed Hamiltonian path and every strong locally semicomplete digraph has a Hamiltonian cycle. We also consider connectivity properties, domination orientability, and algorithmic aspects of locally semicomplete digraphs. Some of the results on connectivity are new, even when restricted to semicomplete digraphs.     

Slim graphs

We consider the graphs that can be obtained by deleting in a Meyniel graphG all the edges induced by an arbitrary set of nodes. These graphs will be called Slim and we prove that they are perfect. We study relations between Slim graphs and other well known classes of perfect graphs; particularly we show that the perfection of Slim graphs gives a proof to the conjecture of M. Preissmann that Meyniel graphs are locally perfect.     

Perfect and locally perfect colorings

We present a new algorithm for coloring perfect graphs and use it to color the parity orderable graphs, a class which strictly contains parity graphs. Also, we modify this algorithm to obtain an O(m² + n) locally perfect coloring algorithm for parity graphs. © 1995 John Wiley & Sons, Inc.     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

Quasi-isometries between graphs and trees

Criteria for quasi-isometry between trees and general graphs as well as for quasi-isometries between metrically almost transitive graphs and trees are found. Thereby we use different concepts of thickness for graphs, ends and end spaces. A metrically almost transitive graph is quasi-isometric to a tree if and only if it has only thin metric ends (in the sense of Definition 3.6). If a graph is quasi-isometric to a tree then there is a one-to-one correspondence between the metric ends and those d-fibers which contain a quasi-geodesic. The graphs considered in this paper are not necessarily locally finite.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

Combinatorially homogeneous graphs

Gardiner classified ultrahomogeneous graphs and posed the problem of defining “combinatorial homogeneity”. Later, Ronse proved that homogeneous graphs are ultrahomogeneous by classifying such graphs. In this paper, we give a direct proof that (suitably defined) combinatorially homogeneous graphs are ultrahomogeneous. Also, we clasify combinatorially C-homogeneous graphs.     

On a Problem of Cameron’s on Inexhaustible Graphs

A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G. We address a question of Cameron [6], who asked which countable graphs are inexhaustible. In particular, we prove that there are continuum many countable inexhaustible graphs with properties in common with the infinite random graph, including adjacency properties and universality. Locally finite inexhaustible graphs and forests are investigated, as is a semigroup structure on the class of inexhaustible graphs. We extend a result of [7] on homogeneous inexhaustible graphs to pseudo-homogeneous inexhaustible graphs.The authors gratefully acknowledge support from the Natural Science and Engineering Research Council of Canada (NSERC).     

Complete <Emphasis Type="Italic">k</Emphasis>-Curvature Homogeneous Pseudo-Riemannian Manifolds

Abstract. For k ≥ 2, we exhibit complete k-curvature homogeneous neutral signature pseudo-Riemannian manifolds which are not locally affine homogeneous (and hence not locally homogeneous). All the local scalarWeyl invariants of these manifolds vanish. These manifolds are Ricci flat, Osserman, and Ivanov-Petrova. Mathematics Subject Classification (2000): 53B20     

Locally Paley Graphs

We conjecturethat all locally Paley graphs are known. For locally Paley(p)with p < 100000 this is true.     

Three- and Four-Dimensional Einstein-like Manifolds and Homogeneity

The aim of this paper is to study three- and four-dimensional Einstein-like Riemannian manifolds which are Ricci-curvature homogeneous, that is, have constant Ricci eigenvalues. In the three-dimensional case, we present the complete classification of these spaces while, in the four-dimensional case, this classification is obtained in the special case where the manifold is locally homogeneous. We also present explicit examples of four-dimensional locally homogeneous Riemannian manifolds whose Ricci tensor is cyclic-parallel (that is, are of type A) and has distinct eigenvalues. These examples are invalidating an expectation stated by F. Podestá and A. Spiro, and illustrating a striking contrast with the three-dimensional case (where this situation cannot occur). Finally, we also investigate the relation between three- and four-dimensional Einstein-like manifolds of type A and D'Atri spaces, that is, Riemannian manifolds whose geodesic symmetries are volume-preserving (up to sign).     

A product formula for orthogonal polynomials associated with infinite distance-transitive graphs

The infinite, locally finite distance-transitive graphs form an extension of homogeneous trees and are described by two discrete parameters. The associated orthogonal polynomials may be regarded as spherical functions of certain Gelfand pairs or as characters of some polynomial hypergroups; they are certain Bernstein polynomials and admit a discrete nonnegative product formula. In this paper we use the graph-theoretic origin of these polynomials to derive the existence of positive dual continuous product and transfer formulas. The dual product formulas will be computed explicitly.     

Simplicity of <Emphasis Type="Italic">C</Emphasis>*-algebras associated to row-finite locally convex higher-rank graphs

In a previous work, the authors showed that the C*-algebra C*(Λ) of a row-finite higher-rank graph Λ with no sources is simple if and only if Λ is both cofinal and aperiodic. In this paper, we generalise this result to row-finite higher-rank graphs which are locally convex (but may contain sources). Our main tool is Farthing’s “removing sources” construction which embeds a row-finite locally convex higher-rank graph in a row-finite higher-rank graph with no sources in such a way that the associated C*-algebras are Morita equivalent.     

Locally finite homogeneous graphs

A connected graph G is said to be z-homogeneous if any isomorphism between finite connected induced subgraphs of G extends to an automorphism of G. Finite z-homogeneous graphs were classified in [17]. We show that z-homogeneity is equivalent to finite-transitivity on the class of infinite locally finite graphs. Moreover, we classify the graphs satisfying these properties. Our study of bipartite z-homogeneous graphs leads to a new characterization for hypercubes.     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Locally petersen graphs

A graph Γ is locally Petersen if, for each point t of Γ, the graph induced by Γ on all points adjacent to t is isomorphic to the Petersen graph. We prove that there are exactly three isomorphism classes of connected, locally Petersen graphs and further characterize these graphs by certain of their parameters.