ORIGINAL_ARTICLE
On the complexity of the colorful directed paths in vertex coloring of digraphs
The colorful paths and rainbow paths have been considered by several authors. A colorful directed path in a digraph $G$ is a directed path with $\chi(G)$ vertices whose colors are different. A $v$-colorful directed path is such a directed path, starting from $v$. We prove that for a given $3$-regular triangle-free digraph $G$ determining whether there is a proper $\chi(G)$-coloring of $G$ such that for every $v \in V (G)$, there exists a $v$-colorful directed path is $ \mathbf{NP} $-complete.
http://toc.ui.ac.ir/article_2840_6a5c24f33fd5a66915e473e2c44ca4aa.pdf
2013-06-01T11:23:20
2019-02-22T11:23:20
1
7
10.22108/toc.2013.2840
Colorful Directed Paths
Computational Complexity
Vertex Coloring
S.
Saqaeeyan
true
1
Abadan Branch, Islamic Azad University
Abadan Branch, Islamic Azad University
Abadan Branch, Islamic Azad University
LEAD_AUTHOR
Esmaeil
Mollaahmadi
mollaahmadi@gmail.com
true
2
Sharif University of Technology .
Sharif University of Technology .
Sharif University of Technology .
AUTHOR
Ali
Dehghan
ali_dehghan16@aut.ac.ir
true
3
Amirkabir University of Technology, Tehran, Iran
Amirkabir University of Technology, Tehran, Iran
Amirkabir University of Technology, Tehran, Iran
AUTHOR
ORIGINAL_ARTICLE
Convolutional cylinder-type block-circulant cycle codes
In this paper, we consider a class of column-weight two quasi-cyclic low-density parity check codes in which the girth can be large enough, as an arbitrary multiple of 8. Then we devote a convolutional form to these codes, such that their generator matrix can be obtained by elementary row and column operations on the parity-check matrix. Finally, we show that the free distance of the convolutional codes is equal to the minimum distance of
their block counterparts.
http://toc.ui.ac.ir/article_2848_9c85537997b5b347da497a3d38139266.pdf
2013-06-01T11:23:20
2019-02-22T11:23:20
9
17
10.22108/toc.2013.2848
LDPC codes
convolutional codes
Girth
Mohammad
Gholami
gholamimoh@gmail.com
true
1
Shahrekord University
Shahrekord University
Shahrekord University
LEAD_AUTHOR
Mehdi
Samadieh
m.samadieh@mathhouse.org
true
2
Isfahan Mathematics House
Isfahan Mathematics House
Isfahan Mathematics House
AUTHOR
ORIGINAL_ARTICLE
On schemes originated from Ferrero pairs
The Frobenius complement of a given Frobenius group acts on its kernel. The scheme which is arisen from the orbitals of this action is called Ferrero pair scheme. In this paper, we show that the fibers of a Ferrero pair scheme consist of exactly one singleton fiber and every two fibers with more than one point have the same cardinality. Moreover, it is shown that the restriction of a Ferrero pair scheme on each fiber is isomorphic to a regular scheme. Finally, we prove that for any prime $p$, there exists a Ferrero pair $p$-scheme, and if $p> 2$, then the Ferrero pair $p$-schemes of the same rank are all isomorphic.
http://toc.ui.ac.ir/article_2869_9eaaa1dafa631de15cb2c9f513a98e5c.pdf
2013-06-01T11:23:20
2019-02-22T11:23:20
19
26
10.22108/toc.2013.2869
Frobenius group
Oribtal
Scheme
Hossein
Moshtagh
moshtagh@dena.kntu.ac.ir
true
1
Department of
Mathematics, K. N. Toosi University of Technology,
Department of
Mathematics, K. N. Toosi University of Technology,
Department of
Mathematics, K. N. Toosi University of Technology,
AUTHOR
Amir
Rahnamai Barghi
rahnama@kntu.ac.ir
true
2
K. N. Toosi university of Technology University, Tehran-Iran.
K. N. Toosi university of Technology University, Tehran-Iran.
K. N. Toosi university of Technology University, Tehran-Iran.
LEAD_AUTHOR
ORIGINAL_ARTICLE
On the number of cliques and cycles in graphs
We give a new recursive method to compute the number of cliques and cycles of a graph. This method is related, respectively to the number of disjoint cliques in the complement graph and to the sum of permanent function over all principal minors of the adjacency matrix of the graph. In particular, let $G$ be a graph and let $\overline {G}$ be its complement, then given the chromatic polynomial of $\overline {G}$, we give a recursive method to compute the number of cliques of $G$. Also given the adjacency matrix $A$ of $G$ we give a recursive method to compute the number of cycles by computing the sum of permanent function of the principal minors of $A$. In both cases we confront to a new computable parameter which is defined as the number of disjoint cliques in $G$.
http://toc.ui.ac.ir/article_2872_183b76bba4970596525b994ca1ef4997.pdf
2013-06-01T11:23:20
2019-02-22T11:23:20
27
33
10.22108/toc.2013.2872
graph
cycle
Clique
Masoud
Ariannejad
m.ariannejad@gmail.com
true
1
University of zanjan
University of zanjan
University of zanjan
LEAD_AUTHOR
Mojgan
Emami
mojgan.emami@yahoo.com
true
2
Department of Mathematics, University of Zanjan
Department of Mathematics, University of Zanjan
Department of Mathematics, University of Zanjan
AUTHOR
ORIGINAL_ARTICLE
Probabilistic analysis of the first Zagreb index
In this paper we study the first Zagreb index in bucket recursive trees containing buckets with variable capacities. This model was introduced by Kazemi in 2012. We obtain the mean and variance of the first Zagreb index and introduce a martingale based on this quantity.
http://toc.ui.ac.ir/article_2881_e4d82056fd1c36fd883f73551fe4a60f.pdf
2013-06-01T11:23:20
2019-02-22T11:23:20
35
40
10.22108/toc.2013.2881
Bucket recursive trees with variable capacities
of buckets
Zagreb index
martingale
Ramin
Kazemi
kazemi@ikiu.ac.ir
true
1
Department of statistics, Imam Khomeini International University, Qazvin
Department of statistics, Imam Khomeini International University, Qazvin
Department of statistics, Imam Khomeini International University, Qazvin
LEAD_AUTHOR
ORIGINAL_ARTICLE
On the spectra of reduced distance matrix of dendrimers
Let $G$ be a simple connected graph and $\{v_1,v_2,\ldots, v_k\}$ be the set of pendent (vertices of degree one) vertices of $G$. The reduced distance matrix of $G$ is a square matrix whose $(i,j)$-entry is the topological distance between $v_i$ and $v_j$ of $G$. In this paper, we obtain the spectrum of the reduced distance matrix of regular dendrimers.
http://toc.ui.ac.ir/article_2890_73b2bef50330eda9f10bd13a01debf78.pdf
2013-06-01T11:23:20
2019-02-22T11:23:20
41
46
10.22108/toc.2013.2890
Reduced distance matrix
spectrum
Regular Dendrimers
Abbas
Heydari
a-heidari@iau-arak.ac.ir
true
1
staff
staff
staff
LEAD_AUTHOR
ORIGINAL_ARTICLE
Modular chromatic number of $C_m \square P_n$
A modular $k\!$-coloring, $k\ge 2,$ of a graph $G$ is a coloring of the vertices of $G$ with the elements in $\mathbb{Z}_k$ having the property that for every two adjacent vertices of $G,$ the sums of the colors of their neighbors are different in $\mathbb{Z}_k.$ The minimum $k$ for which $G$ has a modular $k\!$-coloring is the modular chromatic number of $G.$ Except for some special cases, modular chromatic number of $C_m\square P_n$ is determined.
http://toc.ui.ac.ir/article_2943_5fa15d9e433e3cf4e5d1849c0214c4df.pdf
2013-06-01T11:23:20
2019-02-22T11:23:20
47
72
10.22108/toc.2013.2943
modular coloring
modular chromatic number
Cartesian product
N.
Paramaguru
true
1
Annamalai University
Annamalai University
Annamalai University
AUTHOR
R.
Sampathkumar
true
2
Annamalai University
Annamalai University
Annamalai University
AUTHOR