Search

Our proof (with Robertson and Thomas) of the strong perfect graph conjecture ran to 179 pages of dense matter; and the most impenetrable part was the final 55 pages, on what we called ''wheel systems.'' In this paper we give a replacement for those 55 pages, much easier and shorter, using ''even pairs.'' This is based on an approach of Maffray and Trotignon.

We say that a graph G is k-Pfaffian if the generating function of its perfect matchings can be expressed as a linear combination of Pfaffians of k matrices corresponding to orientations of G. We prove that 3-Pfaffian graphs are 1-Pfaffian, 5-Pfaffian graphs are 4-Pfaffian and that a graph is 4-Pfaffian if and only if it can be drawn on the torus (possibly with crossings) so that every perfect matching intersects itself an even number of times. We state conjectures and prove partial results for k>5.

International audience; We prove that every n-vertex cubic bridgeless graph has at least n/2 perfect matchings and give a list of all 17 such graphs that have less than n/2+2 perfect matchings.

The attempts to construct a counterexample to the Strong Perfect Graph Conjecture yielded the notion of partitionable graphs as minimal imperfect graphs; then near-factorizations of finite groups gained some interest since from any near-factorization some partitionable graphs can be constructed in a natural way. Recently, the proof of SPGC was declared by Chudnovsky, Robertson, Seymour and Thomas [3], but near-factorizations remain interesting on their own rights as (i) rare objects being “close” to factorizations of groups; and (ii) they yield graphs with surprising properties.

We prove that a K"4-free graph G of order n, size m and maximum degree at most three has an independent set of cardinality at least 17([email protected]), where @l counts the number of components of G whose blocks are each either isomorphic to one of four specific graphs or edges between two of these four specific graphs and tr is the maximum number of vertex-disjoint triangles in G. Our result generalizes a bound due to Heckman and Thomas [C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math. 233 (2001) 233-237].

