Search

Your search keyword '"Ghodrati, Amir Hossein"' showing total 14 results
Start Over Author "Ghodrati, Amir Hossein"
14 results on '"Ghodrati, Amir Hossein"'

4. Chromatic Number and Dichromatic Polynomial of Digraphs

Author

Akbari, Saeed, Ghodrati, Amir Hossein, Jabalameli, Afrouz, and Saghafian, Morteza

Subjects
Mathematics - Combinatorics
Abstract

Let $G$ be a graph of order $n$. It is well-known that $\alpha(G)\geq \sum_{i=1}^n \frac{1}{1+d_i}$, where $\alpha(G)$ is the independence number of $G$ and $d_1,\ldots,d_n$ is the degree sequence of $G$. We extend this result to digraphs by showing that if $D$ is a digraph with $n$ vertices, then $ \alpha(D)\geq \sum_{i=1}^n \left( \frac{1}{1+d_i^+} + \frac{1}{1+d_i^-} - \frac{1}{1+d_i}\right)$, where $\alpha(D)$ is the maximum size of an acyclic vertex set of $D$. Golowich proved that for any digraph $D$, $\chi(D)\leq \lceil \frac{4k}{5} \rceil+2$, where $k=max(\Delta^+(D),\Delta^-(D))$. We give a short and simple proof for this result. Next, we investigate the chromatic number of tournaments and determine the unique tournament such that for every integer $k>1$, the number of proper $k$-colorings of that tournament is maximum among all strongly connected tournaments with the same number of vertices. Also, we find the chromatic polynomial of the strongly connected tournament with the minimum number of cycles., Comment: 13 pages

Published
2017

12. Nowhere–zero bases for the nullspace of the incidence matrices of graphs.

Author

Akbari, Saieed, Ghodrati, Amir Hossein, and Shahriari, Shahriar

Subjects
*UNDIRECTED graphs, *COMPLETE graphs, *MATRICES (Mathematics), *LOGICAL prediction, *DIRECTED graphs
Abstract

A nowhere-zero k-flow for a directed or undirected graph is a vector in the nullspace of the incidence matrix of the graph such that all the entries of the vector are from the set { ± 1 , ± 2 , ... , ± (k − 1) }. We consider the problem of finding a basis consisting of nowhere-zero k-flows for the nullspace of the incidence matrix. For a variety of graphs—including the complete graphs—we find such bases with k=2 or k=3. We prove that all directed graphs with no cut-edge have such a basis with k=12, and conjecture that 12 can be replaced with 5. If true, this would strengthen Tutte's celebrated conjecture on nowhere-zero 5-flows. For undirected graphs that have some nowhere-zero k-flow, we prove the existence of a basis of nowhere-zero 36-flows and conjecture that 36 can be replaced with 6. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

14. Equimatchable Regular Graphs.

Author

Akbari, Saieed, Ghodrati, Amir Hossein, Hosseinzadeh, Mohammad Ali, and Iranmanesh, Ali

Subjects
*REGULAR graphs, *GRAPH theory, *MATCHING theory, *ISOMORPHISM (Mathematics), *GEOMETRIC vertices
Abstract

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3-regular graphs are K4 and K3, 3. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r-regular graph, then [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results