Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Distinguishing number of Functigraphs
141
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $G_{1}$ and $G_{2}$ be disjoint copies of a graph $G$, and let $g:V(G_{1})rightarrow V(G_{2})$ be a function. A functigraph $F_{G}$ consists of the vertex set $V(G_{1})cup V(G_{2})$ and the edge set $E(G_{1})cup E(G_{2})cup {uv:g(u)=v}$. In this paper, we extend the study of the distinguishing number of a graph to its functigraph. We discuss the behavior of the distinguishing number in passing from $G$ to $F_{G}$ and find its sharp lower and upper bounds. We also discuss the distinguishing number of functigraphs of complete graphs and join graphs.
rate research
Read More
The fixing number of a graph $G$ is the order of the smallest subset $S$ of its vertex set $V(G)$ such that stabilizer of $S$ in $G$, $Gamma_{S}(G)$ is trivial. Let $G_{1}$ and $G_{2}$ be disjoint copies of a graph $G$, and let $g:V(G_{1})rightarrow V(G_{2})$ be a function. A functigraph $F_{G}$ consists of the vertex set $V(G_{1})cup V(G_{2})$ and the edge set $E(G_{1})cup E(G_{2})cup {uv:v=g(u)}$. In this paper, we study the behavior of the fixing number in passing from $G$ to $F_{G}$ and find its sharp lower and upper bounds. We also study the fixing number of functigraphs of some well known families of graphs like complete graphs, trees and join graphs.
The edge-distinguishing chromatic number (EDCN) of a graph $G$ is the minimum positive integer $k$ such that there exists a vertex coloring $c:V(G)to{1,2,dotsc,k}$ whose induced edge labels ${c(u),c(v)}$ are distinct for all edges $uv$. Previous work has determined the EDCN of paths, cycles, and spider graphs with three legs. In this paper, we determine the EDCN of petal graphs with two petals and a loop, cycles with one chord, and spider graphs with four legs. These are achieved by graph embedding into looped complete graphs.
We show that, in an alphabet of $n$ symbols, the number of words of length $n$ whose number of different symbols is away from $(1-1/e)n$, which is the value expected by the Poisson distribution, has exponential decay in $n$. We use Laplaces method for sums and known bounds of Stirling numbers of the second kind. We express our result in terms of inequalities.
A graph polynomial $P$ is weakly distinguishing if for almost all finite graphs $G$ there is a finite graph $H$ that is not isomorphic to $G$ with $P(G)=P(H)$. It is weakly distinguishing on a graph property $mathcal{C}$ if for almost all finite graphs $Ginmathcal{C}$ there is $H in mathcal{C}$ that is not isomorphic to $G$ with $P(G)=P(H)$. We give sufficient conditions on a graph property $mathcal{C}$ for the characteristic, clique, independence, matching, and domination and $xi$ polynomials, as well as the Tutte polynomial and its specialisations, to be weakly distinguishing on $mathcal{C}$. One such condition is to be addable and small in the sense of C. McDiarmid, A. Steger and D. Welsh (2005). Another one is to be of genus at most $k$.
A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such coloring. The distinguishing threshold of $G$, denoted by $theta(G)$, is the minimum number $k$ such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $theta(G)$, find its relation to the cycle structure of the automorphism group of $G$ and prove that $theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $overline{K_n}$. Finally, we consider the graphs in the Johnson scheme for their distinguishing numbers and thresholds.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
