Search ResultsShowing 1-20 of 33
-
arXiv:2404.10216 (Published 2024-04-16)
Twist polynomial as a weight system for set systems
Comments: 11 pagesCategories: math.CORecently, Chmutov proved that the partial-dual polynomial considered as a function on chord diagrams satisfies the four-term relation. Deng et al. then proved that this function on framed chord diagrams also satisfies the four-term relation, i.e., is a framed weight system. In this paper, we extend their results to the twist polynomial of a set system by proving that the twist polynomial on set systems satisfies the four-term relation.
-
arXiv:2403.05825 (Published 2024-03-09)
A direct proof of well-definedness for the polymatroid Tutte polynomial
Categories: math.COFor a polymatroid $P$ over $[n]$, Bernardi, K\'{a}lm\'{a}n and Postnikov [\emph{Adv. Math.} 402 (2022) 108355] introduced the polymatroid Tutte polynomial $\mathscr{T}_{P}$ relying on the order $1<2<\cdots<n$ of $[n]$, which generalizes the classical Tutte polynomial from matroids to polymatroids. They proved the independence of this order by the fact that $\mathscr{T}_{P}$ is equivalent to another polynomial that only depends on $P$. In this paper, similar to the Tutte's original proof of the well-definedness of the Tutte polynomial defined by the summation over all spanning trees using activities depending on the order of edges, we give a direct and elementary proof of the well-definedness of the polymatroid Tutte polynomial.
-
arXiv:2402.03799 (Published 2024-02-06)
Partial-dual polynomial as a framed weight system
Comments: 11pages, 11figuresCategories: math.CORecently, Chmutov proved that the partial-dual polynomial considered as a function on chord diagrams satisfies the four-term relations. In this paper, we show that this function on framed chord diagrams also satisfies the four-term relations, i.e., is a framed weight system.
-
arXiv:2310.07104 (Published 2023-10-11)
On the edge reconstruction of the characteristic and permanental polynomials of a simple graph
Categories: math.COAs a variant of the Ulam's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, Cvetkovi\'c and Schwenk posed independently the following problem: Can the characteristic polynomial of a simple graph $G$ with vertex set $V$ be reconstructed from the characteristic polynomials of all subgraphs in $\{G-v|v\in V\}$ for $|V|\geq 3$? This problem is still open. A natural problem is: Can the characteristic polynomial of a simple graph $G$ with edge set $E$ be reconstructed from the characteristic polynomials of all subgraphs in $\{G-e|e\in E\}$? In this paper, we prove that if $|V|\neq |E|$, then the characteristic polynomial of $G$ can be reconstructed from the characteristic polynomials of all subgraphs in $\{G-uv, G-u-v|uv\in E\}$, and the similar result holds for the permanental polynomial of $G$. We also prove that the Laplacian (resp. signless Laplacian) characteristic polynomial of $G$ can be reconstructed from the Laplacian (resp. signless Laplacian) characteristic polynomials of all subgraphs in $\{G-e|e\in E\}$ (resp. if $|V|\neq |E|$).
-
arXiv:2309.13639 (Published 2023-09-24)
A deletion-contraction formula and monotonicity properties for the polymatroid Tutte polynomial
Comments: 27 pages, 2 figuresCategories: math.COThe Tutte polynomial is a crucial invariant of matroids. The polymatroid Tutte polynomial $\mathscr{T}_{P}(x,y)$, introduced by Bernardi et al., is an extension of the classical Tutte polynomial from matroids to polymatroids $P$. In this paper, we first obtain a deletion-contraction formula for $\mathscr{T}_{P}(x,y)$. Then we prove two natural monotonicity properties, for containment and for minors of the interior polynomial $x^{n}\mathscr{T}_{P}(x^{-1},1)$ and the exterior polynomial $y^{n}\mathscr{T}_{P}(1,y^{-1})$, for polymatroids $P$ over $[n]$. We show by a counter-example that these monotonicity properties do not extend to $\mathscr{T}_{P}(x,y)$. Using deletion-contraction, we obtain formulas for the coefficients of terms of degree $n-1$ in $\mathscr{T}_{P}(x,y)$. Finally, for all $k\geq 0$, we characterize hypergraphs $\mathcal{H}=(V,E)$ so that the coefficient of $y^{k}$ in the exterior polynomial of the associated polymatroid $P_{\mathcal{H}}$ attains its maximal value $\binom{|V|+k-2}{k}$.
-
arXiv:2309.11885 (Published 2023-09-21)
On the maximum local mean order of sub-k-trees of a k-tree
Categories: math.COFor a k-tree T, a generalization of a tree, the local mean order of sub-k-trees of T is the average order of sub-k-trees of T containing a given k-clique. The problem whether the largest local mean order of a tree (i.e., a 1-tree) at a vertex always takes on at a leaf was asked by Jamison in 1984 and was answered by Wagner and Wang in 2016. In 2018, Stephens and Oellermann asked a similar problem: for any k-tree T, does the maximum local mean order of sub-k-trees containing a given k-clique occur at a k-clique that is not a major k-clique of T? In this paper, we give it an affirmative answer.
-
arXiv:2308.00581 (Published 2023-08-01)
New results on the 1-isolation number of graphs without short cycles
Let $G$ be a graph. A subset $D \subseteq V(G)$ is called a 1-isolating set of $G$ if $\Delta(G-N[D]) \leq 1$, that is, $G-N[D]$ consists of isolated edges and isolated vertices only. The $1$-isolation number of $G$, denoted by $\iota_1(G)$, is the cardinality of a smallest $1$-isolating set of $G$. In this paper, we prove that if $G \notin \{P_3,C_3,C_7,C_{11}\}$ is a connected graph of order $n$ without $6$-cycles, or without induced 5- and 6-cycles, then $\iota_1(G) \leq \frac{n}{4}$. Both bounds are sharp.
-
arXiv:2306.06568 (Published 2023-06-11)
Extreme coefficients of multiplicity Tutte polynomials
Categories: math.COThe multiplicity Tutte polynomial including the arithmetic Tutte polynomial is a generalization of classical Tutte polynomial of matroids. In this paper, we obtain the expressions of six extreme coefficients of multiplicity Tutte polynomials. In particular, as corollaries, the expressions of corresponding extreme coefficients of Tutte polynomial for matroids are deduced.
-
arXiv:2305.07913 (Published 2023-05-13)
On the edge reconstruction of six digraph polynomials
Categories: math.COLet $G=(V,E)$ be a digraph having no loops and no multiple arcs, with vertex set $V=\{v_1,v_2,\ldots,v_n\}$ and arc set $E=\{e_1,e_2,\ldots,e_m\}$. Denote the adjacency matrix and the vertex in-degree diagonal matrix of $G$ by $A=(a_{ij})_{n\times n}$ and $D=diag(d^+(v_1),d^+(v_2),\cdots,d^+(v_n))$, where $a_{ij}=1$ if $(v_i,v_j)\in E(G)$ and $a_{ij}=0$ otherwise, and $d^+(v_i)$ is the number of arcs with head $v_i$. Set $f_1(G;x)=\det(xI-A), f_2(G;x)=\det(xI-D+A),f_3(G;x)=\det(xI-D-A),f_4(G;x)={\rm per}(xI-A), f_5(G;x)={\rm per}(xI-D+A),f_6(G;x)={\rm per}(xI-D-A)$, where $\det(X)$ and ${\rm per}(X)$ denote the determinant and the permanent of a square matrix $X$, respectively. In this paper, we consider a variant of the Ulam's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, and prove that, for any $1\leq i\leq 6$, \begin{equation*} (m-n)f_i(G;x)+xf_i'(G;x)=\sum\limits_{e\in E}f_i(G-e;x), \end{equation*} which implies that if $m\neq n$, then $f_i(G;x)$ can be reconstructed from $\{f_i(G-e;x)|e\in E\}$.
-
arXiv:2304.02256 (Published 2023-04-05)
Extremal trees, unicyclic and bicyclic graphs with respect to $p$-Sombor spectral radii
For a graph $G=(V,E)$ and $v_{i}\in V$, denote by $d_{v_{i}}$ (or $d_{i}$ for short) the degree of vertex $v_{i}$. The $p$-Sombor matrix $\textbf{S}_{\textbf{p}}(G)$ ($p\neq0$) of a graph $G$ is a square matrix, where the $(i,j)$-entry is equal to $\displaystyle (d_{i}^{p}+d_{j}^{p})^{\frac{1}{p}}$ if the vertices $v_{i}$ and $v_{j}$ are adjacent, and 0 otherwise. The $p$-Sombor spectral radius of $G$, denoted by $\displaystyle \rho(\textbf{S}_{\textbf{p}}(G))$, is the largest eigenvalue of the $p$-Sombor matrix $\textbf{S}_{\textbf{p}}(G)$. In this paper, we consider the extremal trees, unicyclic and bicyclic graphs with respect to the $p$-Sombor spectral radii. We characterize completely the extremal graphs with the first three maximum Sombor spectral radii, which answers partially a problem posed by Liu et al. in [MATCH Commun. Math. Comput. Chem. 87 (2022) 59-87].
-
arXiv:2301.05416 (Published 2023-01-13)
Two spectral extremal results for graphs with given order and rank
Comments: 26 pages, 3 figuresCategories: math.COThe spectral radius and rank of a graph are defined to be the spectral radius and rank of its adjacency matrix, respectively. It is an important problem in spectral extremal graph theory to determine the extremal graph that has the maximum or minimum spectral radius over certain families of graphs. Monsalve and Rada [Extremal spectral radius of graphs with rank 4, Linear Algebra Appl. 609 (2021) 1-11] obtained the extremal graphs with maximum and minimum spectral radii among all graphs with order n and rank 4. In this paper, we first determine the extremal graph which attains the maximum spectral radius among all graphs with any given order n and rank r, and further determine the extremal graph which attains the minimum spectral radius among all graphs with order n and rank 5.
-
arXiv:2210.15273 (Published 2022-10-27)
Partial-twuality polynomials of delta-matroids
Comments: 18 pagesCategories: math.COGross, Mansour and Tucker introduced the partial-twuality polynomial of a ribbon graph. Chumutov and Vignes-Tourneret posed a problem: it would be interesting to know whether the partial duality polynomial and the related conjectures would make sense for general delta-matroids. In this paper we consider analogues of partial-twuality polynomials for delta-matroids. Various possible properties of partial-twuality polynomials of set systems are studied. We discuss the numerical implications of partial-twualities on a single element and prove that the intersection graphs can determine the partial-twuality polynomials of bouquets and normal binary delta-matroids, respectively. Finally, we give a characterization of vf-safe delta-matroids whose partial-twuality polynomials have only one term.
-
arXiv:2207.04421 (Published 2022-07-10)
On the polymatroid Tutte polynomial
Comments: 14 pages, 0 figuresCategories: math.COThe Tutte polynomial is a well-studied invariant of matroids. The polymatroid Tutte polynomial $\mathcal{J}_{P}(x,y)$, introduced by Bernardi et al., is an extension of the classical Tutte polynomial from matroids to polymatroids $P$. In this paper, we first prove that $\mathcal{J}_{P}(x,t)$ and $\mathcal{J}_{P}(t,y)$ are interpolating for any fixed real number $t\geq 1$, and then we study the coefficients of high-order terms in $\mathcal{J}_{P}(x,1)$ and $\mathcal{J}_{P}(1,y)$. These results generalize results on interior and exterior polynomials of hypergraphs.
-
arXiv:2205.03487 (Published 2022-05-06)
Twist monomials of binary delta-matroids
Comments: 10 pages. arXiv admin note: text overlap with arXiv:2108.01263Categories: math.CORecently, we introduced the twist polynomials of delta-matroids and gave a characterization of even normal binary delta-matroids whose twist polynomials have only one term and posed a problem: what would happen for odd binary delta-matroids? In this paper, we show that a normal binary delta-matroid whose twist polynomials have only one term if and only if each connected component of the intersection graph of the delta-matroid is either a complete graph of odd order or a single vertex with a loop.
-
arXiv:2201.12531 (Published 2022-01-29)
On coefficients of the interior and exterior polynomials
Comments: 28 pages, 3 figuresCategories: math.COThe interior polynomial and the exterior polynomial are generalizations of valuations on $(1/\xi,1)$ and $(1,1/\eta)$ of the Tutte polynomial $T_G(x,y)$ of graphs to hypergraphs, respectively. The pair of hypergraphs induced by a connected bipartite graph are abstract duals and are proved to have the same interior polynomial, but may have different exterior polynomials. The top of the HOMFLY polynomial of a special alternating link coincides with the interior polynomial of the pair of hypergraphs induced by the Seifert graph of the link. Let $G=(V\cup E, \varepsilon)$ be a connected bipartite graph. In this paper, we mainly study the coefficients of the interior and exterior polynomials. We prove that the interior polynomial of a connected bipartite graph is interpolating. We strengthen the known result on the degree of the interior polynomial for connected bipartite graphs with 2-vertex cuts in $V$ or $E$. We prove that interior polynomials for a family of balanced bipartite graphs are monic and the interior polynomial of any connected bipartite graph can be written as a linear combination of interior polynomials of connected balanced bipartite graphs. The exterior polynomial of a hypergraph is also proved to be interpolating. It is known that the coefficient of the linear term of the interior polynomial is the nullity of the bipartite graph, we obtain a `dual' result on the coefficient of the linear term of the exterior polynomial: if $G-e$ is connected for each $e\in E$, then the coefficient of the linear term of the exterior polynomial is $|V|-1$. Interior and exterior polynomials for some families of bipartite graphs are computed.
-
arXiv:2201.12496 (Published 2022-01-29)
A direct and elementary proof of the well-definedness of the interior and exterior polynomials of hypergraphs
Comments: 14 pagesCategories: math.COT. K\'{a}lm\'{a}n (A version of Tutte's polynomial for hypergraphs, Adv. Math. 244 (2013) 823-873.) introduced the interior and exterior polynomials which are generalizations of the Tutte polynomial $T(x,y)$ on plane points $(1/x,1)$ and $(1,1/y)$ to hypergraphs. The two polynomials are defined under a fixed ordering of hyperedges, and are proved to be independent of the ordering using techniques of polytopes. In this paper, similar to the Tutte's original proof we provide a direct and elementary proof for the well-definedness of the interior and exterior polynomials of hypergraphs.
-
arXiv:2108.01263 (Published 2021-08-03)
Twist polynomials of delta-matroids
Comments: 13 pages, 1 figureCategories: math.CORecently, Gross, Mansour and Tucker introduced the partial duality polynomial of a ribbon graph and posed a conjecture that there is no orientable ribbon graph whose partial duality polynomial has only one non-constant term. We found an infinite family of counterexamples for the conjecture and showed that essentially these are the only counterexamples. This is also obtained independently by Chumutov and Vignes-Tourneret and they posed a problem: it would be interesting to know whether the partial duality polynomial and the related conjectures would make sence for general delta-matroids. In this paper, we show that partial duality polynomials have delta-matroid analogues. We introduce the twist polynomials of delta-matroids and discuss its basic properties for delta-matroids. We give a characterization of even normal binary delta-matroids whose twist polynomials have only one term and then prove that the twist polynomial of a normal binary delta-matroid contains non-zero constant term if and only if its intersection graph is bipartite.
-
arXiv:2106.12141 (Published 2021-06-23)
Enumeration of spanning trees of middle graphs
Categories: math.COLet $D$ be a connected weighted digraph. The relation between the vertex weighted complexity (with a fixed root) of the line digraph of $D$ and the edge weighted complexity (with a fixed root) of $D$ has been given in (L. Levine, Sandpile groups and spanning trees of directed line graphs, J. Combin. Theory Ser. A 118 (2011) 350-364) and, independently, in (S. Sato, New proofs for Levine's theorems, Linear Algebra Appl. 435 (2011) 943-952). In this paper, we obtain a relation between the vertex weighted complexity of the middle digraph of $D$ and the edge weighted complexity of $D$. Particularly, when the weight of each arc and each vertex of $D$ is 1, the enumerative formula of spanning trees of the middle digraph of a general digraph is obtained.
-
arXiv:2106.09873 (Published 2021-06-18)
The Ihara-zeta function and the spectrum of the join of two semi-regular bipartite graphs
Comments: 21 pagesIn this paper, using matrix techniques, we compute the Ihara-zeta function and the number of spanning trees of the join of two semi-regular bipartite graphs. Furthermore, we show that the spectrum and the zeta function of the join of two semi-regular bipartite graphs can determine each other.
-
arXiv:2102.02089 (Published 2021-02-03)
Tutte polynomials of fan-like graphs with applications in benzenoid systems
Categories: math.COWe study the computation of the Tutte polynomials of fan-like graphs and obtain expressions of their Tutte polynomials via generating functions. As applications, Tutte polynomials, in particular, the number of spanning trees, of two kinds of benzenoid systems, i.e. pyrene chains and triphenylene chains, are obtained.