Let n, a1 , . . . , ak be distinct positive integers. A finite Toeplitz graph Tn (a1 , . . . , ak ) = (V , E ) is a graph where V = {v0 , . . . , vn-1 } and E = {(vi , vj ) : |i - j| ? {a1 , . . . , ak }}. In this paper, we characterize bipartite finite Toeplitz graphs with k <= 3. In most cases, the characterization takes O(log a3 ) arithmetic steps; in the remaining cases, it takes O(a1 ). A consequence of the proposed results is the complete characterization of the chromatic number of finite Toeplitz graphs with k <= 3. In addition, we characterize some classes of infinite bipartite Toeplitz graphs with k >= 4.
Bipartite finite Toeplitz graphs
SNicoloso;
2014
Abstract
Let n, a1 , . . . , ak be distinct positive integers. A finite Toeplitz graph Tn (a1 , . . . , ak ) = (V , E ) is a graph where V = {v0 , . . . , vn-1 } and E = {(vi , vj ) : |i - j| ? {a1 , . . . , ak }}. In this paper, we characterize bipartite finite Toeplitz graphs with k <= 3. In most cases, the characterization takes O(log a3 ) arithmetic steps; in the remaining cases, it takes O(a1 ). A consequence of the proposed results is the complete characterization of the chromatic number of finite Toeplitz graphs with k <= 3. In addition, we characterize some classes of infinite bipartite Toeplitz graphs with k >= 4.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
