34 results
Showing 1–20 · 0.16 seconds · RSS
The American Journal of Combinatorics
ISSN 2768-4202 · American Journal of Combinatorics · 34 articles in the index
-
Journal Article
Vacillating Parking Functions and the Fibonacci Numbers
Vacillating parking functions are parking functions in which a car only tolerates parking in its preferred spot, in the spot behind its preferred spot, or in the spot ahead of its preferred spot, which they check precisely in that order. Our main result characterizes the possible permutations that…
-
Journal Article
Sparse paving positroids
Using Postnikov's Le-diagrams, decorated permutations, and Grassmann necklaces, we classify which positroids are sparse paving matroids. This allows us to enumerate sparse paving positroids, making connections to a known sequence involving the golden ratio and to the Lucas numbers.
-
Journal Article
Ordered trees with distinguished children
A new tree model is introduced based on ordered trees, by distinguishing exactly one child of each node that has children. The basic enumeration leads to a cubic equation of the generating function. The extraction of its coefficients can be done using the Lagrange inversion formula. Various…
-
Journal Article
On outer-convex Roman dominating function in graphs
Let \(G = (V(G), E(G))\) be a connected graph and let \(\phi:V(G)\rightarrow \{0,1,2\}\) be a Roman dominating function (RDF) on \(G\). For each \(j \in \{0, 1, 2\}\), let \(V_j=\{x \in V(G): \phi(x)=j\}\). Then \(\phi\) can be represented as \(\phi=(V_0, V_1, V_2)\). A function \(\phi\) is an…
-
Journal Article
Enumeration of odd-dimensional partitions modulo 4
The number of standard Young tableaux on a partition shape \(\lambda\) is called the dimension of the partition. Partitions with odd dimensions were enumerated by McKay and were further characterized by Macdonald in the 1970s. Let \(a_i(n)\) be the number of partitions of \(n\) with dimension…
-
Journal Article
Generalization of a formula for marked plane trees
Deutsch, Munarin and Rinaldi derived a formula for counting marked plane trees while investigating the enumeration of skew Dyck paths. The formula involves the Catalan numbers, which count plane trees among other classical combinatorial structures. In this paper, we generalize their result by…
-
Journal Article
Very strongly connected graphs
A simple connected graph is strongly connected if there exists a directed path between every pair of vertices in both directions. Robbins showed that every \(2\)-edge-connected graph can be given edge orientations that result in the graph being strongly connected. But a random assignment of edge…
-
Journal Article
Eigenspaces for \(-2\) in signed line graphs
It is known that \(-2\) appears in the spectrum of a connected signed line graph if and only if its root is either (a) a balanced signed graph, not a tree, that spans a switching of the complete signed graph or (b) an unbalanced simply signed graph, not a unicyclic simply signed graph, that spans a…
-
Journal Article
Automorphisms of the generalized cluster complex
We exhibit a dihedral symmetry in the generalized cluster complex defined by Fomin and Reading. Together with diagram symmetries, they generate the automorphism group of the complex. A consequence is a simple explicit formula for the order of this automorphism group.
-
Journal Article
Pullback parking functions
We introduce a generalization of parking functions in which cars are limited in their movement backwards and forwards by two nonnegative integer parameters \(k\) and \(\ell\), respectively. In this setting, there are \(n\) spots on a one-way streetand \(m\) cars attempting to park in those spots…
-
Journal Article
On the geometry of stack-sorting simplices
We show that all stack-sorting polytopes are simplices. Furthermore, we show that the stack-sorting polytopes generated from permutations of the form \(Ln1\) have relative volume 1. We establish an upper bound for the number of lattice points in a stack-sorting polytope. In particular…
-
Journal Article
The \(\mathscr{G}\)-average of adjacency and Laplacian polynomials of a graph
Let \(\mathscr{G}\) be a finite multiplicative group of quaternion unit \(U(\mathbb{H})\). The \(\mathscr{G}\)-average of adjacency (resp., Laplacian) polynomial of a graph \(G\) is defined as the arithmetic mean of the characteristic polynomials of adjacency (resp., Laplacian) matrice of all…
-
Journal Article Full text
The nullity of the net Laplacian matrix of a signed graph
The net Laplacian matrix of a signed graph \(\Gamma = (G, \sigma)\), where \(G = (V(G),E(G))\) is an unsigned graph (referred to as the underlying graph) and \(\sigma: E(G) \rightarrow \{-1, +1\}\) is the sign function, is defined as \(L^{\pm}(\Gamma) = D^{\pm}(\Gamma) - A(\Gamma)\). Here…
Also available at: DOAJ
-
Journal Article
Computing the degree of some matchings in a graph
Let \(G\) be a connected graph. A matching \(M\) in \(G\) is a set of edges of \(G\) without two of them adjacent (having a common vertex). The graph whose vertices are the matchings in \(G\) and two matchings \(M\) and \(N\) are adjacent if and only if \( (M\setminus N)\cup (N\setminus M)\) is the…
-
Journal Article
A note on the minimum rank of graphs with given dominating induced subgraph
An induced subgraph of a graph \(G\) is said to be dominating if every vertex of \(G\) is at distance at most one from this subgraph. We investigate pairs \((G, F)\) where \(F\) is a non-singular dominating induced subgraph of \(G,\) and the rank of \(G\) (that is, the rank of its adjacency matrix)…
-
Journal Article
Computing the permanental polynomial of 4k-intercyclic bipartite graphs
Let \(G\) be a bipartite graph with adjacency matrix \(A(G)\). The characteristic polynomial \(\phi(G,x)=\det(xI-A(G))\) and the permanental polynomial \(\pi(G,x) = \operatorname{per}(xI-A(G))\) are both graph invariants used to distinguish graphs. For bipartite graphs, we define the modified…
-
Journal Article
On the Min4PC Matrix of a Tree
The Four point condition (abbreviated as 4PC) is a condition used to test if a given distance matrix arises from shortest path distances on trees. From a tree \(T\), Bapat and Sivasubramanian defined a matrix \(\operatorname{Min4PC}_T\) based on this condition. They also gave a basis \(B\) for the…
-
Journal Article
Eigenvalues of multipart matrices and their applications
A square matrix is called a multipart matrix if all its diagonal entries are zero and all other entries in each column are constant. In this paper, we describe various interesting spectral properties of multipart matrices. We provide suitable bounds for the spectral radius of a multipart matrix…
-
Journal Article
Incidence and Laplacian matrices of wheel graphs and their inverses
It has been an open problem to find the Moore-Penrose inverses of the incidence, Laplacian, and signless Laplacian matrices of families of graphs except trees and unicyclic graphs. Since the inverse formulas for an odd unicyclic graph and an even unicyclic graph are quite different, we consider…