University of IsfahanTransactions on Combinatorics2251-865712320230901The number of graph homomorphisms between paths and cycles with loops, a problem from Stanley’s enumerative combinatorics1151302678810.22108/toc.2022.131646.1949ENZeinabBandpeyDepartment of Mathematics, Northern Virginia Community College, 2645 College Drive, Woodbridge, VA 22191, United
States of America0000-0001-7670-4790Jonathan DavidFarleyDepartment of Mathematics, Northern Virginia Community College, 2645 College Drive, Woodbridge, VA 22191, United
States of AmericaJournal Article20220103Let $g_{k}(n)$ denote the number of sequences $t_{1},ldots,t_{n}$ in $\{0, 1,\ldots,k-1\}$ such that $t_{j+1}\equiv t_{j}-1, t_{j}$ or $t_{j}+1$ (mod $k$), $1\leq j\leq n$, (where $t_{n+1}$ is identified with $t_{1}$). It is proved combinatorially that $g_{4}(n)= 3^{n}+2+(-1)^{n}$ and $g_{6}(n)= 3^{n}+2^{n+1}+(-1)^{n}$. This solves a problem from Richard P. Stanley's 1986 text, $Enumerative$ $Combinatorics$.https://toc.ui.ac.ir/article_26788_8767f1e10b0ecd627858fb572c491887.pdfUniversity of IsfahanTransactions on Combinatorics2251-865712320230901The normalized signless Laplacian Estrada index of graphs1311422678910.22108/toc.2022.127155.1814ENŞ. BurcuBozkurt AltındağYenikent Kardelen Konutları, Selçuklu, Konya, Turkey0000-0001-9727-6107Emina I.MilovanovicFaculty of Electronic Engineering, University of Niš, Niš, SerbiaMarjanMatejicFaculty of Electronic Engineering, University of Niš, Niš, Serbia0000-0003-0354-6749IgorMilovanovicFaculty of Electronic Engineering, University of Niš, Niš, SerbiaJournal Article20210124Let $G$ be a simple connected graph of order $n$ with $m$ edges. Denote by $% \gamma _{1}^{+}\geq \gamma _{2}^{+}\geq \cdots \geq \gamma _{n}^{+}\geq 0$ the normalized signless Laplacian eigenvalues of $G$. In this work, we define the normalized signless Laplacian Estrada index of $G$ as $NSEE\left(G\right) =\sum_{i=1}^{n}e^{\gamma _{i}^{+}}.$ Some lower bounds on $%NSEE\left( G\right) $ are also established.https://toc.ui.ac.ir/article_26789_9c9907d54350ec8e47c22a708eaa9627.pdfUniversity of IsfahanTransactions on Combinatorics2251-865712320230901Transformations among rectangular partitions1431632680810.22108/toc.2022.133242.1984ENVinodKumarDepartment of Mathematics, Birla Institute of Technology and Science, Pilani, Pilani Campus, Rajasthan-333031, India0000-0001-5008-0166KrishnendraShekhawatDepartment of Mathematics, Birla Institute of Technology and Science, Pilani, Pilani Campus, Rajasthan-333031, India0000-0002-3408-7912Journal Article20220409We first prove that there always exists a maximal rectangularly dualizable graph for a given rectangularly dualizable graph and present an algorithm for its construction. Further, we show that a maximal rectangularly dualizable graph can always be transformed to an edge-irreducible rectangularly dualizable graph and present an algorithm that transforms a maximal rectangularly dualizable graph to an edge-irreducible rectangularly dualizable graph.https://toc.ui.ac.ir/article_26808_c7fc0941f103f715082931044c68cdd4.pdfUniversity of IsfahanTransactions on Combinatorics2251-865712320230901Energy of strong reciprocal graphs1651712681010.22108/toc.2022.134259.1999ENMaryamGhahremaniDepartment of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, IranAbolfazlTehranianScience and Research Branch, Islamic Azad UniversityHamidRasouliDepartment of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, IranMohammad AliHosseinzadehFaculty of Engineering Modern Technologies, Amol University of Special Modern Technologies, Amol, IranJournal Article20220704The energy of a graph $G$, denoted by $\mathcal{E}(G)$, is defined as the sum of absolute values of all eigenvalues of $G$. A graph $G$ is called reciprocal if $ \frac{1}{\lambda} $ is an eigenvalue of $G$ whenever $\lambda$ is an eigenvalue of $G$. Further, if $ \lambda $ and $\frac{1}{\lambda}$ have the same multiplicities, for each eigenvalue $\lambda$, then it is called strong reciprocal. In (MATCH Commun. Math. Comput. Chem. 83 (2020) 631--633), it was conjectured that for every graph $G$ with maximum degree $\Delta(G)$ and minimum degree $\delta(G)$ whose adjacency matrix is non-singular, $\mathcal{E}(G) \geq \Delta(G) + \delta(G)$ and the equality holds if and only if $G$ is a complete graph. Here, we prove the validity of this conjecture for some strong reciprocal graphs. Moreover, we show that if $G$ is a strong reciprocal graph, then $\mathcal{E}(G) \geq \Delta(G) + \delta(G) - \frac{1}{2}$. Recently, it has been proved that if $G$ is a reciprocal graph of order $n$ and its spectral radius, $\rho$, is at least $4\lambda_{min}$, where $ \lambda_{min}$ is the smallest absolute value of eigenvalues of $G$, then $\mathcal{E}(G) \geq n+\frac{1}{2}$. In this paper, we extend this result to almost all strong reciprocal graphs without the mentioned assumption.https://toc.ui.ac.ir/article_26810_877d7be13cf3ac469149b724447166ab.pdfUniversity of IsfahanTransactions on Combinatorics2251-865712320230901Counterexamples to a conjecture on matching Kneser graphs1721732684710.22108/toc.2022.132638.1961ENMoharramN. IradmusaDepartment of Mathematical Sciences, Shahid Beheshti University.0000-0003-0608-5781Journal Article20220207Let $G$ be a graph and $r\in\mathbb{N}$. The matching Kneser graph $\textsf{KG}(G, rK_2)$ is a graph whose vertex set is the set of $r$-matchings in $G$ and two vertices are adjacent if their corresponding matchings are edge-disjoint. In [M. Alishahi and H. Hajiabolhassan, On the Chromatic Number of Matching Kneser Graphs, <em>Combin. Probab. and Comput.</em>, <strong>29</strong>, No. 1 (2020), 1--21] it was conjectured that for any connected graph $G$ and positive integer $r\geq 2$, the chromatic number of $\textsf{KG}(G, rK_2)$ is equal to $|E(G)|-\textsf{ex}(G,rK_2)$, where $\textsf{ex}(G,rK_2)$ denotes the largest number of edges in $G$ avoiding a matching of size $r$. In this note, we show that the conjecture is not true for snarks.https://toc.ui.ac.ir/article_26847_9307b1b5b45d7de0418b8b8b2bb530fc.pdf