Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors

A hereditary property of graphs is any class of graphs closed under isomorphism and subgraphs. Let 𝒫₁, 𝒫₂,…, 𝒫_n be hereditary properties of graphs. We say that a graph G has property 𝒫_1°𝒫_2°···_°𝒫_n if the vertex set of G can be partitioned into n sets V₁, V₂,…, V_n such that the subgraph of G induced by V_i belongs to 𝒫_i; i = 1, 2,…, n. A hereditary property is said to be reducible if there exist hereditary properties 𝒫₁ and 𝒫₂ such that ℛ = 𝒫_1°𝒫₂; otherwise it is irreducible. We prove that the factorization of a reducible hereditary property into irreducible factors is unique whenever the property is additive, i.e., it is closed under the disjoint union of graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 44–53, 2000     

The fine structure of octahedron-free graphs

This paper is one of a series of papers in which, for a family L of graphs, we describe the typical structure of graphs not containing any L∈L. In this paper, we prove sharp results about the case L={O₆}, where O₆ is the graph with 6 vertices and 12 edges, given by the edges of an octahedron. Among others, we prove the following results.(a) The vertex set of almost every O₆-free graph can be partitioned into two classes of almost equal sizes, U₁ and U₂, where the graph spanned by U₁ is a C₄-free and that by U₂ is P₃-free.(b) Similar assertions hold when L is the family of all graphs with 6 vertices and 12 edges.(c) If H is a graph with a color-critical edge and χ(H)=p+1, then almost every sH-free graph becomes p-chromatic after the deletion of some s−1 vertices, where sH is the graph formed by s vertex disjoint copies of H.These results are natural extensions of theorems of classical extremal graph theory. To show that results like those above do not hold in great generality, we provide examples for which the analogs of our results do not hold.     

Constructions of infinite graphs with Ramsey property

For every infinite cardinal λ and 2 ≤ n < ω there is a directed graph D of size λ such that D does not contain directed circuits of length ≤n and if its vertices are colored with <λ colors, then there is a monochromatic directed circuit of length n + 1. For every infinite cardinal λ and finite graph X there is a λ-sized graph Y such that if the vertices of Y are colored with <λ colors, then there is a monochromatic induced copy of X. Further, Y does not contain larger cliques or shorter odd circuits than X. The constructions are using variants of Specker-type graphs.     

Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs.     

On the strong p-Helly property

The notion of strong p-Helly hypergraphs was introduced by Golumbic and Jamison in 1985 [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B 38 (1985) 8-22]. Independently, other authors [A. Bretto, S. Ubéda, J. ?erovnik, A polynomial algorithm for the strong Helly property. Inform. Process. Lett. 81 (2002) 55-57, E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220, W.D. Wallis, Guo-Hui Zhang, On maximal clique irreducible graphs. J. Combin. Math. Combin. Comput. 8 (1990) 187-193.] have also considered the strong Helly property in other contexts. In this paper, we characterize strong p-Helly hypergraphs. This characterization leads to an algorithm for recognizing such hypergraphs, which terminates within polynomial time whenever p is fixed. In contrast, we show that the recognition problem is co-NP-complete, for arbitrary p. Further, we apply the concept of strong p-Helly hypergraphs to the cliques of a graph, leading to the class of strong p-clique-Helly graphs. For p=2, this class is equivalent to that of hereditary clique-Helly graphs [E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220]. We describe a characterization for this class and obtain an algorithm for recognizing such graphs. Again, the algorithm has polynomial-time complexity for p fixed, and we show the corresponding recognition problem to be NP-hard, for arbitrary p.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

