Combinatorics

Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let $ S_n $ denote the set of all permutations of $ [n]=\set{1,2,\ldots,n} $. Let $ i(\pi) $ and $ d(\pi) $ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $ \pi $. Let $ X(\pi) $ denote the set of subsequences of $ \pi $ with length at least three. Let $ t(\pi) $ denote $ \sum_{\tau\in X(\pi)}(i(\tau)+d(\tau)) $.

A permutation $ \pi\in S_n $ is called a Roller Coaster permutation if $ t(\pi)=\max_{\tau\in S_n}t(\tau) $. Let $ RC(n) $ be the set of all Roller Coaster permutations in $ S_n $.

Conjecture   For $ n\geq 3 $,
    \item If $ n=2k $, then $ |RC(n)|=4 $. \item If $ n=2k+1 $, then $ |RC(n)|=2^j $ with $ j\leq k+1 $.
Conjecture  (Odd Sum conjecture)   Given $ \pi\in RC(n) $,
    \item If $ n=2k+1 $, then $ \pi_j+\pi_{n-j+1} $ is odd for $ 1\leq j\leq k $. \item If $ n=2k $, then $ \pi_j + \pi_{n-j+1} = 2k+1 $ for all $ 1\leq j\leq k $.

Keywords:

Posted by Tanbir Ahmed
updated October 14th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Total Dominator Chromatic Number of a Hypercube ★★

Author(s): Adel P. Kazemi

Conjecture   For any integer $ n\geq 5 $, $ \chi_d^t(Q_n)=2^{n-2}+2 $.

Keywords: Total dominator chromatic number, hypercube.

Posted by Adel P. Kazemi
updated November 1st, 2014
1 comment
Graph Theory » Basic G.T.

Total Domination number of a hypercube ★★★

Author(s): Adel P. Kazemi

Conjecture   For any integer $ n\geq 6 $, $ \gamma_t(Q_n) = 2^{n-2} $.

Keywords: Total domination number, Hypercube

Posted by Adel P. Kazemi
updated November 30th, 2013
1 comment