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 .     

Dissections, Hom-complexes and the Cayley trick

We show that certain canonical realizations of the complexes Hom(G,H) and Hom₊(G,H) of (partial) graph homomorphisms studied by Babson and Kozlov are, in fact, instances of the polyhedral Cayley trick. For G a complete graph, we then characterize when a canonical projection of these complexes is itself again a complex, and exhibit several well-known objects that arise as cells or subcomplexes of such projected Hom-complexes: the dissections of a convex polygon into k-gons, Postnikov's generalized permutohedra, staircase triangulations, the complex dual to the lower faces of a cyclic polytope, and the graph of weak compositions of an integer into a fixed number of summands.     

Cube intersection concepts in median graphs

In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Q_k(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices H_x and H_y in Q_k(G) are adjacent whenever the intersection H_x∩H_y contains a subgraph isomorphic to Q_k. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations.     

Vertex Coverings by Coloured Induced Graphs—Frames and Umbrellas

A graph G homogeneously embeds in a graph H if for every vertex x of G and every vertex y of H there is an induced copy of G in H with x at y. The graph G uniformly embeds in H if for every vertex y of H there is an induced copy of G in H containing y. For positive integer k, let f_k(G) (respectively, g_k(G)) be the minimum order of a graph H whose edges can be k-coloured such that for each colour, G homogeneously embeds (respectively, uniformly embeds) in the graph given by V(H) and the edges of that colour. We investigate the values f₂(G) and g₂(G) for special classes of G, in particular when G is a star or balanced complete bipartite graph. Then we investigate f_k(G) and g_k(G) when k ≥ 3 and G is a complete graph.     

Edge decompositions into two kinds of graphs

Let H be an arbitrary graph and let K_1,2 be the 2-edge star. By a {K_1,2,H}-decomposition of a graph G we mean a partition of the edge set of G into subsets inducing subgraphs isomorphic to K_1,2 or H. Let J be an arbitrary connected graph of odd size. We show that the problem to decide if an instance graph G has a {K_1,2,H}-decomposition is NP-complete if H has a component of an odd size and H≠pK_1,2∪qJ, where pK_1,2∪qJ is the disjoint union of p copies of K_1,2 and q copies of J. Moreover, we prove polynomiality of this problem for H=qJ.     

Edge-colorings avoiding rainbow and monochromatic subgraphs

For two graphs G and H, let the mixed anti-Ramsey numbers, maxR(n;G,H), (minR(n;G,H)) be the maximum (minimum) number of colors used in an edge-coloring of a complete graph with n vertices having no monochromatic subgraph isomorphic to G and no totally multicolored (rainbow) subgraph isomorphic to H. These two numbers generalize the classical anti-Ramsey and Ramsey numbers, respectively.We show that maxR(n;G,H), in most cases, can be expressed in terms of vertex arboricity of H and it does not depend on the graph G. In particular, we determine maxR(n;G,H) asymptotically for all graphs G and H, where G is not a star and H has vertex arboricity at least 3.In studying minR(n;G,H) we primarily concentrate on the case when G=H=K₃. We find minR(n;K₃,K₃) exactly, as well as all extremal colorings. Among others, by investigating minR(n;K_t,K₃), we show that if an edge-coloring of K_n in k colors has no monochromatic K_t and no rainbow triangle, then n?2^kt2.     

On a conjecture of Meyniel

A graph G is said to be very strongly perfect if for each induced subgraph H of G, each vertex of H belongs to a stable set that meets all maximal cliques of H. Meyniel proved that a graph is perfect if each of its odd cycles with at least five vertices contains at least two chords. Nowadays, such a graph is called a Meyniel graph. We prove that, as conjectured by Meyniel, a graph is very strongly perfect if and only if it is a Meyniel graph. We also design a polynomial-time algorithm which, given a Meyniel graph G and a vertex x of G, finds a stable set that contains x and meets all maximal cliques of G. We shall convert this algorithm into another polynomial-time algorithm which, given a Meyniel graph G, finds an optimal coloring of G, and a largest clique of G. Finally, we shall establish another property, related to perfection, of Meyniel graphs.     

H-domination in graphs

Let H be some fixed graph of order p. For a given graph G and vertex set S⊆V(G), we say that S is H-decomposable if S can be partitioned as S=S₁∪S₂∪?∪S_j where, for each of the disjoint subsets S_i, with 1?i?j, we have |S_i|=p and H is a spanning subgraph of 〈S_i〉, the subgraph induced by S_i. We define the H-domination number of G, denoted as γ_H(G), to be the minimum cardinality of an H-decomposable dominating set S. If no such dominating set exists, we write γ_H(G)=∞. We show that the associated H-domination decision problem is NP-complete for every choice of H. Bounds are shown for γ_H(G). We show, in particular, that if δ(G)?2, then γ_P3(G)?3γ(G). Also, if γ_P3(G)=3γ(G), then every γ(G)-set is an efficient dominating set.     

Two-factors in orientated graphs with forbidden transitions

The instance of the problem of finding 2-factors in an orientated graph with forbidden transitions consists of an orientated graph G and for each vertex v of G, a graph H_v of allowed transitions at v. Vertices of the graph H_v are the edges incident to v. An orientated 2-factor F of G is called legal if all the transitions are allowed, i.e. for every vertex v, the two edges of F adjacent to it form an edge in H_v. Deciding whether a legal 2-factor exists in G is NP-complete in general. We investigate the case when the graphs of allowed transitions are taken from some fixed class C. We provide an exact characterization of classes C so that the problem is NP-complete. In particular, we prove a dichotomy for this problem, i.e. that for any class C it is either polynomial or NP-complete.     

A note on cycle spectra of line graphs

We show that line graphs G=L(H) with σ₂(G)≥7 contain cycles of all lengths k, 2rad(H)+1≤k≤c(G). This implies that every line graph of such a graph with 2rad(H)≥Δ(H) is subpancyclic, improving a recent result of Xiong and Li. The bound on σ₂(G) is best possible.     

Main Q-eigenvalues and generalized Q-cospectrality of graphs

Let Q ^G denote the signless Laplacian matrix of a graph G. An eigenvalue μ of Q ^G is said to be a main Q-eigenvalue of G if μ has an eigenvector which is not orthogonal to an all-ones vector e. We give some basic properties of main Q-eigenvalues. For a graph G of order n, G is called Q-controllable if G has n distinct main Q-eigenvalues. We show that a graph H is generalized Q-cospectral with a Q-controllable G if and only if H is Q-controllable and there exists a unique rational orthogonal matrix R such that R _e = e, Q _H = R ^? Q _G R.     

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].     

