Problems

Conjecture 1. Given an undirected connected graph G. We consider v an extremum of the Fiedler vector of the graph G.\tilde{G} is the graph obtained from G and v as in Proposition 1. Then for all x>0 the Fiedler vector \Phi(x,\cdot) of…

Is it true that for every nonnegative integer k, there exists a connected hypergraph H satisfying φ_ST(H) − κ_ST(H) + 1 = k?

Let G be a 2-connected bipartite graph with sides A and B satisfying |N^2(X)| ≥ |X| for every X ⊆ A of size at least 3. For every X ⊆ A, |X| ≥ 3, there is a cycle C_X in G such that V(C_X) ∩ A = X.

Let G be a fuzzy graph. Then, (1) s(G) ≤ 2Δ(G) + 1, (2) for every integer k ≥ 2, there exists a fuzzy graph G_k such that k-1 ≤ Δ(G_k) and s(G_k) = Δ(G_k) + k.

Let M(n) denote the absolute value of the Möbius function μ[1,W_n]=μ[1,M_n] . Then for n>50 we have M(2n)=n^2⇔ n+1 isprimeandn ≡ 0(bmod6)M(2n)=n^2-1 ⇔ n+1 isprimeandn ≡ 4(bmod6)M(2n+1)=n^2-n ⇔ n+1 isprimeandn ≡ 0(bmod6)M(2n+1)=n^2-n-1 ⇔…

Let G be a connected graph of order n. If 1/2<α<1 , then λ_n(A_α(G))≥ λ_n(A_α(K_1,n-1)),the equality holds if and only if G ≅ K_1,n-1 .

First of all, is it possible to sharpen Theorem 1 to the assertion that ‘colex is best’: if A ⊂ [n]^(3), and C is the set of the first |A| elements of [n]^(3) in the colex order, then must we have |VA| ≥ |VC|?

Suppose that G ∈ G^r . Is λ_min^(p)(G) continuously differentiable for p>r ? Is λ_min^(p)(G) continuously differentiable for p \ne k, k=2, ..., r ?

It remains open whether enumeration on chordal graphs can be improved further, so we hereby pose it as an open problem, or whether one can obtain a higher lower bound, which might also be a gap-improvement on general graphs.

Conjecture 18. The top subsegment of the n-core (n=12,14,16, ...) is μ_n/4=μ_n-4(A-3× 2^n-7)⊕ μ_(n-2)/4(A)^3 , where A=M_n-1+2^n-3 is the senior term of the n-core.

For which graphs H does there exist an H' such that π_G^(H') determines π_G^(H) for every graph G?

Suppose we revised our definition of an s-partition so that each part was required to be 2-edge connected, except the small part. What degree of edge connectivity would be required to ensure the existence of an s-partition (if such a…

Give a bound R depending on some invariants of the simplicial complex Δ such that for r ≥R the polynomial h^sd^r(Δ)(t) has only real roots.

The question of finding necessary and sufficient conditions for this to happen is to the best of the author's knowledge an open problem.

Conjecture 3.6. Let k ≥2 be an integer, G=(V,E) be a graph, and r:V \to Z_{+} such that r(V) ≥k+1. Then G has a k-connected r-detachment if and only if (a) G is k-edge connected, (b) d(v) ≥k r(v) for all v \in V , (c) G-y has a…

We conjecture that ex_v(vecV_r, vecQ_n) = 2^n-1 + Θ(n^r-2) holds for every r ≥ 3.

Let f(n) be the largest integer for which there is a C_4 free graph of n vertices every vertex of which has degree ≥ f(n). Is it true that f(n+1) ≥ f(n)?

Let d ≥ 1. Then for any 0 ≤ ℓ < k ≤ d - ℓ - 1, does there exist an infinite family P_1, P_2, … of integral convex polytopes of dimension d such that for each P_i and P_j with i ≠ j, the followings are satisfied: For t = 1, …, k, we have…

If r = o(n) holds, then the order of magnitude of M(n, r) is Θ(n).

While it is important to note that twisted subgroups need not be subgroups (e.g., there are small counterexamples in non-abelian groups of order 27 and 75), it could perhaps be the case that L(G) = {|H| : H \subsetneq G} (and thus, our…