Generating weakly triangulated graphs

We show that a graph is weakly triangulated, or weakly chordal, if and only if it can be generated by starting with a graph with no edges, and repeatedly adding an edge, so that the new edge is not the middle edge of any chordless path with four vertices. This is a corollary of results due to Sritharan and Spinrad, and Hayward, Hoång and Maffray, and a natural analog of a theorem due to Fulkerson and Gross, which states that a graph is triangulated, or chordal, if and only if it can be generated by starting with a graph with no vertices, and repeatedly adding a vertex, so that the new vertex is not the middle vertex of any chordless path with three vertices. Our result answers the question of whether there exists a composition scheme that generates exactly the class of weakly triangulated graphs. © 1996 John Wiley & Sons, Inc.     

Weakly triangulated graphs

A graph is triangulated if it has no chordless cycle with four or more vertices. It follows that the complement of a triangulated graph cannot contain a chordless cycle with five or more vertices. We introduce a class of graphs (namely, weakly triangulated graphs) which includes both triangulated graphs and complements of triangulated graphs (we define a graph as weakly triangulated if neither it nor its complement contains a chordless cycle with five or more vertices). Our main result is a structural theorem which leads to a proof that weakly triangulated graphs are perfect.     

Chromaticity of triangulated graphs

It is shown here that a connected graph G without subgraphs isomorphic to K₄ is triangulated if and only if its chromatic polynomial P(G,λ) equals λ(λ ? 1)^m(λ ? 2)^r for some integers m ≧ 1, r ≧ 0. This result generalizes the characterization of Two-Trees given by E.G. Whitehead [“Chromaticity of Two-Trees,” Journal of Graph Theory 9 (1985) 279–284].     

More characterizations of triangulated graphs

New characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability function has all its coefficients equal to 0, +1 or ?1.     

Representing triangulated graphs in stars

A graphG is calledrepresentable in a tree T, ifG is isomorphic to the intersection graph of a family of subtrees ofT. In this paper those graphs are characterized which are representable in some subdivision of theK _1,n. In the finite case polynomial-time recognition algorithms of these graphs are given. But this concept can be generalized to essentially infinite graphs by using no more trees but ‘tree-like’ posets and representability of graphs in these posets.     

Slightly triangulated graphs are perfect

A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C _k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;

1. G contains no chordless cycle with at least 5 vertices.
2. For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.

     

On weakly cospectral graphs

We prove that any set of pair-wise nonisomorphic strongly connected weakly cospectral pseudodigraphs whose set of nilpotency indices is finite also is finite.     

Submanifolds weakly associated with graphs

We establish an interesting link between differential geometry and graph theory by defining submanifolds weakly associated with graphs. We prove that, in a local sense, every submanifold satisfies such an association, and other general results. Finally, we study submanifolds associated with graphs either in low dimensions or belonging to some special families.     

On some weakly bipartite graphs

We characterize a class of weakly bipartite graphs. In this case, the max-cut problem can be solved by finding a minimum two-commodity cut.     

A relationship between triangulated graphs,comparability graphs,proper interval graphs,proper circular-arc graphs,and nested interval graphs

Given a set F of digraphs, we say a graph G is a F-graph (resp., F*-graph) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in F. It is proved that all the classes of graphs mentioned in the title are F-graphs or F*-graphs for subsets F of a set of three digraphs.     

Rank-perfect and" weakly rank-perfect graphs

An edge e of a perfect graph G is critical if G−e is imperfect. We would like to decide whether G−e is still “almost perfect” or already “very imperfect”. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.     

Edmonds polytopes and weakly hamiltonian graphs

Jack Edmonds developed a new way of looking at extremal combinatorial problems and applied his technique with a great success to the problems of the maximal-weight degreeconstrained subgraphs. Professor C. St. J.A. Nash-Williams suggested to use Edmonds' approach in the context of hamiltonian graphs. In the present paper, we determine a new set of inequalities (the comb inequalities) which are satisfied by the characteristic functions of hamiltonian circuits but are not explicit in the straightforward integer programming formulation. A direct application of the linear programming duality theorem then leads to a new necessary condition for the existence of hamiltonian circuits; this condition appears to be stronger than the ones previously known. Relating linear programming to hamiltonian circuits, the present paper can also be seen as a continuation of the work of Dantzig, Fulkerson and Johnson on the traveling salesman problem.     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

A class of weakly perfect graphs

A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.     

Geometric graphs which are 1-skeletons of unstacked triangulated polygons

We give sufficient (and necessary) conditions of local character ensuring that a geometric graph is the 1-skeleton of an unstacked triangulation of a simple polygon.