Narrow Results

We give a list of minimal grid diagrams of the 13 crossing prime non-alternating knots which have arc index 13. There are 9,988 prime knots with crossing number 13. Among them 4,878 are alternating and have arc index 15. Among the other non-alternating knots, 49, 399, 1,412, and 3,250 have arc index 10, 11, 12, and 13, respectively. We used the Dowker–Thistlethwaite code of the 3,250 knots provided by the program Knotscape to generate spanning trees of the corresponding knot diagrams to obtain minimal arc presentations in the form of grid diagrams.

Remmel and Williamson recently defined a class of directed graphs, called filtered digraphs, and described a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions [12]. Filtered digraphs include many specialized graphs such as complete k-partite graphs. The Remmel-Williamson bijections provide explicit formulas for various multivariate generating functions for the oriented spanning forests which arise in this context. In this paper, we prove another important property of these bijections, namely, that it allows one to construct efficient algorithms for ranking and unranking spanning trees or spanning forests of filtered digraphs G. For example, we show that if G=(V,E) is a filtered digraph and SP(G) is the collection of spanning trees of G, then our algorithm requires O(|V|) operations of sum, difference, product, quotient, and comparison of numbers less than or equal |SP(G)| to rank or unrank spanning trees of G.

The current standard transparent bridge protocol IEEE-802.1D is based on the Spanning Tree (ST) algorithm. It has a very important restriction: it cannot work when the topology has active loops. Therefore, a tree is the only possible interconnection topology that can be used. The ST algorithm guarantees that the active topology is a tree discarding lines that form loops. However, because of this, network bandwidth cannot be fully utilized. Moreover, trees have a very serious bottleneck near the root. This paper proposes a new transparent bridge protocol for LAN interconnection that allows active loops. Therefore, strongly connected regular topologies like tori, hypercubes, meshes, etc., as well as irregular topologies can be used without wasting bandwidth. As loops provide alternative paths, the new protocol (named OSR for Optimal-Suboptimal Routing) uses optimal routing or, in the worst case, suboptimal routing.

Inspired by the combinatorial constructions in earlier work of the authors that generalized the classical Alexander polynomial to a large class of spatial graphs with a balanced weight on edges, we show that the value of the Alexander polynomial evaluated at $t=1$ gives the weighted number of the spanning trees of the graph.

This paper proposes a generalized form of Apollonian networks and derives their closed expression for the numbers of spanning trees. The n-edges Apollonian networks are transformed into n-order weighted wheels using the electrically equivalent transformations and weighted generating function rules. The numbers of spanning trees in the weighted fans are then calculated to obtain the counting formula of spanning trees in the weighted wheels, thereby deriving the exact expression for spanning trees of the generalized Apollonian networks.

In this paper, we calculate the Laplacian spectra of a 3-prism graph and apply them. This graph is both planar and polyhedral, and belongs to the generalized Petersen graph. Using the regular structures of this graph, we obtain the recurrent relationships for Laplacian matrix between this graph and its initial state — a triangle — and further derive the corresponding relationships for Laplacian eigenvalues between them. By these relationships, we obtain the analytical expressions for the product and the sum of the reciprocals of all nonzero Laplacian eigenvalues. Finally we apply these expressions to calculate the number of spanning trees and mean first-passage time (MFPT) and see that the scaling of MFPT with the network size N is N², which is larger than those performed on some uniformly recursive trees.

Complex networks have attracted a great deal of attention from scientific communities, and have been proven as a useful tool to characterize the topologies and dynamics of real and human-made complex systems. Laplacian spectrum of the considered networks plays an essential role in their network properties, which have a wide range of applications in chemistry and others. Firstly, we define one vertex–vertex graph. Then, we deduce the recursive relationship of its eigenvalues at two successive generations of the normalized Laplacian matrix, and we obtain the Laplacian spectrum for vertex–vertex graph. Finally, we show the applications of the Laplacian spectrum, i.e. first-order network coherence, second-order network coherence, Kirchhoff index, spanning tree, and Laplacian-energy-like.

This paper presents an algorithm to construct a weighted adjacency matrix of a plane bipartite graph obtained from a pretzel knot diagram. The determinant of this matrix after evaluation is shown to be the Jones polynomial of the pretzel knot by way of perfect matchings (or dimers) of this graph. The weights are Tutte's activity letters that arise because the Jones polynomial is a specialization of the signed version of the Tutte polynomial. The relationship is formalized between the familiar spanning tree setting for the Tait graph and the perfect matchings of the plane bipartite graph above. Evaluations of these activity words are related to the chain complex for the Champanerkar–Kofman spanning tree model of reduced Khovanov homology.