A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with |V(G)| maximum matchings and with |V(G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized.

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least (n + 1)!/4[q − p − (n − 1)(2 Delta − 3) + 4] different perfect matchings, where Delta is the maximum degree of a vertex in G.

The classical conditions of the existence of a perfect matching in bipartite graphs are used directly or indirectly to solve the assignment problem by the well-known algorithms. In the paper, we define a vector and an extended polymatroid for a bipartite graph so that the bipartite graph has a perfect matching if and only if the vector is the basis of the extended polymatroid.

We examine classes of extremal graphs for the inequality γ(G)⩽|V|-max{d(v)+βv(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and βv(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.

We discuss some new and old results about skew partitions in perfect graphs. © 2007 Published by Elsevier B.V.

The L(p,q)-labelling of graphs, is a graph theoretic framework introduced by Griggs and Yeh [Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595] to model the channel assignment problem. In this paper we improve the best known upper bound for the L(p,1)-labelling of graphs with given maximum degree. We show that for any integer p>=2, any graph G with maximum degree @D admits an L(p,1)-labelling such that the labels range from 0 to @D^2+(p-1)@D-2.

In this paper, we provide complete classification of classes of bipartite graphs defined by a single forbidden induced bipartite subgraph with respect to bounded/unbounded clique-width.

The subgraph homeomorphism problem has been shown by Robertson and Seymour to be polynomial-time solvable for any fixed pattern graph H. The result, however, is not practical, involving constants that are worse than exponential in |H|. Practical algorithms have only been developed for a few specific pattern graphs, the most recent of these being the wheels with four and five spokes. This paper looks at the subgraph homeomorphism problem where the pattern graph is a wheel with six spokes. The main result is a theorem characterizing graphs that do not contain subdivisions of W 6. We give an efficient algorithm for solving the subgraph homeomorphism problem for W 6. We also give a strengthening of the previous W 5 result.

We give a new and more direct proof of the characterization theorem for finitary homomorphism dualities of directed graphs. This result may be viewed as a characterization of Gallai–Hasse–Roy–Vitaver type theorems. We exhibit infinitely many examples where this general setting improves the bounds for chromatic number of graphs and we relate this to extremal problems for oriented graphs.

We define a new invarianttB(G)in bipartite graphs that is analogous to the toughnesst(G)and we give sufficient conditions in term oftB(G)for the existence ofk-factors in bipartite graphs. We also show that these results are sharp.

We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.

A connected planar graph is called ?$m$?-generalized fullerene if two of its faces are ?$m$?-gons and all other faces are pentagons and hexagons. In this paper we first determine some structural properties of ?$m$?-generalized fullerenes and then use them to obtain new results on the enumerative aspects of perfect matchings in such graphs. We provide both upper and lower bounds on the number of perfect matchings in ?$m$?-generalized fullerene graphs and state exact results in some special cases. Povezan ravninski graf se imenuje ?$m$?-posplošeni fuleren, če sta dve njegovi lici ?$m$?-kotnika, vsa druga lica pa so petkotniki in šestkotniki. V tem članku najprej določimo nekaj strukturnih lastnosti ?$m$?-posplošenih fulerenov, nato pa jih uporabimo za to, da dobimo nove rezultate v zvezi s preštevanjem popolnih prirejanj v takšnih grafih. Najdemo zgornjo in spodnjo mejo števila popolnih prirejanj v ?$m$?-posplošenih fulerenskih grafih in navedemo natančne razultate v nekaterih posebnih primerih.

It has been conjectured that for every claw-free graph $G$ the choice number of $G$ is equal to its chromatic number. We focus on the special case of this conjecture where $G$ is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most $4$.

Quantum state transfer within a quantum computer can be achieved by using a network of qubits, and such a network can be modelled mathematically by a graph. Here, we focus on the corresponding Laplacian matrix, and those graphs for which the Laplacian can be diagonalized by a Hadamard matrix. We give a simple eigenvalue characterization for when such a graph has perfect state transfer at time $\pi /2$; this characterization allows one to choose the correct eigenvalues to build graphs having perfect state transfer. We characterize the graphs that are diagonalizable by the standard Hadamard matrix, showing a direct relationship to cubelike graphs. We then give a number of constructions producing a wide variety of new graphs that exhibit perfect state transfer, and we consider several corollaries in the settings of both weighted and unweighted graphs, as well as how our results relate to the notion of pretty good state transfer. Finally, we give an optimality result, showing that among regular graphs of degree at most $4$, the hypercube is the sparsest Hadamard diagonalizable connected unweighted graph with perfect state transfer., Comment: 29 pages, 1 figure, minor revisions, fixed typos

We study perfect colorings of the Johnson graph in two colors. We give sufficient conditions for a perfect coloring of the Johnson graph to be k-regular and present examples of perfect colorings. The proof of the theorem is in many respects similar to the proof of the result by Etzion and Schwartz [1] on k-regularity of perfect codes.

Combining Ky Fan's theorem with ideas of Greene and Matousek we prove a generalization of Dol'nikov's theorem. Using another variant of the Borsuk-Ulam theorem due to Bacon and Tucker, we also prove the presence of all possible completely multicolored t-vertex complete bipartite graphs in t-colored t-chromatic Kneser graphs and in several of their relatives. In particular, this implies a generalization of a recent result of G. Spencer and F. E. Su., Comment: 16 pages

This paper considers some classes of graphs which are easily seen to have many perfect matchings. Such graphs can be considered robust with respect to the property of having a perfect matching if under vertex deletions (with some mild restrictions), the resulting subgraph continues to have a perfect matching. It is clear that you can destroy the property of having a perfect matching by deleting an odd number of vertices, by upsetting a bipartition or by deleting enough vertices to create an odd component. One class of graphs we consider is the m×m lattice graph (or grid graph) for m even. Matchings in such grid graphs correspond to coverings of an m×m checkerboard by dominoes. If in addition to the easy conditions above, we require that the deleted vertices be Θ(m) apart, the resulting graph has a perfect matching. The second class of graphs we consider is a k-fold product graph consisting of k copies of a given graph G with the ith copy joined to the i+1st copy by a perfect matching joining copies of the same vertex. We show that, apart from some easy restrictions, we can delete any vertices from the kth copy of G and find a perfect matching in the product graph with k suitably large.

Circular-perfect graphs form a natural superclass of the well-known perfect graphs by means of a more general coloring concept. For perfect graphs, a characterization by means of forbidden subgraphs was recently settled by Chudnovsky et al. [Chudnovsky, M., N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics 164 (2006) 51–229]. It is, therefore, natural to ask for an analogous characterization for circular-perfect graphs or, equivalently, for a characterization of all minimally circular-imperfect graphs. Our focus is the circular-(im)perfection of triangle-free graphs. We exhibit several different new infinite families of minimally circular-imperfect triangle-free graphs. This shows that a characterization of circular-perfect graphs by means of forbidden subgraphs is a difficult task, even if restricted to the class of triangle-free graphs. This is in contrary to the perfect case where it is long-time known that the only minimally imperfect triangle-free graphs are the odd holes [Tucker, A., Critical Perfect Graphs and Perfect 3-chromatic Graphs, J. Combin. Theory (B) 23 (1977) 143–149].

The pre-coloring extension problem consists, given a graph $G$ and a subset of nodes to which some colors are already assigned, in finding a coloring of $G$ with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that ``PrExt perfect'' graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (``co-Artemis'' graphs, which are ``co-perfectly contractile'' graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs.

We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane geometric graphs and connected plane geometric graphs as well as the number of cycle-free plane geometric graphs is minimized when S is in convex position. Moreover, these results hold for all these graphs with an arbitrary but fixed number of edges. Consequently, we provide a unified proof that the cardinality of any family of acyclic graphs (for example spanning trees, forests, perfect matchings, spanning paths, and more) is minimized for point sets in convex position. In addition we construct a new maximizing configuration, the so-called double zig-zag chain. Most noteworthy this example bears Θ* $${{(\sqrt{72}\,}^n)}$$ = Θ*(8.4853n) triangulations (omitting polynomial factors), improving the previously known best maximizing examples.

A conjecture of G. Fan and A. Raspaud asserts that every bridgeless cubic graph contains three perfect matchings with empty intersection. We suggest a possible approach to problems of this type, based on the concept of a balanced join in an embedded graph. The method can be used to prove a special case of a conjecture of E. Macajova and M. Skoviera on Fano colorings of cubic graphs.

Let ϕ(G), κ(G), α(G), χ(G), cl(G), diam(G) denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved: 1. max {ϕ(G): |V (G)| = 2n, κ(G) ≤ k} = k[(2n − 3)!!], 2. $$ \max {\left\{ {\phi {\left( G \right)}:{\left| {V{\left( G \right)}} \right|} = 2n,\alpha {\left( G \right)} \geqslant k} \right\}} = {\left[ {{\prod\limits_{i = 0}^{k - 1} {{\left( {2n - k - i} \right)}} }} \right]}{\left[ {{\left( {2n - 2k - 1} \right)}!!} \right]}, $$ 3. max{ϕ(G): |V (G)| = 2n, χ(G) ≤ k} = ϕ(T k,2n ) T k,2n is the Turan graph, that is a complete k-partite graph on 2n vertices in which all parts are as equal in size as possible, 4. max{ϕ(G): |V (G)| = 2n, cl(G) = 2} = n!, 5. max{ϕ(G): |V (G)| = 2n, diam(G) ≥ 2} = (2n − 2)(2n − 3)[(2n − 5)!!], max{ϕ(G): |V (G)| = 2n, diam(G) ≥ 3} = (n − 1)2[(2n − 5)!!].

A graph is distance-hereditary if the distance stays the same between any of two vertices in every connected induced subgraph containing both. Two well-known classes of graphs, trees and cographs, both belong to distance-hereditary graphs. In this paper, we first show that the perfect domination problem can be solved in sequential linear-time on distance-hereditary graphs. By sketching some regular property of the problem, we also show that it can be easily parallelized on distance-hereditary graphs.

International audience; We consider the class of Berge graphs that contain no odd prism and no square (cycle on four vertices). We prove that every graph G in this class either is a clique or has an even pair, as conjectured by Everett and Reed. This result is used to devise a polynomial-time algorithm to color optimally every graph in this class.

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of $H$-free split graphs whose clique-width is bounded. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs $H$ for which the class of $H$-free split graphs has bounded clique-width., 17 pages, 5 figures. An extended abstract of this paper appeared in the proceedings of EuroComb 2015

In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n43) time to find the chaotic numbers, with n3 the number of vertices in the largest partite set.

A kernel of a directed graph D is defined as an independent set which is reachable from each outside vertex by an arc. A graph G is called kernel-solvable if an orientation D of G has a kernel whenever each clique of G has a kernel in D. The notion of kernel-solvability has important applications in combinatorics, list coloring, and game theory. It turns out that kernel-solvability is equivalent to perfectness, as it was conjectured by Berge and Duchet in 1983. These and other kernel-related results are the subject of the present survey. Many of these results are independent of the strong perfect graph conjecture, yet, the recent proof of this conjecture and the efficient recognition of perfect graphs have several important implications, in particular in game theory, which are also included here.

Given a symmetric m by m matrix M over 0,1,*, the M-partition problem asks whether or not an input graph G can be partitioned into m parts corresponding to the rows (and columns) of M so that two distinct vertices from parts i and j (possibly with i=j) are non-adjacent if M(i,j)=0, and adjacent if M(i,j)=1. These matrix partition problems generalize graph colourings and homomorphisms, and arise frequently in the study of perfect graphs; example problems include split graphs, clique and skew cutsets, homogeneous sets, and joins.In this paper we study M-partitions restricted to perfect graphs. We identify a natural class of ‘normal’ matrices M for which M-partitionability of perfect graphs can be characterized by a finite family of forbidden induced subgraphs (and hence admits polynomial time algorithms for perfect graphs). We further classify normal matrices into two classes: for the first class, the size of the forbidden subgraphs is linear in the size of M; for the second class we only prove exponential bounds on the size of forbidden subgraphs. (We exhibit normal matrices of the second class for which linear bounds do not hold.)We present evidence that matrices M which are not normal yield badly behaved M-partition problems: there are polynomial time solvable M-partition problems that do not have finite forbidden subgraph characterizations for perfect graphs. There are M-partition problems that are NP-complete for perfect graphs. There are classes of matrices M for which even proving ‘dichotomy’ of the corresponding M-partition problems for perfect graphs—i.e., proving that these problems are all polynomial or NP-complete—is likely to be difficult.

The strong perfect graph conjecture, suggested by Claude Berge in 1960, had a major impact on the development of graph theory over the last 40 years. It has led to the definitions and study of many new classes of graphs for which the strong perfect graph conjecture has been verified. Powerful concepts and methods have been developed to prove the strong perfect graph conjecture for these special cases. In this paper we survey 120 of these classes, list their fundamental algorithmic properties and present all known relations between them.

A set S of pairwise nonadjacent vertices in an undirected graph G is called a stable transversal of G if S meets every maximal (with respect to set-inclusion) clique of G. G is called strongly perfect if all its induced subgraphs (including G itself) have stable transversals. A claw is a graph consisting of vertices a,b,c,d and edges ab,ac,ad. We characterize claw-free strongly perfect graphs by five infinite families of forbidden induced subgraphs. This result—whose validity had been conjectured by Ravindra [Research problems, Discrete Math. 80 (1990) 105–107]—subsumes the characterization of strongly perfect line-graphs that was discovered earlier by Ravindra [Strongly perfect line graphs and total graphs, Finite and Infinite Sets. Colloq. Math. Soc. János Bolyai 37 (1981) 621–633].

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.

In this paper we characterize subclasses of co-graphs defined by restricted NLC-width operations and subclasses of co-graphs defined by restricted clique-width operations. We show that a graph has NLCT-width 1 if and only if it is (C"4,P"4)-free. Since (C"4,P"4)-free graphs are exactly trivially perfect graphs, the set of graphs of NLCT-width 1 is equal to the set of trivially perfect graphs, and a recursive definition for trivially perfect graphs follows. Further we show that a graph has linear NLC-width 1 if and only if is (C"4,P"4,2K"2)-free. This implies that the set of graphs of linear NLC-width 1 is equal to the set of threshold graphs. We also give forbidden induced subgraph characterizations for co-graphs defined by restricted clique-width operations using P"4, 2K"2, and co-2P"3.

We present the first algorithm for generating random variates exactly uniformly from the set of perfect matchings of a bipartite graph with a polynomial expected running time over a nontrivial set of graphs. Previous Markov chain results obtain approximately uniform variates for arbitrary graphs in polynomial time, but their general running time is Θ(n10 (ln n)2). Other algorithms (such as Kasteleyn's O(n3) algorithm for planar graphs) concentrated on restricted versions of the problem. Our algorithm employs acceptance/rejection together with a new upper limit on the permanent of a form similar to Bregman's theorem. For graphs with 2n nodes, where the degree of every node is γn for a constant γ, the expected running time is O(n1.5 + .5/γ). Under these conditions, Jerrum and Sinclair showed that a Markov chain of Broder can generate approximately uniform variates in Θ(n4.5 + .5/γ ln n) time, making our algorithm significantly faster on this class of graphs. The problem of counting the number of perfect matchings in these types of graphs is # P complete. In addition, we give a 1 + σ approximation algorithm for finding the permanent of 0–1 matrices with identical row and column sums that runs in O(n1.5 + .5/γ (1/σ2) log (1/δ))$, where the probability that the output is within 1 + \sigma$ of the permanent is at least 1 – δ.

Given a set P of points in general position in the plane, the graph of triangulations ** of P has a vertex for every triangulation of P, and two of them are adjacent if they differ by a single edge exchange. We prove that the subgraph ** of **, consisting of all triangulations of P that admit a perfect matching, is connected. A main tool in our proof is a result of independent interest, namely that the graph ** that has as vertices the non-crossing perfect matchings of P and two of them are adjacent if their symmetric difference is a single non-crossing cycle, is also connected.

We study random lifts of a graph G as defined in [1]. We prove a 0-1 law which states that for every graph G either almost every lift of G has a perfect matching, or almost none of its lifts has a perfect matching. We provide a precise description of this dichotomy. Roughly speaking, the a.s. existence of a perfect matching in the lift depends on the existence of a fractional perfect matching in G. The precise statement appears in Theorem 1.

We present an O(n5) combinatorial algorithm for the minimum weighted coloring problem on claw-free perfect graphs, which was posed by Hsu and Nemhauser in 1984. Our algorithm heavily relies on the structural descriptions of claw-free perfect graphs given by Chavatal and Sbihi and by Maffray and Reed.

In this paper, we give a primitive recursive proof for a theorem that provides a measure of the extent to which a finite bipartite graph is a Ramsey object in the class of finite bipartite graphs.

The class of 2K2-free graphs includes several interesting subclasses such as split, pseudo-split, threshold graphs, complements to chordal, interval or trivially perfect graphs. The fundamental property of 2K2-free graphs is that they contain polynomially many maximal independent sets. As a consequence, several important problems that are NP-hard in general graphs, such as 3- colorability, maximum weight independent set (WIS), minimum weight independent dominating set (WID), become polynomial-time solvable when restricted to the class of 2K2-free graphs. In the present paper, we extend 2K2-free graphs to larger classes with polynomial-time solvable WIS or WID. In particular, we show that WIS can be solved in polynomial time for (K2 + K1,3)- free graphs and WID for (K2 + K1,2)-free graphs. The latter result is in contrast with the fact that independent domination is NP-hard in the class of 2K1,2-free graphs, which has been recently proven by Zverovich.

In this note, we present an apparently new and rather short proof of a celebrated theorem of Horst Sachs characterizing bipartite finite graphs in term of their eigenvalue spectrum. Moreover, the simplicity of the proof allows us to establish this theorem and related results as a special instance of much more general assertions regarding the spectral theory of “compact graphs”. Finally, some intriguing possible generalizations to locally finite, yet not “compact” graphs suggested by Horst Sachs are discussed in the last section.

Splitters are introduced to capture the meaning of barriers in graphs having a perfect internal matching. The factor-critical property is extended in a natural way to accommodate such graphs, and a characterization of factor-critical graphs is given in the new context. Two Tutte type theorems are presented for open graphs with perfect internal matchings, one on maximal splitters, and the other on maximal inaccessible splitters.

We prove different fixed subgraph properties for some infinite weakly modular graphs. In particular we prove that every self-contraction (map which preserves or collapses the edges) of a weakly median graph G fixes a non-empty finite regular weakly median subgraph of G if and only if G is connected and contains no infinite simplices and no isometric rays. We also prove some fixed finite simplex theorems for other weakly modular graphs such as Helly graphs, chordal graphs and bridged graphs.