Authors:Baoyindureng Wu, Heping Zhang Pages: 1 - 8 Abstract: An edge subset $S$ of a connected graph $G$ is called an anti-Kekul\'{e} set if $G-S$ is connected and has no perfect matching. We can see that a connected graph $G$ has no anti-Kekul\'{e} set if and only if each spanning tree of $G$ has a perfect matching. In this note, we characterize all graphs where each spanning tree has a perfect matching. In addition, we show that if $G$ is a connected graph of order $2n$ for a positive integer $n\geq 4$ and size $m$ whose each spanning tree has a perfect matching, then $m\leq (n+1)n/2$, with equality if and only if $G\cong K_n\circ K_1$. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Jin Hong Kim, Park Nari Pages: 9 - 30 Abstract: Recently Sjoberg and Ziegler showed a remarkable result that completely characterizes the flag vector pair $(f_0, f_{03} )$ of any $4$-dimensional polytopes. Motivated by their results and techniques, in this paper we show some necessary conditions for other remaining flag vector pairs such as $(f_0 , f_{02})$, $(f_{02}, f_{03})$, $(f_{1}, f_{02})$, and $(f_1 , f_{03})$ to be flag vector pairs of $4$-dimensional convex polytopes. Results of this paper give some partial answers to the questions posed by Sj\" oberg and Ziegler. As an application of the bounds for flag vector pairs $(f_1 , f_{03})$, in this paper we also provide some bounds of fatness function for certain $4$-polytopes as well as $3$-polytopes. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Nadia Li, Wenchang Chu Pages: 31 - 41 Abstract: By means of the linearization method, we establish four analytical formulae for the $q$-Kummer sum extended by two integer parameters. Ten closed formulae are presented as examples. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Hery Randriamaro Pages: 42 - 64 Abstract: The story ”Tutte Polynomial of Reflection Group” begins in 2007 when Ardila computed the Tutte polynomials of the hyperplane arrangements associated to the symmetric groups Sym(n), and to the imprimitive groups $G(2,1,n)$ and $G(2,2,n)$. One year later, De Concini and Procesi computed the Tutte polynomials associated to the primitive groups $G28,G35,G36,G37$, as well as Geldon in 2009. Then, we computed those associated to the imprimitive groups $G(m,p,n)$ in 2017. This article aims to close the chapter on the complex reflection groups by computing the Tutte polynomials associated to the primitive groups $G4,...,G27,G29,...,G34$. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Longshu Wu, Qin Wang Pages: 65 - 73 Abstract: A graph $G$ is induced matching extendable (shortly, IM-extendable) if every induced matching of $G$ is included in a perfect matching of $G$. The IM-extendable graph was first introduced by Yuan. A graph $G$ is nearly IM-extendable if $G \vee K_1$ is IM-extendable. We show in this paper that: (1) Let $G$ be a graph with $2n-1$ vertices, where $n \geq 2$. If for each pair of nonadjacent vertices $u$ and $v$ in $G$, $d(u)+d(v) \geq 2 \lceil {{4n}/{3}}\rceil-3$, then $G$ is nearly IM-extendable. (2) Let $G$ be a claw-free graph with $2n-1$ vertices, where $n \geq 2$. If for each pair of nonadjacent vertices $u$ and $v$ in $G$, $d(u)+d(v) \geq 2n-1$, then $G$ is nearly IM-extendable. Minimum degree conditions of nearly IM-extendable graphs and nearly IM-extendable claw-free graphs are also obtained in this paper. It is also shown that all these results are best possible. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Samir Shukla, Shuchita Goyal, Anurag Singh Pages: 74 - 92 Abstract: We show that the independence complexes of generalised Mycielskian of complete graphs are homotopy equivalent to a wedge sum of spheres, and determine the number of copies and the dimensions of these spheres. We also prove that the independence complexes of categorical product of complete graphs are wedge sum of circles, upto homotopy. Further, we show that if we perturb a graph $G$ in a certain way, then the independence complex of this new graph is homotopy equivalent to the suspension of the independence complex of $G$. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Wei Gao, Yanling Shao Pages: 93 - 110 Abstract: Let $G$ be a simple graph with vertex set $V(G)=\{v_{1},v_{2},$ $\dots,v_{n}\}$, and $G^{\sigma}$ be an orientation of $G$. Denote by $d(v_i)$ the degree of the vertex $v_i$ for $i=1,2,\dots,n$. The skew Randić matrix of $G^{\sigma}$, denoted by $R_S(G^{\sigma})$, is the real skew-symmetric matrix $(r_{ij})_{n\times n}$, where $r_{ij}={1}/{\sqrt{d(v_i)d(v_j)}}$ and $r_{ji}=-{1}/{\sqrt{d(v_i)d(v_j)}}$ if $v_i\rightarrow v_j$ is an arc of $G^{\sigma}$, otherwise $r_{ij}=r_{ji}=0$. The skew Randi\'{c} energy $\mathcal{RE}_S(G^{\sigma})$ of $G^{\sigma}$ is defined as the sum of the norms of all the eigenvalues of $R_S(G^{\sigma})$. In this paper, the oriented unicyclic graphs with minimal skew Randić energy are determined. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Katherina Böhmova, Cristina Dalfo, Clemens Huemer Pages: 111 - 124 Abstract: We obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs' $MCK(d,\ell)$, and it is derived from the Kautz digraphs $K(d,\ell)$ and from the so-called cyclic Kautz digraphs $CK(d,\ell)$. The cyclic Kautz digraphs $CK(d,\ell)$ were defined as the digraphs whose vertices are labeled by all possible sequences $a_1\ldots a_\ell$ of length $\ell$, such that each character $a_i$ is chosen from an alphabet of $d+1$ distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that $a_1\neq a_\ell$. Their arcs are between vertices $a_1 a_2\ldots a_\ell$ and $a_2 \ldots a_\ell a_{\ell+1}$, with $a_1\neq a_\ell$ and $a_2\neq a_{\ell+1}$. Since $CK(d,\ell)$ do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that $MCK(d,\ell)$ are $d$-out-regular. Moreover, for $t\geq1$, we compute the number of vertices of the iterated line digraphs $L^t(CK(d,\ell))$. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Antoine Deza, Jean-Baptiste Hiriart-Urruty, Lionel Pournin Pages: 125 - 138 Abstract: We study a family of polytopes and their duals, that appear in various optimization problems as the unit balls for certain norms. These two families interpolate between the hypercube, the unit ball for the $\infty$-norm, and its dual cross-polytope, the unit ball for the $1$-norm. We give combinatorial and geometric properties of both families of polytopes such as their $f$-vector, their volume, and the volume of their boundary. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Abel Cabrera Martinez Pages: 139 - 152 Abstract: An Italian dominating function on a graph $G$ is a function $f:V(G)\rightarrow \{0,1,2\}$ such that $\sum_{u\in N(v)}f(u)\geq 2$ for every vertex $v\in V_0$, where $V_0=\{v\in V(G) : f(v)=0\}$ and $N(v)$ represents the open neighbourhood of $v$. A starred Italian dominating function on $G$ is an Italian dominating function $f$ such that $V_0$ is not a dominating set of $G$. The starred Italian domination number of $G$, denoted $\gamma_{I}^*(G)$, is the minimum weight $\omega(f)=\sum_{v\in V(G)}f(v)$ among all starred Italian dominating functions $f$ on $G$. In this article, we initiate the study of the starred Italian domination in graphs. For instance, we give some relationships that exist between this parameter and other domination invariants in graphs. Also, we present tight bounds and characterize the extreme cases. In addition, we obtain exact formulas for some particular families of graphs. Finally, we show that the problem of computing the starred Italian domination number of a graph is NP-hard. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Jesus Gonzalez, Teresa I. Hoekstra-Mendoza Pages: 139 - 160 Abstract: Let $D_{n,\gamma}$ be the complex of graphs on $n$ vertices and domination number at least~$\gamma$. We prove that $D_{n,n-2}$ has the homotopy type of a finite wedge of 2-spheres. This is done by using discrete Morse theory techniques. Acyclicity of the needed matching is proved by introducing a relativized form of a well known method for constructing acyclic matchings on suitable chunks of simplices. Our approach allows us to extend our results to the realm of infinite graphs. In addition, we give evidence supporting the assertion that the homotopy equivalences $D_{n,n-1}\simeq \bigvee S^0$ and $D_{n,n-2}\simeq \bigvee S^2$ do not seem to generalize for $D_{n,\gamma}$ with $\gamma\leq n-3$. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Authors:Jason Brown, Iain Beaton Pages: 175 - 182 Abstract: A dominating set $S$ of a graph $G$ of order $n$ is a subset of the vertices of $G$ such that every vertex is either in $S$ or adjacent to a vertex of $S$. The domination polynomial is defined by $D(G,x) = \sum d_k x^k$ where $d_k$ is the number of dominating sets in $G$ with cardinality $k$. In this paper we show that the closure of the real roots of domination polynomials is $(-\infty,0]$. PubDate: 2021-12-31 Issue No:Vol. 16, No. 3 (2021)
Open Access journal
[18 journals]