Building blocks for the variety of absolute retracts

Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism r:H→G such that r(x)=x for all vertices x in G. We call G a retract of H. While deciding the existence of a retraction to a fixed graph G is NP-complete in general, necessary and sufficient conditions have been provided for certain classes of graphs in terms of holes, see for example Hell and Rival.For any integer k?2 we describe a collection of graphs that generate the variety AR_k of graphs G with the property that G is a retract of H whenever G is a subgraph of H and no hole in G of size at most k is filled by a vertex of H. We also prove that AR_k⊂NUF_k+1, where NUF_k+1 is the variety of graphs that admit a near unanimity function of arity k+1.     

Netlike partial cubes II. Retracts and netlike subgraphs

First we show that the class of netlike partial cubes is closed under retracts. Then we prove, for a subgraph G of a netlike partial cube H, the equivalence of the assertions: G is a netlike subgraph of H; G is a hom-retract of H; G is a retract of H. Finally we show that a non-trivial netlike partial cube G, which is a retract of some bipartite graph H, is also a hom-retract of H if and only if G contains at most one convex cycle of length greater than 4.     

Backbone colorings of graphs with bounded degree

We study backbone colorings, a variation on classical vertex colorings: Given a graph G and a subgraph H of G (the backbone of G), a backbone coloring for G and H is a proper vertex k-coloring of G in which the colors assigned to adjacent vertices in H differ by at least 2. The minimal k∈N for which such a coloring exists is called the backbone chromatic number of G. We show that for a graph G of maximum degree Δ where the backbone graph is a d-degenerated subgraph of G, the backbone chromatic number is at most Δ+d+1 and moreover, in the case when the backbone graph being a matching we prove that the backbone chromatic number is at most Δ+1. We also present examples where these bounds are attained.Finally, the asymptotic behavior of the backbone chromatic number is studied regarding the degrees of G and H. We prove for any sparse graph G that if the maximum degree of a backbone graph is small compared to the maximum degree of G, then the backbone chromatic number is at most .     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

On the characteristic polynomial of a special class of graphs and spectra of balanced trees

Let H be a simple graph with n vertices and G be a sequence of n rooted graphs G₁,G₂,…,G_n. Godsil and McKay [C.D. Godsil, B.D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978) 21-28] defined the rooted product H(G), of H by G by identifying the root vertex of G_i with the ith vertex of H, and determined the characteristic polynomial of H(G). In this paper we prove a general result on the determinants of some special matrices and, as a corollary, determine the characteristic polynomials of adjacency and Laplacian matrices of H(G).Rojo and Soto [O. Rojo, R. Soto, The spectra of the adjacency matrix and Laplacian matrix for some balanced trees, Linear Algebra Appl. 403 (2005) 97-117] computed the characteristic polynomials and the spectrum of adjacency and Laplacian matrices of a class of balanced trees. As an application of our results, we obtain their conclusions by a simple method.     

Groups with the same non-commuting graph

The non-commuting graph Γ_G of a non-abelian group G is defined as follows. The vertex set of Γ_G is G−Z(G) where Z(G) denotes the center of G and two vertices x and y are adjacent if and only if xy≠yx. It has been conjectured that if G and H are two non-abelian finite groups such that Γ_G≅Γ_H, then |G|=|H| and moreover in the case that H is a simple group this implies G≅H. In this paper, our aim is to prove the first part of the conjecture for all the finite non-abelian simple groups H. Then for certain simple groups H, we show that the graph isomorphism Γ_G≅Γ_H implies G≅H.     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.     

Homotopy groups of Hom complexes of graphs

The notion of ×-homotopy from [Anton Dochtermann, Hom complexes and homotopy theory in the category of graphs, European J. Combin., in press] is investigated in the context of the category of pointed graphs. The main result is a long exact sequence that relates the higher homotopy groups of the space Hom_∗(G,H) with the homotopy groups of Hom_∗(G,HI). Here Hom_∗(G,H) is a space which parameterizes pointed graph maps from G to H (a pointed version of the usual Hom complex), and HI is the graph of based paths in H. As a corollary it is shown that πi(Hom_∗(G,H))≅_×[G,ΩiH], where ΩH is the graph of based closed paths in H and _×[G,K] is the set of ×-homotopy classes of pointed graph maps from G to K. This is similar in spirit to the results of [Eric Babson, Hélène Barcelo, Mark de Longueville, Reinhard Laubenbacher, Homotopy theory of graphs, J. Algebraic Combin. 24 (1) (2006) 31-44], where the authors seek a space whose homotopy groups encode a similarly defined homotopy theory for graphs. The categorical connections to those constructions are discussed.