Geodesics and almost geodesic cycles in random regular graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d_G(u, v) is at least d_C(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = log_d?1log_d?1n+ ω(n) and |C| = 2log_d?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011     

群的遗传根性和强半单根性

本文利用群的根性的性质,解决了Szasz在环的根性理论中提出的公开问题在群论中的对应问题.同时我们研究了群的遗传根性和强半单根性的一些性质,并介绍了群的根类的交运算和并运算,由此得到了一些很好的结果.     

The maximum edit distance from hereditary graph properties

For a graph property , the edit distance of a graph G from , denoted , is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a graph satisfying . What is the largest possible edit distance of a graph on n vertices from ? Denote this distance by .A graph property is hereditary if it is closed under removal of vertices. In a previous work, the authors show that for any hereditary property, a random graph essentially achieves the maximal distance from , proving: with high probability. The proof implicitly asserts the existence of such , but it does not supply a general tool for determining its value or the edit distance.In this paper, we determine the values of and for some subfamilies of hereditary properties including sparse hereditary properties, complement invariant properties, (r,s)-colorability and more. We provide methods for analyzing the maximum edit distance from the graph properties of being induced H-free for some graphs H, and use it to show that in some natural cases G(n,1/2) is not the furthest graph. Throughout the paper, the various tools let us deduce the asymptotic maximum edit distance from some well studied hereditary graph properties, such as being Perfect, Chordal, Interval, Permutation, Claw-Free, Cograph and more. We also determine the edit distance of G(n,1/2) from any hereditary property, and investigate the behavior of as a function of p.The proofs combine several tools in Extremal Graph Theory, including strengthened versions of the Szemerédi Regularity Lemma, Ramsey Theory and properties of random graphs.     

Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

The common structure graph: Common structural features of a set of graphs

A method is proposed for abstracting the common features of a set of graphs. It is based on the graph homomorphisms that a set of graphs share. A semilattice structure is imposed on the partial order of graph homomorphisms of a set of graphs. The ‘common structure graphs’ are defined in relation to this semilattice.     

Almost all 5-regular graphs have a 3-flow

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.     

Factor-critical property in 3-dominating-critical graphs

A vertex subset S of a graph G is a dominating set if every vertex of G either belongs to S or is adjacent to a vertex of S. The cardinality of a smallest dominating set is called the dominating number of G and is denoted by γ(G). A graph G is said to be γ-vertex-critical if γ(G−v)<γ(G), for every vertex v in G.Let G be a 2-connected K_1,5-free 3-vertex-critical graph of odd order. For any vertex v∈V(G), we show that G−v has a perfect matching (except two graphs), which solves a conjecture posed by Ananchuen and Plummer [N. Ananchuen, M.D. Plummer, Matchings in 3-vertex critical graphs: The odd case, Discrete Math., 307 (2007) 1651-1658].     

Nowhere-zero 4-flow in almost Petersen-minor free graphs

Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let be the graph obtained from the Petersen graph by contracting μ edges from a perfect matching. In this paper we prove that every bridgeless -minor free graph admits a nowhere-zero 4-flow.     

What is the furthest graph from a hereditary property?

For a graph property P, the edit distance of a graph G from P, denoted E_P(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge‐modification problems, in which one wishes to find or approximate the value of E_P(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = E_P(G(n,p(P))) + o(n²) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The locally 2-arc transitive graphs admitting an almost simple group of Suzuki type

In this paper, seven families of vertex-intransitive locally (G,2)-arc transitive graphs are constructed, where Sz(q)?G?Aut(Sz(q)), q=²2k+1 for some k∈N. It is then shown that for any graph Γ in one of these families, Sz(q)?Aut(Γ)?Aut(Sz(q)) and that the only locally 2-arc transitive graphs admitting an almost simple group of Suzuki type whose vertices all have valency at least three are (i) graphs in these seven families, (ii) (vertex transitive) 2-arc transitive graphs admitting an almost simple group of Suzuki type, or (iii) double covers of the graphs in (ii). Since the graphs in (ii) have been classified by Fang and Praeger (1999) [6], this completes the classification of locally 2-arc transitive graphs admitting a Suzuki simple group     

Shadows of ordered graphs

Isoperimetric inequalities have been studied since antiquity, and in recent decades they have been studied extensively on discrete objects, such as the hypercube. An important special case of this problem involves bounding the size of the shadow of a set system, and the basic question was solved by Kruskal (in 1963) and Katona (in 1968). In this paper we introduce the concept of the shadow ∂G of a collection G of ordered graphs, and prove the following, simple-sounding statement: if n∈N is sufficiently large, |V(G)|=n for each G∈G, and |G|<n, then |∂G|?|G|. As a consequence, we substantially strengthen a result of Balogh, Bollobás and Morris on hereditary properties of ordered graphs: we show that if P is such a property, and |Pk|<k for some sufficiently large k∈N, then |Pn| is decreasing for k?n<∞.