SOME NEW RESULTS ON THE CURLING NUMBER OF GRAPHS

NEW

Problem: The paper’s Problem 7.6 is not a yes/no conjecture but an open-ended determination problem. I formalize it as follows: for finite simple nonempty graphs, determine $cn^c$ of the standard products considered or mentioned in the paper when one factor is regular.

Use the paper’s convention that if the well-arranged degree sequence has degree-class multiplicities $\mu_X(q)=|\{v:d_X(v)=q\}|$, then

$$cn^c(X)=\prod_{\mu_X(q)>0}\mu_X(q).$$

Let $R$ be $k$-regular on $m$ vertices, and let $H$ have order $n$. Put

$$D=\{d:\ a_d>0\},\qquad a_d=|\{v\in V(H):d_H(v)=d\}|,\qquad C_H=\prod_{d\in D}a_d .$$

Result: The compound curling numbers are as follows.

$$cn^c(R\square H)=m^{|D|}C_H.$$ $$cn^c(R\boxtimes H)=m^{|D|}C_H.$$

For the direct/tensor product:

$$cn^c(R\times H)= \begin{cases} m^{|D|}C_H,& k>0,\\ mn,& k=0. \end{cases}$$

For the lexicographic products:

$$cn^c(R[H])=cn^c(H[R])=m^{|D|}C_H.$$

For the join $R+H$, let $d_0=k+n-m$. Then

$$cn^c(R+H)= \begin{cases} (m+a_{d_0})\displaystyle\prod_{d\in D,\ d\ne d_0}a_d,& d_0\in D,\\[1ex] mC_H,& d_0\notin D. \end{cases}$$

For the corona $R\odot H$, let $d_1=k+n-1$. Then

$$cn^c(R\odot H)= \begin{cases} (m+ma_{d_1})\displaystyle\prod_{d\in D,\ d\ne d_1}(ma_d),& d_1\in D,\\[1ex] m^{|D|+1}C_H,& d_1\notin D. \end{cases}$$

For the reversed corona $H\odot R$, let $d_2=k+1-m$. Then

$$cn^c(H\odot R)= \begin{cases} (nm+a_{d_2})\displaystyle\prod_{d\in D,\ d\ne d_2}a_d,& d_2\in D,\\[1ex] nmC_H,& d_2\notin D. \end{cases}$$

Proof. In each case, compute the degree of a product vertex.

For $R\square H$,

$$d_{R\square H}(r,h)=k+d_H(h),$$

so each degree class $d$ of $H$ becomes a degree class of size $ma_d$.

For $R\boxtimes H$,

$$d_{R\boxtimes H}(r,h)=k+d_H(h)+kd_H(h)=k+(k+1)d_H(h),$$

again injective in $d_H(h)$.

For $R\times H$,

$$d_{R\times H}(r,h)=k\,d_H(h).$$

If $k>0$, the degree classes remain separated; if $k=0$, all $mn$ vertices have degree $0$.

For $R[H]$,

$$d_{R[H]}(r,h)=kn+d_H(h),$$

and for $H[R]$,

$$d_{H[R]}(h,r)=m\,d_H(h)+k,$$

so the same multiplicities $ma_d$ occur.

For the join, vertices of $R$ have degree $k+n$, while vertices of $H$ of original degree $d$ have degree $d+m$. These collide exactly when $d=d_0=k+n-m$, giving the stated formula.

For $R\odot H$, vertices from $R$ have degree $k+n$, while vertices in the attached copies of $H$ coming from degree $d$ have degree $d+1$ and multiplicity $ma_d$. Collision occurs exactly when $d=d_1=k+n-1$.

For $H\odot R$, vertices from $H$ of degree $d$ become degree $d+m$, while all vertices in copies of $R$ have degree $k+1$, with multiplicity $nm$. Collision occurs exactly when $d=d_2=k+1-m$.

In every case, $cn^c$ is the product of the resulting degree-class multiplicities. This proves all formulas.

Audit. The formulas use only the regularity, order, and degree-class multiplicities of the other graph; no hidden connectedness assumption is needed. If the paper’s standing convention “finite simple nontrivial connected” is imposed, these formulas remain valid, with the $k=0$ degeneracies automatically excluded except for $K_1$-type boundary cases.

Citation: Problem and terminology: N. K. Sudev, C. Susanth, K. P. Chithra, J. Kok, S. J. Kalayathankal, “Some New Results on the Curling Number of Graphs,” arXiv:1510.01271. Standard product degree formulas are classical; see R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, 2nd ed., CRC Press, 2011.