Combinatorics (math.CO)

Abstract: For a simple graph $F$, let $\mathrm{EX}(n, F)$ and $\mathrm{EX_{sp}}(n,F)$ be the set of graphs with the maximum number of edges and the set of graphs with the maximum spectral radius in an $n$-vertex graph without any copy of the graph $F$, respectively. Let $F$ be a graph with $\mathrm{ex}(n,F)=e(T_{n,r})+O(1)$. In this paper, we show that $\mathrm{EX_{sp}}(n,kF)\subseteq \mathrm{EX}(n,kF)$ for sufficiently large $n$. This generalizes a result of Wang, Kang and Xue [J. Comb. Theory, Ser. B, 159(2023) 20-41]. We also determine the extremal graphs of $kF$ in term of the extremal graphs of $F$.

Abstract: Computer experiments suggest some conjectures about Hankel determinants of convolution powers of Catalan numbers. Unfortunately, for most of them I have no proofs. I would like to present them anyway hoping that someone finds them interesting and can prove them.

Abstract: The symmetric difference of two graphs $G_1,G_2$ on the same set of vertices $V$ is the graph on $V$ whose set of edges are all edges that belong to exactly one of the two graphs $G_1,G_2$. For a fixed graph $H$ call a collection ${\cal G}$ of spanning subgraphs of $H$ a connectivity code for $H$ if the symmetric difference of any two distinct subgraphs in ${\cal G}$ is a connected spanning subgraph of $H$. It is easy to see that the maximum possible cardinality of such a collection is at most $2^{k'(H)} \leq 2^{\delta(H)}$, where $k'(H)$ is the edge-connectivity of $H$ and $\delta(H)$ is its minimum degree. We show that equality holds for any $d$-regular (mild) expander, and observe that equality does not hold in several natural examples including powers of long cycles and products of a small clique with a long cycle.

Abstract: There is a philosophy to discover Ramsey-type theorem: given a graph parameter $\mu$, characterize the family $\HH$ of graphs which satisfies that every $\HH$-free graph $G$ has bounded parameter $\mu$. The classical Ramsey's theorem deals the parameter $\mu$ as the number of vertices. It also has a corresponding connected version. This Ramsey-type problem on domination number has been solved by Furuya. We will use this result to handle more parameters related to domination.

Abstract: A graph is called uniquely distinguishing colorable if there is only one partition of vertices of the graph that forms distinguishing coloring with the smallest possible colors. In this paper, we study the unique colorability of the distinguishing coloring of a graph and its applications in computing the distinguishing chromatic number of disconnected graphs. We introduce two families of uniquely distinguishing colorable graphs, namely type 1 and type 2, and show that every disconnected uniquely distinguishing colorable graph is the union of two isomorphic graphs of type 2. We obtain some results on bipartite uniquely distinguishing colorable graphs and show that any uniquely distinguishing $n$-colorable tree with $ n \geq 3$ is a star graph. For a connected graph $G$, we prove that $\chi_D(G\cup G)=\chi_D(G)+1$ if and only if $G$ is uniquely distinguishing colorable of type 1. Also, a characterization of all graphs $G$ of order $n$ with the property that $\chi_{D}(G\cup G) = \chi_{D}(G) = k$, where $k=n-2, n-1, n$, is given in this paper. Moreover, we determine all graphs $G$ of order $n$ with the property that $\chi_{D}(G\cup G) = \chi_{D}(G)+1 = \ell$, where $\ell=n-1, n, n+1$. Finally, we investigate the family of connected graphs $G$ with $\chi_{D}(G\cup G) = \chi_{D}(G)+1 = 3$.

Abstract: An $H$-decomposition of a graph $\Gamma$ is a partition of its edge set into subgraphs isomorphic to $H$. A transitive decomposition is a special kind of $H$-decomposition that is highly symmetrical in the sense that the subgraphs (copies of $H$) are preserved and transitively permuted by a group of automorphisms of $\Gamma$. This paper concerns transitive $H$-decompositions of the graph $K_n \Box K_n$ where $H$ is a path. When $n$ is an odd prime, we present a construction for a transitive path decomposition where the paths in the decomposition are arbitrary large.

Abstract: For an arbitrary set or multiset $A$ of positive integers, we associate the $A$-partition function $p_A(n)$ (that is the number of partitions of $n$ whose parts belong to $A$). We also consider the analogue of the $k$-colored partition function, namely, $p_{A,-k}(n)$. Further, we define a family of polynomials $f_{A,n}(x)$ which satisfy the equality $f_{A,n}(k)=p_{A,-k}(n)$ for all $n\in\mathbb{Z}_{\geq0}$ and $k\in\mathbb{N}$. This paper concerns the polynomization of the Bessenrodt--Ono type inequality for $f_{A,n}(x)$: \begin{align*} f_{A,a}(x)f_{A,b}(x)>f_{A,a+b}(x), \end{align*} where $a$ and $b$ are arbitrary positive integers; and delivers some efficient criteria for its solutions. Moreover, we also investigate a few basic properties related to both functions $f_{A,n}(x)$ and $f_{A,n}'(x)$.

Abstract: We consider two types of joins of graphs $G_{1}$ and $G_{2}$, $G_{1}\veebar G_{2}$ - the Neighbors Splitting Join and $G_{1}\underset{=}{\lor}G_{2}$ - the Non Neighbors Splitting Join, and compute the adjacency characteristic polynomial, the Laplacian characteristic polynomial and the signless Laplacian characteristic polynomial of these joins. When $G_{1}$ and $G_{2}$ are regular, we compute the adjacency spectrum, the Laplacian spectrum, the signless Laplacian spectrum of $G_{1}\underset{=}{\lor}G_{2}$ and the normalized Laplacian spectrum of $G_{1}\veebar G_{2}$ and $G_{1}\underset{=}{\lor}G_{2}$. We use these results to construct non regular, non isomorphic graphs that are cospectral with respect to the four matrices: adjacency, Laplacian , signless Laplacian and normalized Laplacian.

Abstract: The Clebsch--Gordan coefficients of $U(\mathfrak{sl}_2)$ are expressible in terms of Hahn polynomials. The phenomenon can be explained by an algebra homomorphism from the universal Hahn algebra $\mathcal H$ into $U(\mathfrak{sl}_2)\otimes U(\mathfrak{sl}_2)$. Let $\Omega$ denote a finite set and $2^\Omega$ denote the power set of $\Omega$. It is generally known that $\mathbb C^{2^\Omega}$ supports a $U(\mathfrak{sl}_2)$-module. Fix an element $x_0\in 2^\Omega$. By the linear isomorphism $\mathbb C^{2^\Omega}\to \mathbb C^{2^{\Omega\setminus x_0}}\otimes \mathbb C^{2^{x_0}}$ given by $x\mapsto (x\setminus x_0)\otimes (x\cap x_0)$ for all $x\in 2^\Omega$, this induces a $U(\mathfrak{sl}_2)\otimes U(\mathfrak{sl}_2)$-module structure on $\mathbb C^{2^\Omega}$. Pulling back via the algebra homomorphism $\mathcal H\to U(\mathfrak{sl}_2)\otimes U(\mathfrak{sl}_2)$, the $U(\mathfrak{sl}_2)\otimes U(\mathfrak{sl}_2)$-module $\mathbb C^{2^\Omega}$ forms an $\mathcal H$-module. The $\mathcal H$-module $\mathbb C^{2^\Omega}$ enfolds the Terwilliger algebra of a Johnson graph. This result connects these two seemingly irrelevant topics: The Clebsch--Gordan coefficients of $U(\mathfrak{sl}_2)$ and the Terwilliger algebras of Johnson graphs. Unfortunately some steps break down in the $q$-analog case. By making detours, the imperceptible connection between the Clebsch--Gordan coefficients of $U_q(\mathfrak{sl}_2)$ and the Terwilliger algebras of Grassmann graphs is successfully disclosed in this paper.

Abstract: A well-known bijection between Motzkin paths and ordered trees with outdegree always $\le2$, is lifted to Grand Motzkin paths (the nonnegativity is dropped) and an ordered list of an odd number of such $\{0,1,2\}$ trees. This offers an alternative to a recent paper by Rocha and Pereira Spreafico.