The space ${𝒞}$ of conservative vertex colorings (over a field $𝔽$) of a countable, locally finite graph $G$ is introduced. When $G$ is connected, the subspace ${{𝒞}}^0$ of based colorings is shown to be isomorphic to the bicycle space of the graph. For graphs $G$ with a cofinite free ${\mathbb{Z}}^d$-action by automorphisms, ${𝒞}$ is dual to a finitely generated module over the polynomial ring $𝔽[x_1^{\pm 1},\dots ,x_d^{\pm 1}]$. Polynomial invariants for this module, the Laplacian polynomials ${\mathrm{\Delta }}_k,k\ge 0$, are defined, and their properties are discussed. The logarithmic Mahler measure of ${\mathrm{\Delta }}_0$ is characterized in terms of the growth of spanning trees.

We consider a model of multicast communication in a network whereby multiple sources have messages to disseminate among all sites of a network. We propose that the messages from all sources are disseminated along the same spanning tree of the network and consider the problem of constructing an optimal such tree. One measure for suitability of the construction is the sum of distances from all sources to all other vertices. We show that finding the exact solution in this case in -hard (in the strong sense). We then investigate solutions for some restricted classes of graphs and give efficient algorithms for those. We also consider an alternative measure of goodness for the spanning tree, being the maximum eccentricity of a source. We show that the problem of finding such a minimum eccentricity spanning tree is somewhat easier to solve and give a pseudo-polynomial solution algorithm.

The minimum stretch spanning tree problem for a connected graph $G$ is to find a spanning tree $T$ of $G$ such that the maximum distance in $T$ between two adjacent vertices of $G$ is minimized, where the minimum value is called the tree-stretch of $G$. This paper presents the tree-stretch of a graph constructed by the Cartesian product of two trees. This result is a generalization of the result for the grid graphs obtained by Lin and Lin (L. Lin, Y. Lin, The minimum stretch spanning tree problem for typical graphs, Acta Mathematicae Applicatae Sinica, English Series, 37(3) (2021) 510–522). Then, we give the tree-stretch of the $k$-th power of a tree.

Storyboard consisting of key-frames is a popular format of video summarization as it helps in efficient indexing, browsing and partial or complete retrieval of video. In this paper, we have presented a size constrained storyboard generation scheme. Given the shots i.e. the output of the video segmentation process, the method has two major steps: extraction of appropriate key-frame(s) from each shot and finally, selection of a specified number of key-frames from the set thus obtained. The set of selected key-frames should retain the variation in visual content originally possessed by the video. The number of key-frames or representative frames in a shot may vary depending on the variation in its visual content. Thus, automatic selection of suitable number of representative frames from a shot still remains a challenge. In this work, we propose a novel scheme for detecting the sub-shots, having consistent visual content, from a shot using Wald–Wolfowitz runs test. Then from each sub-shot a frame rendering the highest fidelity is extracted as key-frame. Finally, a spanning tree based novel method is proposed to select a subset of key-frames having specific cardinality. Chronological arrangement of such frames generates the size constrained storyboard. Experimental result and comparative study show that the scheme works satisfactorily for a wide variety of shots. Moreover, the proposed technique rectifies mis-detection error, if any, incurred in video segmentation process. Similarly, though not implemented, the proposed hypothesis test has ability to rectify the false-alarm in shot detection if it is applied on pair of adjacent shots.

In this paper, we introduce the concept of the spanning simplicial complex Δ_s(G) associated to a simple finite connected graph G. We characterize all spanning trees of the uni-cyclic graph U_n,m. In particular, we give a formula for computing the Hilbert series and h-vector of the Stanley-Reisner ring k[Δ_s(U_n,m)]. Finally, we prove that the spanning simplicial complex Δ_s(U_n,m) is shifted and hence is shellable.

Let $F\left(x\right)={\displaystyle {\sum }_{n=1}^{\infty }{\tau }_{s_1,s_2,\dots ,s_k}\left(n\right)x^n}$ be the generating function for the number ${\tau }_{s_1,s_2,\dots ,s_k}\left(n\right)$ of spanning trees in the circulant graph C_n(s₁, s₂, …, s_k). We show that F(x) is a rational function with integer coefficients satisfying the property F(x) = F(1/x). A similar result is also true for the circulant graphs C_2n(s₁, s₂, …, s_k, n) of odd valency. We illustrate the obtained results by a series of examples.

