Problems

The problem COMPUTECHARBINARY is GapP-complete under many-one reductions.

If G=(V, E) is self-complementary and vertice-transitive,then ρ^⊥(G)=⌈ n/2 ⌉

Suppose that the graphs Γ_1 and Γ_2 have the same refined spectra. Are their complements cospectral?

Give a sharp upper bound on γ(X(G)) in terms of γ(G) for any connected graph G with δ(G) ≥ 2, where γ denotes the domination number.

Let \alpha, \beta and \mu be partitions of the same size. The generating function \sum_{N \ge 0} L_{N\alpha,N\beta}^{N\mu}(q) t^N is a rational function of q and t.

Charactrize all graphs G which diam(G)=2 and diam(D_{2}(G))=2 or 3.

Do there exist polynomials f_{1}(\zeta),f_{2}(\zeta),f_{3}(\zeta) and f_{4}(\zeta) in \zeta of order 6 , given as in (15), satisfying (16) and (17), such that f_{1}(1)=0,\quad f_{2}(1)^{2}=f_{3}(1)^{2}=f_{4}(1)^{2}=3^{2}?

It meets ρ^⊥(G)>ρ^⊥(V_c) if it meets the following: - ρ^⊥(V_c)>ρ^⊥(A) - ρ^⊥(V_c)>ρ^⊥(B) - ρ^⊥(V_c)≤ ρ^⊥(A)+ρ^⊥(B)

Note that the divisibility conditions in (22) should be equivalent to those in (23) if a t-(n,k,λ) exists. It is open if they are equivalent.

No two non-isomorphic H-shape trees are L-cospectral.

if n is odd then there exist isometric embeddings of \frac{1}{2}H_{n} in the half-spin Grassmann graphs of \Pi whose images are not apartments.

In fact, what can be said (in general) about the connected components of these graphs: are they all paths or cliques ?

If ζ(α) = ζ(β), are α and β necessarily related by switching?

Let S be the parameter matrix of a k-transversal in a d-uniform r-regular hyper graph G. Then the characteristic polynomial of S is φ(λ)=λ^d-2∏_i=j^d(λ-ξ^jkr), where ξ is a d-th primitive root of unity.

Characterize the nontrivial lexicographic product graphs that are well-totally-dominated.