University of IsfahanTransactions on Combinatorics2251-865713220240601On the skew spectral moments of trees with a given bipartition1271362727510.22108/toc.2023.128742.1856ENYapingWuSchool of Artificial Intelligence, Jianghan University, 430056, Wuhan, P. R.ChinaQiongFanSchool of Mathematics and Statistics, Central China Normal University, 430070, Wuhan, P. R.ChinaHuiqingLiuSchool of Mathematics and Statistics, Hubei University, 430062, Wuhan, P. R.ChinaWeishengZhaoSchool of Artificial Intelligence, Jianghan University, 430056, Wuhan, P. R.ChinaJournal Article20210518Let $G$ be a simple graph, and $\vec{G}$ be an oriented graph of $G$ with an orientation and skew-adjacency matrix $S(\vec{G})$. Let $\lambda_1(\vec{G}), \lambda_2(\vec{G}),\ldots,\lambda_n(\vec{G})$ be the eigenvalues of $S(\vec{G})$. The number $\sum_{i=1}^{n}\lambda_i^k(\vec{G})$ $(k=0, 1,\ldots,n-1)$, denoted by $T_k(\vec{G})$, is called the $k$-th {\em skew spectral moment} of $\vec{G}$, and $T(\vec{G})=(T_0(\vec{G}),T_1(\vec{G}),\ldots,$ $T_{n-1}(\vec{G}))$ is the sequence of skew spectral moments of $\vec{G}$. Suppose $\vec{G}_1$ and $\vec{G}_2$ are two digraphs. We shall write $\vec{G}_1\prec_T \vec{G}_2$ ($\vec{G}_1$ comes before $\vec{G}_2$ in a $T$-order) if for some $k$ $(1 \leq k \leq n-1)$, $T_i(\vec{G}_1)=T_i(\vec{G}_2)$ ($i=0, 1,\ldots,k-1$) and $T_k(\vec{G_1})< T_k(\vec{G}_2)$ hold. For two given positive integers $p$ and $q$ with $p \leq q$, we denote $\mathscr T_{n}^{p,q}=\{T: T$ is a tree of order $n$ with a $(p,q)$-bipartition $\}$. In this paper, we discuss $T$-order among all trees in $\mathscr T_{n}^{p,q}$. Furthermore, the last three trees, in the $T$-order, underlying graphs among $\mathscr T_{n}^{p,q}~(4\leq p\leq q)$ are characterized.https://toc.ui.ac.ir/article_27275_dcabe982e0b71f416bf15ea1140c0684.pdfUniversity of IsfahanTransactions on Combinatorics2251-865713220240601A new $q$-analogue of the binomial identity $\sum_{k}(-1)^k{2n\choose n+3k}=2\cdot 3^{n-1}$1371422726910.22108/toc.2023.135277.2017ENYan-NiLiDepartment of Mathematics, Wenzhou University, Wenzhou, PR ChinaYuan-YuanZhaoDepartment of Mathematics, Wenzhou University, Wenzhou, PR ChinaJournal Article20220929In this paper, we establish a new $q$-analogue of the binomial identity:<br />\begin{align*}<br />&\sum_{k}(-1)^k{2n\choose n+3k}=<br />\begin{cases}<br />1,&\text{if $n=0$,}\\[5pt]<br />2\cdot3^{n-1},&\text{if $n\ge 1$.}<br />\end{cases}<br />\end{align*}<br />Our proof relies on a weight-preserving and sign-reversing involution due to Guo and Zhang.https://toc.ui.ac.ir/article_27269_317c41c8d5ea02d038cbaaa17b7694f0.pdfUniversity of IsfahanTransactions on Combinatorics2251-865713220240601Some results on non-progressive spread of influence in graphs1431522738710.22108/toc.2023.133649.1988ENSamanehHosseinzadehFaculty of Science, Urmia University of Technology, Urmia, IranHosseinSoltaniFaculty of Science, Urmia University of Technology, Urmia, IranJournal Article20220517This paper studies the non-progressive spread of influence with threshold model in social networks. Consider a graph $G$ with a threshold function $\tau$ on its vertex set. Spread of influence is a discrete dynamic process as follows. For a given set of initially infected vertices at time step $0$ each vertex $v$ gets infected at time step $i$, $i\geq1$, if and only if the number of infected neighbors are at least $\tau(v)$ in time step $i-1$. Our goal is to find the minimum cardinality of initially infected vertices (perfect target set) such that eventually all of the vertices get infected at some time step $\ell$.<br /> <br />In this paper an upper bound for the convergence time of the process is given for graphs with general thresholds. Then an integer linear programming for the size of minimum perfect target set is presented. Then we give a lower bound for the size of perfect target sets with strict majority threshold on graphs which all of the vertices have even degrees. It is shown that the later bound is asymptotically tight.https://toc.ui.ac.ir/article_27387_3cbad2d6f93ace8f4492ca1a59126be5.pdfUniversity of IsfahanTransactions on Combinatorics2251-865713220240601The Higman-Sims sporadic simple group as the automorphism group of resolvable $3$-designs1531642744910.22108/toc.2023.132404.1956ENAli RezaRahimipourDepartment of Mathematics, Faculty of Science, University of Qom, P.O. Box 37161−46611, Qom, I. R. IranJournal Article20220119Presenting sporadic simple groups as an automorphism groups of designs and graphs is an exciting field in finite group theory.In this paper, with two different methods, we present some new resolvable simple $3$-designs with Higman-Sims sporadic simple group $\rm HS$ as the full automorphism group.Also, we classify all block-transitive self-orthogonal designs on 176 points with even block size that admit sporadic simple group $\rm HS$ as an automorphism group. Furthermore, with these methods we construct some new resolvable $3$-designs on 36, 40, 120 and 176 points.https://toc.ui.ac.ir/article_27449_93598d4e4857489d340fb1104c1c9a68.pdfUniversity of IsfahanTransactions on Combinatorics2251-865713220240601Graphs without a $2C_3$-minor and bicircular matroids without a $U_{3,6}$-minor1651672747010.22108/toc.2023.134261.1998ENDanielSlilatyDepartment of Mathematics and Statistics, Wright State University Dayton, OH 45435, USAJournal Article20220703In this note we characterize all graphs without a $2C_3$-minor. A consequence of this result is a characterization of the bicircular matroids with no $U_{3,6}$-minor.https://toc.ui.ac.ir/article_27470_8757063fc4c35a68565bdfb58eb12719.pdfUniversity of IsfahanTransactions on Combinatorics2251-865713220240601Whitney numbers of partial dowling lattices1691782757510.22108/toc.2023.135127.2013ENThomasZaslavskyBinghamton University, Binghamton, NY 13902-6000,
U.S.A.Journal Article20220913The Dowling lattice $Q_n(G)$, $G$ a finite group, generalizes the geometric lattice generated by all vectors, over a field, with at most two nonzero components. Abstractly, it is a fundamental object in the classification of finite matroids. Constructively, it is the frame matroid of a certain gain graph known as $G K{_n}{^V}$. Its Whitney numbers of the first kind enter into several important formulas. Ravagnani suggested and partially proved that these numbers of $Q_n(G)$ and higher-weight generalizations are polynomial functions of $|G|$. We give a simple proof for $Q_n(G)$ and its generalization to a wider class of gain graphs and biased graphs, and we determine the degrees and coefficients of the polynomials.https://toc.ui.ac.ir/article_27575_bdef8952ccff9cae9d0dc839bfbe55e8.pdfUniversity of IsfahanTransactions on Combinatorics2251-865713220240601The generous Roman domination number1791962760210.22108/toc.2023.131167.1928ENMohammedBenatallahRECITS Laboratory, Faculty of Sciences UZA, Djelfa, AlgeriaMostafaBlidiaDepartment of Mathematics, University of Blida, Blida, AlgeriaLyesOuldrabahDepartment of Mathematics, University of M´ed´ea, M´ed´ea, Algeria0000-0002-8667-5214Journal Article20211024Let $G=(V,E)$\ be a simple graph and $f:V\rightarrow\{0,1,2,3\}$ be a function. A vertex $u$ with $f\left( u\right) =0$ is called an undefended vertex with respect to $f$ if it is not adjacent to a vertex $v$ with $f(v)\geq2.$ We call the function $f$ a generous Roman dominating function (GRDF) if for every vertex with $f\left( u\right) =0$ there exists at least a vertex $v$ with $f(v)\geq2$ adjacent to $u$ such that the function $f^{\prime}:V\rightarrow \{0,1,2,3\}$, defined by $f^{\prime}(u)=\alpha$, $f^{\prime}(v)=f(v)-\alpha$ where $\alpha=1$ or $2$, and $f^{\prime}(w)=f(w)$ if $w\in V-\{u,v\}$ has no undefended vertex. The weight of a generous Roman dominating function $f$ is the value $f(V)=\sum_{u\in V}f(u)$. The minimum weight of a generous Roman dominating function on a graph $G$\ is called the generous Roman domination number of $G$, denoted by $\gamma_{gR}\left( G\right) $. In this paper, we initiate the study of generous Roman domination and show its relationships. Also, we give the exact values for paths and cycles. Moreover, we present an upper bound on the generous Roman domination number, and we characterize cubic graphs $G$ of order $n$ with $\gamma_{gR}\left( G\right) =n-1$, and a Nordhaus-Gaddum type inequality for the parameter is also given. Finally, we study the complexity of this parameter.https://toc.ui.ac.ir/article_27602_9913122b39dd18476cff7ba023f8540e.pdf