Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V₁∪?∪V_r is called a balanced decomposition if V_i is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V₁∪?∪V_r with |V_i|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.     

A generalization of perfect graphs—i-perfect graphs

Let i be a positive integer. We generalize the chromatic number _X(G) of G and the clique number o(G) of G as follows: The i-chromatic number of G, denoted by _X(G), is the least number k for which G has a vertex partition V₁, V₂,…, V_k such that the clique number of the subgraph induced by each V_j, 1 ≤ j ≤ k, is at most i. The i-clique number, denoted by o_i(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly _X1(G) = _X(G) and o₁(G) = o(G). An induced subgraph G′ of G is an i-transversal iff o(G′) = i and o(G − G′) = o(G) − i. We generalize the notion of perfect graphs as follows: (1) A graph G is i-perfect iff _Xi(H) = o_i(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transversable iff either o(G) ≤ i or every induced subgraph H of G with o(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1-perfect graphs and perfectly 1-transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i ≥ 2. We also show that all planar graphs are i-perfect for every i ≥ 2 and perfectly i-transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle-free graphs are 2-perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i-perfect graphs and the recognition of perfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.     

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

We present results on partitioning the vertices of 2-edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every 2-edge-colored graph can be partitioned into at most 2α(G) monochromatic cycles, where α(G) denotes the independence number of G. Another direction, emerged recently from a conjecture of Schelp, is to consider colorings of graphs with given minimum degree. We prove that apart from o(|V (G)|) vertices, the vertex set of any 2-edge-colored graph G with minimum degree at least \(\tfrac{{(1 + \varepsilon )3|V(G)|}} {4}\) can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that \(\bar G\) does not contain a fixed bipartite graph H, we show that in every 2-edge-coloring of G, |V (G)| ? c(H) vertices can be covered by two vertex disjoint paths of different colors, where c(H) is a constant depending only on H. In particular, we prove that c(C ₄)=1, which is best possible.     

Comparing Zagreb indices for connected graphs

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M₂(G)/m≥M₁(G)/n, where M₁ and M₂ are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M₂/(m−1)>M₁/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.     

The cochromatic index of a graph

We discuss partitions of the edge set of a graph into subsets which are uniform in their internal relationships; i.e., the edges are independent, they are incident with a common vertex (a star), or three edges meet in a triangle. We define the cochromatic index z′(G) of G to be the minimum number of subsets into which the edge set of G can be partitioned so that the edges in any subset are either mutually adjacent or independent.Several bounds for z′(G) are discussed. For example, it is shown that δ(G) - 1 ? z′(G)? Δ(G) + 1, with the lower bound being attained only for a complete graph. Here δ(G) and Δ(G) denote the minimum and maximum degrees of G, respectively. The cochromatic index is also found for complete n-partite graphs.Given a graph G define a sequence of graphs G₀, G₁,…, G_k, with G₀=G and

, with k being the first value of i for which G_i is regular. Let φ_i(G) = |V(G) – V(G_i| + Δ (G_i) and setφ(G) = min_0?i?kφ_i(G). We show that φ(G) ? 1 ?z′(G)?φ(G) + 1. We then s that a graph G is of class A, B or C, if z′(G) = φ(G) ? 1, φ(G), orφ(G) + 1, respectively. Examples of graphs of each class are presented; in particular, it is shown that any bipartite graph belongs to class B.Finally, we show that if a, b and c are positive integers with a?b?c + 1 and a?c, then unless a = c = b - 1 = 1, there exists a graph G having δ(G) = a, Δ(G) =c, and z′(G) = b.     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.     

Caterpillar arboricity of planar graphs

We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets (E_i)_1?i?4 in such a way that G[E_i], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

A note on balanced bipartitions

A balanced bipartition of a graph G is a bipartition V₁ and V₂ of V(G) such that −1≤|V₁|−|V₂|≤1. Bollobás and Scott conjectured that if G is a graph with m edges and minimum degree at least 2 then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤m/3, where e(V_i) denotes the number of edges of G with both ends in V_i. In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if G is a graph with m edges and n vertices, and if the maximum degree Δ(G)=o(n) or the minimum degree δ(G)→∞, then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤(1+o(1))m/4, answering a question of Bollobás and Scott in the affirmative. We also provide a sharp lower bound on max{e(V₁,V₂):V₁,V₂ is a balanced bipartition of G}, in terms of size of a maximum matching, where e(V₁,V₂) denotes the number of edges between V₁ and V₂.     

Flow trees for vertex-capacitated networks

Given a graph G=(V,E) with a cost function , we want to represent all possible min-cut values between pairs of vertices i and j. We consider also the special case with an additive cost c where there are vertex capacities c(v)?0∀v∈V, and for a subset S⊆V, c(S)=∑_v∈Sc(v). We consider two variants of cuts: in the first one, separation, {i} and {j} are feasible cuts that disconnect i and j. In the second variant, vertex-cut, a cut-set that disconnects i from j does not include i or j. We consider both variants for undirected and directed graphs. We prove that there is a flow-tree for separations in undirected graphs. We also show that a compact representation does not exist for vertex-cuts in undirected graphs, even with additive costs. For directed graphs, a compact representation of the cut-values does not exist even with additive costs, for neither the separation nor the vertex-cut cases.     

Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges

A set of planar graphs {G₁(V,E₁),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,…,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K₅ or K3,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n⁴)-time algorithms to compute a SEFE.     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

A New Construction for Cohen–Macaulay Graphs

Let G be a finite simple graph on a vertex set V(G) = {x ₁₁,…, x _n1}. Also let m ₁,…, m _n  ≥ 2 be integers and G ₁,…, G _n be connected simple graphs on the vertex sets V(G _i ) = {x _i1,…, x _{im i} }. In this article, we provide necessary and sufficient conditions on G ₁,…, G _n for which the graph obtained by attaching the G _i to G is unmixed or vertex decomposable. Then we characterize Cohen–Macaulay and sequentially Cohen–Macaulay graphs obtained by attaching the cycle graphs or connected chordal graphs to arbitrary graphs.     

Eccentric sequences and eccentric sets in graphs

By a graph we mean a finite undirected connected graph of order p, p ? 2, with no loops or multiple edges. A finite non-decreasing sequence S: s₁, s₂, …, s_p, p ? 2, of positive integers is an eccentric sequence if there exists a graph G with vertex set V(G) = {v₁, v₂, …, v_p} such that for each i, 1 ? i ? p, s, is the eccentricity of v₁. A set S is an eccentric set if there exists a graph G such that the eccentricity ρ(v₁) is in S for every v₁ ? V(G), and every element of S is the eccentricity of some vertex in G. In this note we characterize eccentric sets, and we find the minimum order among all graphs whose eccentric set is a given set, to obtain a new necessary condition for a sequence to be eccentric. We also present some properties of graphs having preassigned eccentric sequences.     

Balanced judicious bipartitions of graphs

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if G is a graph with minimum degree of at least 2 then V(G) admits a balanced bipartition V₁, V₂ such that for each i, G has at most |E(G)|/3 edges with both ends in V_i. The minimum degree condition is necessary, and a result of B. Bollobás and A. D. Scott, J. Graph Theory 46 (2004), 131–143 shows that this conjecture holds for regular graphs G(i.e., when Δ(G)=δ(G)). We prove this conjecture for graphs G with \begin{eqnarray*}\Delta(G)\le\frac{7}{5}\delta(G)\end{eqnarray*}; hence, it holds for graphs ]ensuremathG with \begin{eqnarray*}\delta(G)\ge\frac{5}{7}|V(G)|\end{eqnarray*}. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 210–225, 2010     

The Erd?s-Lovász Tihany conjecture for quasi-line graphs

Erd?s and Lovász conjectured in 1968 that for every graph G with χ(G)>ω(G) and any two integers s,t≥2 with s+t=χ(G)+1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S])≥s and χ(G[T])≥t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.     

Two characterizations of interchange graphs of complete m-partite graphs

A graph G is m-partite if its points can be partitioned into m subsets V₁,…,V_m such that every line joins a point in V_i with a point in V_j, i ≠ j. A complete m-partite graph contains every line joining V_i with V_j. A complete graph K_p has every pair of its p points adjacent. The nth interchange graph I_n(G) of G is a graph whose points can be identified with the K_n+1's of G such that two points are adjacent whenever the corresponding K_n+1's have a K_n in common.Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete m-partite graphs for m ≥ 2.     

The number of vertices of degree 5 in a contraction-critically 5-connected graph

An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V₅(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {G_i} such that lim_i→∞|V₅(G_i)|/|V(G_i)|=1/2.