On the entropy minimal hereditary classes of colored graphs

We consider the hereditary classes of edge-colored graphs. A class is called entropy minimal if it contains no proper hereditary subclasses with the same value of entropy (logarithmic density). For ordinary graphs it is known that, for all fixed a and b, the class consisting of all graphs whose vertex sets can be partitioned into a cliques and b independent sets is entropy minimal. We generalize this to colored graphs.     

On the complexity of the dominating induced matching problem in hereditary classes of graphs

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.     

On hereditary clique-Helly self-clique graphs

A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.     

On classes of minimal circular-imperfect graphs

Circular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ(G)?ω(G)+1.The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs.At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult.     

On an extension of distance hereditary graphs

Given a simple and finite connected graph G, the distance d_G(u,v) is the length of the shortest induced {u,v}-path linking the vertices u and v in G. Bandelt and Mulder [H.J. Bandelt, H.M. Mulder, Distance hereditary graphs, J. Combin. Theory Ser. B 41 (1986) 182-208] have characterized the class of distance hereditary graphs where the distance is preserved in each connected induced subgraph. In this paper, we are interested in the class of k-distance hereditary graphs (k∈N) which consists in a parametric extension of the distance heredity notion. We allow the distance in each connected induced subgraph to increase by at most k. We provide a characterization of k-distance hereditary graphs in terms of forbidden configurations for each k≥2.     

On graphs related to conjugacy classes of groups

LetG be a finite group. Attach toG the following two graphs: Γ — its vertices are the non-central conjugacy classes ofG, and two vertices are connected if their sizes arenot coprime, and Γ* — its vertices are the prime divisors of sizes of conjugacy classes ofG, and two vertices are connected if they both divide the size of some conjugacy class ofG. We prove that whenever Γ* is connected then its diameter is at most 3, (this result was independently proved in [3], for solvable groups) and Γ* is disconnected if and only ifG is quasi-Frobenius with abelian kernel and complements. Using the method of that proof we give an alternative proof to Theorems in [1],[2],[6], namely that the diameter of Γ is also at most 3, whenever the graph is connected, and that Γ is disconnected if and only ifG is quasi-Frobenius with abelian kernel and complements. As a result we conclude that both Γ and Γ* have at most two connected components. In [2],[3] it is shown that the above bounds are best possible. The content of this paper corresponds to a part of the author’s Ph.D. thesis carried out at the Tel Aviv University under the supervision of Prof. Marcel Herzog.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

On the structure of unbreakable graphs

A nonempty set C of vertices is a star-cutset in a graph G if G – C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. Va?ek Chvátal proposed to call a graph G unbreakable if neither G nor its complement G has a star-cutset. A path with four vertices and three edges will be termed a P₄. An edge uv of a graph G is called a wing, if for some vertices x, y, {u,v,x,y} induces a P₄ in G. We define recursively the coercion class C_uv of a wing uv as follows:

• 1 uv ∈ C_uv, and
• 1 if xy ∈ C_uv and xy, x'y' are wings of a same P₄ in G, then x'y' ∈ C_uv.

The purpose of this work is to present new results concerning unbreakable graphs, using the notion of coercion class. These results include a theorem asserting that every unbreakable graph contains at most two distinct coercion classes and a structure theorem for those unbreakable graphs that contain precisely two coercion classes. These results generalize several previously known results about unbreakable graphs.     

On the structure of infinite vertex-transitive graphs

A characterization of all vertex-transitive graphs Γ of connectivity l is given in terms of the lobe structure of Γ. Among these, all graphs are determined whose automorphism groups act primitively (respectively, regularly) on the vertex set.     

On the combinatorial structure of Rauzy graphs

Let S _m ⁰ be the set of all irreducible permutations of the numbers {1, ??,m} (m ?? 3). We define Rauzy induction mappings a and b acting on the set S _m ⁰ . For a permutation ?? ?? S _m ⁰ , denote by R(??) the orbit of the permutation ?? under the mappings a and b. This orbit can be endowed with the structure of an oriented graph according to the action of the mappings a and b on this set: the edges of this graph belong to one of the two types, a or b. We say that the graph R(??) is a tree composed of cycles if any simple cycle in this graph consists of edges of the same type. An equivalent formulation of this condition is as follows: a dual graph R*(??) of R(??) is a tree. The main result of the paper is as follows: if the graph R(??) of a permutation ?? ?? S _m ⁰ is a tree composed of cycles, then the set R(??) contains a permutation ?? ₀: i ? m + 1 ? i, i = 1, ??,m. The converse result is also proved: the graph R(?? ₀) is a tree composed of cycles; in this case, the structure of the graph is explicitly described.     

On the structure of bull-free perfect graphs

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0     

Switching classes of directed graphs

By analogy with Seidel switching classes of graphs, and two-graphs, this paper develops a theory of switching classes of directed graphs. The elements of the theory are these: there is a one-to-one correspondence among switching classes of directed graphs, two-digraphs, and cyclic triple covers of the complete digraph. If G is a group of automorphisms of a switching class of digraphs, there is a cohomological invariant γ which vanishes if and only if some digraph in the switching class is fixed by G. If G is cyclic then γ ≠ 0 if and only if all orbits on vertices have size divisible by 3 and a certain sum (defined in Theorem 3.5) is nonzero. There is a second cohomological invariant β which vanishes if and only if G can be realized as a group of automorphisms of the cyclic triple cover associated with the switching class. If G is cyclic, then β ≠ 0 if and only if G has a subgroup of order 3 for which γ ≠ 0. There is a formula for the number of isomorphism types of two-digraphs on n vertices which is a sum over the symmetric group S_n of a simple function of the cycle structure of its elements. Finally, the only elements of S_n which fix a digraph in every switching class of digraphs they fix are those elements containing a cycle whose length is not divisible by 3.     

On the structure of k-connected graphs without Kk-minor

Suppose G is a k-connected graph that does not contain K_k as a minor. What does G look like? This question is motivated by Hadwiger’s conjecture (Vierteljahrsschr. Naturforsch. Ges. Zürich 88 (1943) 133) and a deep result of Robertson and Seymour (J. Combin. Theory Ser. B. 89 (2003) 43).It is easy to see that such a graph cannot contain a (k−1)-clique, but could contain a (k−2)-clique, as K_k−5+G′, where G′ is a 5-connected planar graph, shows. In this paper, however, we will prove that such a graph cannot contain three “nearly” disjoint (k−2)-cliques. This theorem generalizes some early results by Robertson et al. (Combinatorica 13 (1993) 279) and Kawarabayashi and Toft (Combinatorica (in press)).     

On operations induced by hereditary classes on generalized topological spaces

We introduce the operator $\gamma_{\mu}^{*}$ given by a hereditary class and a generalized topology?μ, and investigate its properties. With the help of? $\gamma_{\mu}^{*}$ , we define $\gamma_{\mu}^{*}$ -semi-open sets which are generalized open sets on generalized topologies and study the relation between such sets and some generalized open sets (e.g. μ-semi-open sets, μ-β-open sets) on generalized topologies.