Arbitrarily vertex decomposable suns with few rays

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,…,n_k) of positive integers with n₁+?+n_k=n, there exists a partition (V₁,…,V_k) of the vertex set of G such that V_i induces a connected subgraph of order n_i, for all i=1,…,k. A sun with r rays is a unicyclic graph obtained by adding r hanging edges to r distinct vertices of a cycle. We characterize all arbitrarily vertex decomposable suns with at most three rays. We also provide a list of all on-line arbitrarily vertex decomposable suns with any number of rays.     

Dense Arbitrarily Vertex Decomposable Graphs

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n ₁, . . . , n _k ) of positive integers such that n ₁ + · · · + n _k = n there exists a partition (V ₁, . . . , V _k ) of the vertex set of G such that for each ${i \in \{1,\ldots,k\}}$ , V _i induces a connected subgraph of G on n _i vertices. The main result of the paper reads as follows. Suppose that G is a connected graph on n ≥ 20 vertices that admits a perfect matching or a matching omitting exactly one vertex. If the degree sum of any pair of nonadjacent vertices is at least n ? 5, then G is arbitrarily vertex decomposable. We also describe 2-connected arbitrarily vertex decomposable graphs that satisfy a similar degree sum condition.     

A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.     

On the shape of decomposable trees

A n-vertex graph is said to be decomposable if, for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. The aim of the paper is to study the homeomorphism classes of decomposable trees. More precisely, we show that homeomorphism classes containing decomposable trees with an arbitrarily large minimal distance between all pairs of distinct vertices of degree different from 2, is exactly the set of combs.     

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.     

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 .     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

A multiplicative inequality for vertex Folkman numbers

Let G be a graph and a₁,…,a_r be positive integers. The symbol G→(a₁,…,a_r) denotes that in every r-coloring of the vertex set V(G) there exists a monochromatic a_i-clique of color i for some i∈{1,…,r}. The vertex Folkman numbers F(a₁,…,a_r;q)=min{|V(G)|:G→(a₁,…,a_r) and K_q?G} are considered. Let a_i, b_i, c_i, i∈{1,…,r}, s, t be positive integers and c_i=a_ib_i, 1?a_i?s,1?b_i?t. Then we prove that

F(c₁,c₂,…,c_r;st+1)?F(a₁,a₂,…,a_r;s+1)F(b₁,b₂,…,b_r;t+1).     

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.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

Two new methods to obtain super vertex-magic total labelings of graphs

Let G=(V,E) be a finite non-empty graph, where V and E are the sets of vertices and edges of G, respectively, and |V|=n and |E|=e. A vertex-magic total labeling (VMTL) is a bijection λ from V∪E to the consecutive integers 1,2,…,n+e with the property that for every v∈V, , for some constant h. Such a labeling is super if λ(V)={1,2,…,n}. In this paper, two new methods to obtain super VMTLs of graphs are put forward. The first, from a graph G with some characteristics, provides a super VMTL to the graph kG graph composed by the disjoint unions of k copies of G, for a large number of values of k. The second, from a graph G₀ which admits a super VMTL; for instance, the graph kG, provides many super VMTLs for the graphs obtained from G₀ by means of the addition to it of various sets of edges.     

A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

Rose window graphs underlying rotary maps

Given natural numbers n≥3 and 1≤a,r≤n−1, the rose window graph R_n(a,r) is a quartic graph with vertex set {x_i∣i∈Z_n}∪{y_i∣i∈Z_n} and edge set {{x_i,x_i+1}∣i∈Z_n}∪{{y_i,y_i+r}∣i∈Z_n}∪{{x_i,y_i}∣i∈Z_n}∪{{x_i+a,y_i}∣i∈Z_n}. In this paper rotary maps on rose window graphs are considered. In particular, we answer the question posed in [S. Wilson, Rose window graphs, Ars Math. Contemp. 1 (2008), 7-19. http://amc.imfm.si/index.php/amc/issue/view/5] concerning which of these graphs underlie a rotary map.     

The rank-width of the square grid

Rank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of G is less than or equal to its branch-width.The n×nsquare grid, denoted by G_n,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}, where a vertex (x,y) is connected by an edge to a vertex (x^′,y^′) if and only if |x−x^′|+|y−y^′|=1.We prove that the rank-width of G_n,n is equal to n−1, thus solving an open problem of Oum.     

A generalization of interval edge-colorings of graphs

An edge-coloring of a graph G with colors 1,2,…,t is called an interval (t,1)-coloring if at least one edge of G is colored by i, i=1,2,…,t, and the colors of edges incident to each vertex of G are distinct and form an interval of integers with no more than one gap. In this paper we investigate some properties of interval (t,1)-colorings. We also determine exact values of the least and the greatest possible number of colors in such colorings for some families of graphs.     

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.     

Bandwidth theorem for random graphs

A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1,2,…,n, so that |i−j|?b whenever {i,j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, Δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most Δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1−1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H₀ which one can find in a spanning subgraph of G(n,p) with minimum degree (1−1/r+γ)np.     

Consecutive magic graphs

Let G be a graph of order n and size e. A vertex-magic total labeling is an assignment of the integers 1,2,…,n+e to the vertices and the edges of G, so that at each vertex, the vertex label and the labels on the edges incident at that vertex, add to a fixed constant, called the magic number of G. Such a labeling is a-vertex consecutive magic if the set of the labels of the vertices is {a+1,a+2,…,a+n}, and is b-edge consecutive magic if the set of labels of the edges is {b+1,b+2,…,b+e}. In this paper we prove that if an a-vertex consecutive magic graph has isolated vertices then the order and the size satisfy (n-1)²+n²=(2e+1)². Moreover, we show that every tree with even order is not a-vertex consecutive magic and, if a tree of odd order is a-vertex consecutive then a=n-1. Furthermore, we show that every a-vertex consecutive magic graph has minimum degree at least two if a=0, or both and 2a?e, and the minimum degree is at least three if both and 2a?e. Finally, we state analogous results for b-edge consecutive magic graphs.