Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.     

Forwarding and optical indices of a graph

Motivated by wavelength-assignment problems for all-to-all traffic in optical networks, we study graph parameters related to sets of paths connecting all pairs of vertices. We consider sets of both undirected and directed paths, under minimisation criteria known as edge congestion and wavelength count; this gives rise to four parameters of a graph G: its edge forwarding index π(G), arc forwarding index , undirected optical index , and directed optical index .In the paper we address two long-standing open problems: whether the equality holds for all graphs, and whether indices π(G) and are hard to compute. For the first problem, we give an example of a family of planar graphs {G_k} such that . For the second problem, we show that determining either π(G) or is NP-hard.     

Localization and duality in topology and modular representation theory

We develop a duality theory for localizations in the context of ring spectra in algebraic topology. We apply this to prove a theorem in the modular representation theory of finite groups.Let G be a finite group and k be an algebraically closed field of characteristic p. If p is a homogeneous nonmaximal prime ideal in H^∗(G,k), then there is an idempotent module κ_p which picks out the layer of the stable module category corresponding to p, and which was used by Benson, Carlson and Rickard [D.J. Benson, J.F. Carlson, J. Rickard, Thick subcategories of the stable module category, Fund. Math. 153 (1997) 59-80] in their development of varieties for infinitely generated kG-modules. Our main theorem states that the Tate cohomology is a shift of the injective hull of H^∗(G,k)/p as a graded H^∗(G,k)-module. Since κ_p can be constructed using a version of the stable Koszul complex, this can be viewed as a statement of localized Gorenstein duality in modular representation theory. Various consequences of this theorem are given, including the statement that the stable endomorphism ring of the module κ_p is the p-completion of cohomology , and the statement that κ_p is a pure injective kG-module.In the course of proving the theorem, we further develop the framework introduced by Dwyer, Greenlees and Iyengar [W.G. Dwyer, J.P.C. Greenlees, S. Iyengar, Duality in algebra and topology, Adv. Math. 200 (2006) 357-402] for translating between the unbounded derived categories and . We also construct a functor to the full stable module category, which extends the usual functor and which preserves Tate cohomology. The main theorem is formulated and proved in , and then translated to and finally to .The main theorem in can be viewed as stating that a version of Gorenstein duality holds after localizing at a prime ideal in H^∗(BG;k). This version of the theorem holds more generally for a compact Lie group satisfying a mild orientation condition. This duality lies behind the local cohomology spectral sequence of Greenlees and Lyubeznik for localizations of H^∗(BG;k).In a companion paper [D.J. Benson, Idempotent kG-modules with injective cohomology, J. Pure Appl. Algebra 212 (7) (2008) 1744-1746], a more recent and shorter proof of the main theorem is given. The more recent proof seems less natural, and does not say anything about localization of the Gorenstein condition for compact Lie groups.     

Packing directed cycles efficiently

Let G be a simple digraph. The dicycle packing number of G, denoted ν_c(G), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set C of directed cycles in G to R₊ is a fractional dicycle packing of G if ∑_e∈C∈Cψ(C)?w(e) for each e∈E(G). The fractional dicycle packing number, denoted , is the maximum value of ∑_C∈Cψ(C) taken over all fractional dicycle packings ψ. In case w≡1 we denote the latter parameter by .Our main result is that where n=|V(G)|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν_c(G)-o(n²) in randomized polynomial time. Since computing ν_c(G) is an NP-Hard problem, and since almost all digraphs have ν_c(G)=Θ(n²) our result is a FPTAS for computing ν_c(G) for almost all digraphs.The result uses as its main lemma a much more general result. Let F be any fixed family of oriented graphs. For an oriented graph G, let ν_F(G) denote the maximum number of arc-disjoint copies of elements of F that can be found in G, and let denote the fractional relaxation. Then, . This lemma uses the recently discovered directed regularity lemma as its main tool.It is well known that can be computed in polynomial time by considering the dual problem. We present a polynomial algorithm that finds an optimal fractional dicycle packing. Our algorithm consists of a solution to a simple linear program and some minor modifications, and avoids using the ellipsoid method. In fact, the algorithm shows that a maximum fractional dicycle packing with at most O(n²) dicycles receiving nonzero weight can be found in polynomial time.     

Distance irredundance and connected domination numbers of a graph

Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γ_k(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number ir_k(G). The authors prove that if an ir_k-set X is a k-independent set of G, then , and that for k?2, if ir_k(G)=1, if ir_k(G) is odd, and if ir_k(G) is even, which generalize some known results.     

The connectivity of a graph and its complement

Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let be the complement of G.In this article we prove that either λ(G)=δ(G) or . In addition, we present the Nordhaus-Gaddum type result . A family of examples will show that this inequality is best possible.     

Convergence theorems for fixed points of uniformly continuous generalized Φ-hemi-contractive mappings

Let E be a real normed linear space, K be a nonempty subset of E and be a uniformly continuous generalized Φ-hemi-contractive mapping, i.e., , and there exist x^∗∈F(T) and a strictly increasing function , Φ(0)=0 such that for all x∈K, there exists j(x−x^∗)∈J(x−x^∗) such that

〈Tx−x^∗,j(x−x^∗)〉?‖x−x^∗‖2−Φ(‖x−x^∗‖).     

On the ideal structure of some Banach algebras related to convolution operators on L(G)

Let G be a locally compact group and let p∈(1,∞). Let be any of the Banach spaces C_δ,p(G), PF_p(G), M_p(G), AP_p(G), WAP_p(G), UC_p(G), PM_p(G), of convolution operators on L^p(G). It is shown that PF_p(G)′ can be isometrically embedded into UC_p(G)′. The structure of maximal regular ideals of (and of MA_p(G)″, B_p(G)″, W_p(G)″) is studied. Among other things it is shown that every maximal regular left (right, two sided) ideal in is either dense or is the annihilator of a unique element in the spectrum of A_p(G). Minimal ideals of is also studied. It is shown that a left ideal M in is minimal if and only if , where Ψ is either a right annihilator of or is a topologically x-invariant element (for some x∈G). Some results on minimal right ideals are also given.     

Distance-two labellings of Hamming graphs

Let j≥k≥0 be integers. An ?-L(j,k)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…,?} such that |?(u)−?(v)|≥j if u,v are adjacent and |?(u)−?(v)|≥k if they are distance two apart. Let λ_j,k(G) be the smallest integer ? such that G admits an ?-L(j,k)-labelling. Define to be the smallest ? if G admits an ?-L(j,k)-labelling with ?(V)={0,1,2,…,?} and ∞ otherwise. An ?-cyclic L(j,k)-labelling is a mapping ?:V→Z_? such that |?(u)−?(v)|_?≥j if u,v are adjacent and |?(u)−?(v)|_?≥k if they are distance two apart, where |x|_?=min{x,?−x} for x between 0 and ?. Let σ_j,k(G) be the smallest ?−1 of such a labelling, and define similarly to . We determine λ_2,0, , σ_2,0 and for all Hamming graphs K_q1□K_q2□?□K_qd (d≥2, q₁≥q₂≥?≥q_d≥2) and give optimal labellings, with the only exception being for q≥4. We also prove the following “sandwich theorem”: If q₁ is sufficiently large then for any graph G between K_q1□K_q2 and K_q1□K_q2□?□K_qd, and moreover we give a labelling which is optimal for these eight invariants simultaneously.