In this paper, we study the enumeration of spanning trees and maximum matchings of the Fibonacci graphs. It is proved that the number of all spanning trees of a Fibonacci graph with $n$ vertices is $(2n-2)$th Fibonacci number. We also obtained a formula for the number of maximum matchings of Fibonacci graphs in terms of Fibonacci numbers.

Let $G=(V,E)$, $V=\{v_1,v_2,\dots ,v_n\}$, be a simple connected graph of order $n$ and size $m$. Denote with ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_{n-1}>{\mu }_n=0$ eigenvalues of the Laplacian matrix $L(G)$ of $G$. The Kirchhoff index and the number of spanning trees of $G$ expressed in terms of Laplacian eigenvalues are given by $\mathrm{\text{Kf}}(G)=n{\sum }_{i=1}^{n-1}\frac{1}{{\mu }_i}$ and $t(G)=\frac{1}{n}{\prod }_{i=1}^{n-1}{\mu }_i$, respectively. The characteristic polynomial of $L(G)$ is given by $\varphi (L(G))={\sum }_{k=0}^n{p}_k{x}^{n-k}$. The first five Laplacian coefficients have been computed in the literature. In this study, we compute the sixth Laplacian coefficient of $G$. Then, we use it to improve the previously obtained results on $\mathrm{\text{Kf}}(G)$ and $t(G)$. In addition, we present new Nordhaus–Gaddum-type inequalities for $\mathrm{\text{Kf}}(G)$ and $t(G)$.

In this paper, we study the infinite graphs which admit a finite dominating set. The main contribution of the work is two folds: (i) characterization of infinite trees and hence infinite connected graphs with a finite dominating set, (ii) it is shown that apart from a family of graphs, all infinite graphs or their complements possess a finite dominating set. Moreover, some conditions of existence of finite dominating sets in product graphs are studied.

Let $G$ be a simple graph with $m$ edges and $H_1$, $H_2,\dots ,H_m$ be $m$ simple graphs. The generalized edge corona, denoted by $G{[H_i]}_1^m$, is the graph obtained by taking one copy of graphs $G$, $H_1$, $H_2,\dots ,H_m$ and then joining two end-vertices of the $i$th edge $e_i$ of $G$ to every vertex of $H_i$ for $1\le i\le m$. In this paper, we determine and study the characteristic polynomial, Laplacian polynomial and signless Laplacian polynomial of $G{[H_i]}_1^m$. As an application, we also count the number of spanning trees of the generalized edge corona.

A $k$-tree is a tree with maximum degree at most $k$. For a graph $G$ and $u,v\in V(G)$ with $uv\notin E(G)$, let $\alpha (u,v;G)$ be the cardinality of a maximum independent set containing $u$ and $v$. For a graph $G$ and $u,v\in V(G)$, the local connectivity $\kappa (u,v;G)$ is defined to be the maximum number of internally disjoint paths connecting $u$ and $v$ in $G$. In this paper, we prove the following theorem and show the condition is sharp. Let $k$, $s$ and $t$ be integers with $k\ge 3$, $0\le s\le k$ and $2\le t\le k$. For any two nonadjacent vertices $u$ and $v$ of $G$, we have $\kappa (u,v;G)\ge s+1$ and $\alpha (u,v;G)\le (\kappa (u,v;G)-s)(k-1)+s(t-1)+1$. Then for any $s$ distinct vertices of $G$, $G$ has a spanning $k$-tree such that each of $s$ specified vertices has degree at most $t$. This theorem implies H. Matsuda and H. Matsumura’s result in [on a $k$-tree containing specified cleares in a graph, Graphs Combin.22 (2006) 371–381] and V. Neumann-Lara and E. Rivera-Campo’s result in [Spanning trees with bounded degrees, Combinatorica11 (1991) 55–61].

We introduce the cycle intersection graph of a graph, an adaptation of the cycle graph of a graph, and use the structure of these graphs to prove an upper bound for the decycling number of all even graphs. This bound is shown to be significantly better when an even graph admits a cycle decomposition in which any two cycles intersect in at most one vertex. Links between the cycle rank of the cycle intersection graph of an even graph and the decycling number of the even graph itself are found. The problem of choosing an ideal cycle decomposition is addressed and is presented as an optimization problem over the space of cycle decompositions of even graphs, and we conjecture that the upper bound for the decycling number of even graphs presented in this paper is best possible.