Aysel Erey
YOU?
Author Swipe
View article: Spreading in graphs
Spreading in graphs Open
Several concepts that model processes of spreading (of information, disease, objects, etc.) in graphs or networks have been studied. In many contexts, we assume that some vertices of a graph $G$ are contaminated initially, before the proce…
View article: On the average order of a dominating set of a forest
On the average order of a dominating set of a forest Open
We show that the average order of a dominating set of a forest graph $G$ on $n$ vertices with no isolated vertices is at most $2n/3$. Moreover, the equality is achieved if and only if every non-leaf vertex of $G$ is a support vertex with o…
View article: Tomescu's graph coloring conjecture for $\ell$-connected graphs
Tomescu's graph coloring conjecture for $\ell$-connected graphs Open
Let $P_G(k)$ be the number of proper $k$-colorings of a finite simple graph $G$. Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that $P_G(k) \le k!(k-1)^{n-k}$ for all connected graphs $G$ on $n$ vertices w…
View article: Length Uniformity in Legal Dominating Sequences
Length Uniformity in Legal Dominating Sequences Open
A sequence of vertices $(v_1,\, \dots , \,v_k)$ of a graph $G$ is called a {\it legal dominating sequence} if $\{v_1,\, \dots , \,v_k\}$ is a dominating set of $G$ and $N[v_i]\nsubseteq \cup _{j=1}^{i-1} N[v_j]$ for every $i$. A graph $G$ …
View article: On the maximum number of colorings of a graph
On the maximum number of colorings of a graph Open
Let $\mathcal{C}_k(n)$ be the family of all connected $k$-chromatic graphs of order $n$. Given a natural number $x\geq k$, we consider the problem of finding the maximum number of $x$-colorings among graphs in $\mathcal{C}_k(n)$. When $k\l…
View article: Characterization and enumeration of 3-regular permutation graphs
Characterization and enumeration of 3-regular permutation graphs Open
A permutation graph is a graph that can be derived from a permutation, where the vertices correspond to letters of the permutation, and the edges represent inversions. We provide a construction to show that there are infinitely many connec…
View article: A note on the real part of complex chromatic roots
A note on the real part of complex chromatic roots Open
A {\em chromatic root} is a root of the chromatic polynomial of a graph. While the real chromatic roots have been extensively studied and well understood, little is known about the {\em real parts} of chromatic roots. It is not difficult t…
View article: New Bounds for Chromatic Polynomials and Chromatic Roots
New Bounds for Chromatic Polynomials and Chromatic Roots Open
If $G$ is a $k$-chromatic graph of order $n$ then it is known that the chromatic polynomial of $G$, $π(G,x)$, is at most $x(x-1)\cdots (x-(k-1))x^{n-k} = (x)_{\downarrow k}x^{n-k}$ for every $x\in \mathbb{N}$. We improve here this bound by…
View article: Restraints Permitting the Largest Number of Colourings
Restraints Permitting the Largest Number of Colourings Open
A \textit{restraint} $r$ on $G$ is a function which assigns each vertex $v$ of $G$ a finite set of forbidden colours $r(v)$. A proper colouring $c$ of $G$ is said to be \textit{permitted by the restraint r} if $c(v)\notin r(v)$ for every v…
View article: On the real roots of $\sigma$-Polynomials
On the real roots of $\sigma$-Polynomials Open
The $\\sigma$-polynomial is given by $\\sigma(G,x) = \\sum_{i=\\chi(G)}^{n}\na_{i}(G)\\, x^{i}$, where $a_{i}(G)$ is the number of partitions of the vertices\nof $G$ into $i$ nonempty independent sets. These polynomials are closely\nrelate…
View article: On the real roots of $σ$-Polynomials
On the real roots of $σ$-Polynomials Open
The $σ$-polynomial is given by $σ(G,x) = \sum_{i=χ(G)}^{n} a_{i}(G)\, x^{i}$, where $a_{i}(G)$ is the number of partitions of the vertices of $G$ into $i$ nonempty independent sets. These polynomials are closely related to chromatic polyno…
View article: Extremal Restraints for Graph Colourings
Extremal Restraints for Graph Colourings Open
A {\em restraint} on a (finite undirected) graph $G = (V,E)$ is a function $r$ on $V$ such that $r(v)$ is a finite subset of ${\mathbb N}$; a proper vertex colouring $c$ of $G$ is {\em permitted} by $r$ if $c(v) \not\in r(v)$ for all verti…
View article: On the Wiener index, distance cospectrality and transmission regular graphs
On the Wiener index, distance cospectrality and transmission regular graphs Open
In this paper, we investigate various algebraic and graph theoretic properties of the distance matrix of a graph. Two graphs are $D$-cospectral if their distance matrices have the same spectrum. We construct infinite pairs of $D$-cospectra…