Search

The k‐ deck of a graph is its multiset of subgraphs induced by k vertices; we study what can be deduced about a graph from its k‐deck. We strengthen a result of Manvel by proving for ℓ∈N that when n is large enough (n>2ℓ(ℓ+1)2 suffices), the (n−ℓ)‐deck determines whether an n‐vertex graph is connected (n≥25 suffices when ℓ=3, and n≤2l cannot suffice). The reconstructibilityρ(G) of a graph G with n vertices is the largest ℓ such that G is determined by its (n−ℓ)‐deck. We generalize a result of Bollobás by showing ρ(G)≥(1−o(1))n∕2 for almost all graphs. As an upper bound on minρ(G), we have ρ(Cn)=⌈n∕2⌉=ρ(Pn)+1. More generally, we compute ρ(G) whenever Δ(G)=2, which involves extending a result of Stanley. Finally, we show that a complete r‐partite graph is reconstructible from its (r+1)‐deck. [ABSTRACT FROM AUTHOR]

Given a family [ABSTRACT FROM AUTHOR]

Given a graph F, a graph G is uniquely F- saturated if F is not a subgraph of G and adding any edge of the complement to G completes exactly one copy of F. In this article, we study uniquely [ABSTRACT FROM AUTHOR]

A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. A result of Broersma from 1988 implies that if G is an n-vertex k-connected graph and [ABSTRACT FROM AUTHOR]

We seek the maximum number of colors in an edge-coloring of the complete graph [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

We define the A4- structure of a graph G to be the 4-uniform hypergraph on the vertex set of G whose edges are the vertex subsets inducing 2 K2, C4, or P4. We show that perfection of a graph is determined by its A4-structure. We relate the A4-structure to the canonical decomposition of a graph as defined by Tyshkevich [Discrete Math 220 (2000) 201-238]; for example, a graph is indecomposable if and only if its A4-structure is connected. We also characterize the graphs having the same A4-structure as a split graph. [ABSTRACT FROM AUTHOR]

Pósa proved that if G is an n-vertex graph in which any two nonadjacent vertices have degree-sum at least n + k, then G has a spanning cycle containing any specified family of disjoint paths with a total of k edges. We consider the analogous problem for a bipartite graph G with n vertices and parts of equal size. Let F be a subgraph of G whose components are nontrivial paths. Let k be the number of edges in F, and let t1 and t2 be the numbers of components of F having odd and even length, respectively. We prove that G has a spanning cycle containing F if any two nonadjacent vertices in opposite partite sets have degree-sum at least n/2 + τ( F), where τ( F) = ⌈ k/2⌉ + ɛ (here ɛ = 1 if t1 = 0 or if ( t1, t2)∈{(1, 0), (2, 0)}, and ɛ = 0 otherwise). We show also that this threshold on the degree-sum is sharp when n>3 k. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:1-17, 2012 [ABSTRACT FROM AUTHOR]