Ramsey-minimal graphs for star-forests

It is shown that if G and H are star-forests with no single edge stars, then (G, H) is Ramsey-finite if and only if both G and H are single stars with an odd number of edges. Further (S_m ∪kS₁, S_n ∪tS₁) is Ramsey-finite when m and n are odd, where S_i denotes a star with i edges. In general, for G and H star-forests, (G∪kS₁, H∪tS₁) can be shown to be Ramsey-finite or Ramsey-infinite depending on the choice of G, H, k, and l with the general case unsettled. This disproves the conjecture given in [2] where it is suggested that the pair of graphs (L, M) is Ramsey-finite if and only if (1) either L or M is a matching, or (2) both L and M are star-forests of the type S_m ∪kS₁, m odd and k ? 0.     

Weak cycle partition involving degree sum conditions

Let G be a graph of order n and k a positive integer. A set of subgraphs H={H₁,H₂,…,H_k} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H₁,…,H_k are vertex disjoint subgraphs of G such that and for all i, 1≤i≤k, H_i is a cycle or K₁ or K₂. If, in addition, for all i, 1≤i≤k, H_i is a cycle or K₁, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G has a k-DCP, except G≅C₅ and k=2. We prove that if G is a graph of order n≥k+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K₂∪K_n−2∪{e}, where e is an edge connecting V(K₂) and V(K_n−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}.     

The Erd?s-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces

We prove that for any orientable surface S and any non-negative integer k, there exists an integer f_S(k) such that every graph G embeddable in S has either k vertex-disjoint odd cycles or a vertex set A of cardinality at most f_S(k) such that G-A is bipartite. Such a property is called the Erd?s-Pósa property for odd cycles. We also show its edge version. As Reed [Mangoes and blueberries, Combinatorica 19 (1999) 267-296] pointed out, the Erd?s-Pósa property for odd cycles do not hold for all non-orientable surfaces.     

On a property of minimal triangulations

A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P₅, or H has two connected components and is an induced subgraph of 2P₃.This completes the results of Parra and Scheffler, who have shown that MT holds for H=P_k, the path on k vertices, if and only if k?5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171-188], and of Meister, who proved that MT holds for ?P₂, ? copies of a P₂, if and only if ??2 [D. Meister, A complete characterisation of minimal triangulations of 2K₂-free graphs, Discrete Mathematics 306 (2006) 3327-3333].     

On some three color Ramsey numbers for paths and cycles

For given graphs G₁,G₂,…,G_k, k≥2, the multicolor Ramsey number, denoted by R(G₁,G₂,…,G_k), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of G_i colored with i, for some 1≤i≤k. Let P_k (resp. C_k) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(P_i,P_k,C_m) for odd m, k≥m≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P₃,P_k,C₄) for all integers k≥3.     

Some remarks on the odd hadwiger’s conjecture

We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l ? 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K _k -minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K _k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) ? 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

On the odd harmonious graphs with applications

The necessary conditions for the existence of odd harmonious labelling of graph are obtained. A cycle C _n is odd harmonious if and only if n≡0 (mod 4). A complete graph K _n is odd harmonious if and only if n=2. A complete k-partite graph K(n ₁,n ₂,…,n _k ) is odd harmonious if and only if k=2. A windmill graph K _n ^t is odd harmonious if and only if n=2. The construction ways of odd harmonious graph are given. We prove that the graph ∨ _i=1 ⁿ G _i , the graph G(+r ₁,+r ₂,…,+r _p ), the graph $\bar{K_{m}}+_{0}P_{n}+_{e}\bar{K_{t}}$ , the graph G∪(X+∪ _k=1 ⁿ Y _k ), some trees and the product graph P _m ×P _n etc. are odd harmonious. The odd harmoniousness of graph can be used to solve undetermined equation.     

Finite 2-groups whose length of chain of nonnormal subgroups is at most 2

Assume that G is a finite non-Dedekind p-group. D. S. Passman introduced the following concept: we say that H₁ < H₂ < ? < H_k is a chain of nonnormal subgroups of G if each H_i ? G and if |H_i : H_i?1| = p for i = 2, 3,…, k. k is called the length of the chain. chn(G) denotes the maximum of the lengths of the chains of nonnormal subgroups of G. In this paper, finite 2-groups G with chn(G) ? 2 are completely classified up to isomorphism.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

On strong joins and pushout of combinatorial geometries

The strong join of two geometries G and H relative to a common subgeometry is a geometry on the point set (G ? x)∪(H ? x)∪x, the closed sets k of which have the property that k ∩ G is closed in the geometry G and k ∩ H is closed in the geometry H. The strong join does not always exist, but if x is a modular flat of G (or H) it does exist. This was proved by Brylawski in his interesting paper “Modular constructions for combinatorial geometries” [1]. We shall show that if one wants the strong join to exist for all H which contain x as a subgeometry, then x must be a modular flat of G. We also show that the concepts strong join and injective pushout defined in [1] are identical.     

Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.     

Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

Operator norm localization property of relative hyperbolic group and graph of groups

In this article we study the spaces which have operator norm localization property. We prove that a finitely generated group Γ which is strongly hyperbolic with respect to a collection of finitely generated subgroups {H₁,…,Hn} has operator norm localization property if and only if each Hi, i=1,2,…,n, has operator norm localization property. Furthermore we prove the following result. Let π be the fundamental group of a connected finite graph of groups with finitely generated vertex groups GP. If GP has operator norm localization property for all vertices P then π has operator norm localization property.     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

On H-Linked Graphs

For a fixed multigraph H, possibly containing loops, with V(H)={h₁, . . . , h_k}, we say a graph G is H-linked if for every choice of k vertices v₁, . . . , v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). This notion clearly generalizes the concept of k-linked graphs (as well as other properties). In this paper we determine, for a connected multigraph H and for any sufficiently large graph G, a sharp lower bound on δ(G) (depending upon H) such that G is H-linked.     

Long Cycles Generate the Cycle Space of a Graph

Let G be a 2-connected graph in which the degree of every vertex is at least d. We prove that the cycles of length at least d + 1 generate the cycle space of G, unless G ≌ K_d+1 and d is odd. As a corollary, we deduce that the cycles of length at least d + 1 generate the subspace of even cycles in G. We also establish the existence of odd cycles of length at least d + 1 in the case when G is not bipartite.A second result states: if G is 2-connected with chromatic number at least k, then the cycles of length at least k generate the cycle space of G, unless G ≌ K_k and k is even. Similar corollaries follow, among them a stronger version of a theorem of Erdös and Hajnal.     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

On H‐immersions

For a fixed multigraph H, possibly containing loops, with V(H) = {h₁,…, h_k}, we say a graph G is H‐linked if for every choice of k vertices v₁,…,v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). An H‐immersion in G is similar except that the paths in G, playing the role of the edges of H, are only required to be edge disjoint. In this article, we extend the notion of an H‐linked graph by determining minimum degree conditions for a graph G to contain an H‐immersion with a bounded number of vertex repetitions on any choice of k vertices. In particular, we extend results found in [2,3,5]. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 245–254, 2008     

Graph minors. I. Excluding a forest

The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG₁,…,G_r each of which has at mostk + 1 vertices, by identifying some vertices ofG_i pairwise with some ofG_i+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width?k. This, together with results of other papers, yields a “good” algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite.