Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Fixing number of Functigraphs
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
The fixing number of a graph $G$ is the smallest cardinality of a set of vertices $S$ such that only the trivial automorphism of $G$ fixes every vertex in $S$. The fixing set of a group $Gamma$ is the set of all fixing numbers of finite graphs with automorphism group $Gamma$. Several authors have studied the distinguishing number of a graph, the smallest number of labels needed to label $G$ so that the automorphism group of the labeled graph is trivial. The fixing number can be thought of as a variation of the distinguishing number in which every label may be used only once, and not every vertex need be labeled. We characterize the fixing sets of finite abelian groups, and investigate the fixing sets of symmetric groups.
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.
The fixing number of a graph $G$ is the smallest cardinality of a set of vertices $Fsubseteq V(G)$ such that only the trivial automorphism of $G$ fixes every vertex in $F$. Let $Pi$ $=$ ${F_1,F_2,ldots,F_k}$ be an ordered $k$-partition of $V(G)$. Then $Pi$ is called a {it fixatic partition} if for all $i$; $1leq ileq k$, $F_i$ is a fixing set for $G$. The cardinality of a largest fixatic partition is called the {it fixatic number} of $G$. In this paper, we study the fixatic numbers of graphs. Sharp bounds for the fixatic number of graphs in general and exact values with specified conditions are given. Some realizable results are also given in this paper.
In this paper, we give bounds on the dichromatic number $vec{chi}(Sigma)$ of a surface $Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $Sigma$. We determine the asymptotic behaviour of $vec{chi}(Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1frac{sqrt{-c}}{log(-c)} leq vec{chi}(Sigma) leq a_2 frac{sqrt{-c}}{log(-c)} $ for every surface $Sigma$ with Euler characteristic $cleq -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $mathbb{N}_1$, the Klein bottle $mathbb{N}_2$, the torus $mathbb{S}_1$, and Dycks surface $mathbb{N}_3$ are all equal to $3$, and that the dichromatic numbers of the $5$-torus $mathbb{S}_5$ and the $10$-cross surface $mathbb{N}_{10}$ are equal to $4$. We also consider the complexity of deciding whether a given digraph or oriented graph embedabble in a fixed surface is $k$-dicolourable. In particular, we show that for any surface, deciding whether a digraph embeddable on this surface is $2$-dicolourable is NP-complete, and that deciding whether a planar oriented graph is $2$-dicolourable is NP-complete unless all planar oriented graphs are $2$-dicolourable (which was conjectured by Neumann-Lara).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
