Fwd: ITCDM-2011_OpenProblems

[Belmannu Devadas Acharya]

Dear All,

I found one problem was missing from the previous list by my oversight. I am now giving below the revised list of open problems that I posed during the discussions that took place in the recently concluded Indo-Tiwanese Conference on Discrete Mathematics (ITCDM-2011), with some additional notes. 

1.  Characterize infinite graphs $G$ and $H$ such that their one-point concatenations are all isomorphic (B.D. Acharya:1975). [I have declared a prize money of Rs.5,000/- for a solution to this problem. For finite graphs and digraphs the solution was due to S.B. Rao who proved my 1972 conjecture that .]

2. Conjecture (B.D. Acharya: 1980): The "Super Prime Graph of order $n$", denoted $SP(n)$, whose vertex set is the set of consecutive integers $1, 2, \dots, n$ and the edge set is formed by joining every pair of distinct vertices $i$ and $j$ that are co-prime to each other, is graceful for every value of $n$. [This has been verified to be true for $n \le 27$.  I have announced a prize of Rs.5,000/- for a solution to this problem too.]

3. Characterize graphs $G$ in which every minimum dominating set induces a unique sub-graph up to isomorphism.

4. Characterize finite graphs $G$ that satisfy the inequality $(-1)^{|V(G)|} \psi(G,0)\psi(G,-1) \le 0$, where $\psi(G,r)$ denotes the value of the characteristic polynomial $\psi(G)$ evaluated for the real number $r$. [This is already known to be true for co-graphs.]

5. There exist co-graphs $G$ on which there are `unbalanced' signed graphs $S$ (i,e. $S$ in which every cycle contains an even number of negative edges), for which $(-1)^{|V(G)|} \psi(S,0)\psi(S,-1) > 0$. Hence, characterize signed graphs $\Sigma$ for which $(-1)^{|V(\Sigma)|} \psi(\Sigma,0)\psi(\Sigma,-1) \le 0$.

6. Characterize signed graphs each of whose spectrum contains a Golden Ratio -- I call such signed graphs "golden signed graphs". 

[Note that, by a theorem of B.D. Acharya (JGT, 1980), since every balanced signed graph on a given graph $G$ is cospectral with its underlying graph $G$, if $G$ is golden then all the balanced signed graphs on $G$ are golden. Similarly, signed graphs that are switching equivalent necessarily have the same eigenvalues by a theorem of T. Zaslavsky (DM, 1980). Therefore, only unbalanced signed graphs are of interest qua signed graphs.  For example, it is interesting that an unbalanced C_5 is golden.  In fact, it is surprising that both balanced and unbalanced signatures of C_5 are golden.  This is surely a rare property.  We (TZ and I) guess that there are only a few graphs $G$ (not counting trees as they are necessarily balanced) such that every signing of G is golden.]

7. A signed graph $\Sigma$ is perfectly golden if each of its eigenvalues is a golden ratio. Characterize perfectly golden signed graphs.

8. Two golden signed graphs are co-golden if they share the same multiset of golden ratios in their spectra. Conjecture: The proportion of the number of co-golden signed graphs of order $n$ to the number of cospectral signed graphs of order $n$ tends to zero as $n$ tends to infinity.   

9. Conjecture (B.D. Acharya: 1985): There are only a finite number of signed graphs each of whose spectrum consists of only integers. 

10. The degree $e(u)$ of a vertex $u$ in a signed graph $\Sigma$ of a finite order $p$ is defined as the number of positive edges incident to $u$ (called the positive degree of $u$ and denoted $e^+(u)$) minus the number of negative edges incident to $u$ (called the negative degree of $u$ and denoted $e^-(u)$). The degree sequence of $\Sigma$ is then a sequence of integers $e=(e_1, e_2, \dots, e_p)$, written in a non-decreasing order such that each of the numbers $e_i$ is the degree of some vertex of $\Sigma$. Let $\mathcal{S}_p(e)$ denote the set of all signed graphs of order $p$ having the same degree sequence $e$. Clearly, there are only a finite number of signed graphs with the same degree sequence, that is $|\mathcal{S}_p(e)| < \infty$. Let $\mathcal{D}_p$ denote the set of all degree sequences of signed graphs of order $p$. Construct a $p$-dimensional polytope $\mathcal{P}$ with $\mathcal{D}_p$ as its vertex set and $ee'$ forming a straight line segment joining $e$ and $e'$ ('edge') whenever there exists a signed graph $\Sigma_1 \in \mathcal{S}_p(e)$ and a signed graph $\Sigma_2 \in \mathcal{S}_p(e')$ such that $|E^+(\Sigma_1)| = |E^+(\Sigma_2)|$ and $|E^-(\Sigma_1)| = |E^-(\Sigma_2)|$, that is, they have the same number of positive and negative edges. Investigate the properties of $\mathcal{P}$. In particular, under what conditions it is convex?    

With best regards, I remain

yours sincerely,

B.D. ACHARYA