فهرست مطالب

Transactions on Combinatorics - Volume:8 Issue:1, 2019
  • Volume:8 Issue:1, 2019
  • تاریخ انتشار: 1397/12/10
  • تعداد عناوین: 5
|
  • Hasan Kharazi, Alireza Mosleh Tehrani * Pages 1-14
    ‎Let $ G = (V,E) $ be a graph‎. ‎We say that $ S subseteq V $ is a defensive alliance if for every $ u in S $‎, ‎the number of neighbors $ u $ has in $ S $ plus one (counting $ u $) is at least as large as the number of neighbors it has outside $ S $‎. ‎Then‎, ‎for every vertex $ u $ in a defensive alliance $ S $‎, ‎any attack on a single vertex by the neighbors of $ u $ in $ V-S $ can be thwarted by the neighbors of $ u $ in $ S $ and $ u $ itself‎. ‎In this paper‎, ‎we study alliances that are containing a given vertex $ u $ and study their mathematical properties‎.
    Keywords: ‎Defensive alliance, Alliances in graphs, Edge cut
  • Majid Arezoomand *, Alireza Abdollahi, Pablo Spiga Pages 15-40
    Fixed-point-free permutations‎, ‎also known as derangements‎, ‎have been studied for centuries‎. ‎In particular‎, ‎depending on their applications‎, ‎derangements of prime-power order and of prime order have always played a crucial role in a variety of different branches of mathematics‎: ‎from number theory to algebraic graph theory‎. ‎Substantial progress has been made on the study of derangements‎, ‎many long-standing open problems have been solved‎, ‎and many new research problems have arisen‎. ‎The results obtained and the methods developed in this area have also effectively been used to solve other problems regarding finite vertex-transitive graphs‎. ‎The methods used in this area range from deep group theory‎, ‎including the classification of the finite simple groups‎, ‎to combinatorial techniques‎. ‎This article is devoted to surveying results‎, ‎open problems and methods in this area‎.
    Keywords: ‎‎Derangements‎, ‎Polycirculant Conjecture‎, ‎Transitive group
  • Ebrahim Vatandoost *, Fatemeh Ramezani, Saeid Alikhani Pages 41-50
    In this article we study the Zero forcing number of Generalized Sierpi'{n}ski graphs $S(G,t)$‎. ‎More precisely‎, ‎we obtain a general lower bound on the Zero forcing number of $S(G,t)$ and we show that this bound is tight‎. ‎In particular‎, ‎we consider the cases in which the base graph $G$ is a star‎, ‎path‎, ‎a cycle or a complete graph‎.
    Keywords: ‎Zero forcing number‎, ‎generalized Sierpi&#039, {n}ski graph‎, ‎Sierpi&#039, {n}ski graph‎, ‎path covering
  • Hamidreza Maimani *, Zeinab Koushki Pages 51-59
    A set $D$ of vertices of graph $G$ is called $double$ $dominating$ $set$ if for any vertex $v$, $|N[v]cap D|geq 2$. The minimum cardinality of $double$ $domination$ of $G$ is denoted by $gamma_d(G)$. The minimum number of edges $E'$ such that $gamma_d(Gsetminus E)>gamma_d(G)$ is called the double bondage number of $G$ and is denoted by $b_d(G)$. This paper determines that $b_d(Gvee H)$ and exact values of $b(P_ntimes P_2)$, and generalized corona product of graphs.
    Keywords: bondage number, double domination, double bondage number
  • Mostafa Momeni *, Ali Zaeembashi Pages 61-68
    Let $G$ be a graph‎. ‎A function $f‎ : ‎V (G) longrightarrow {0,1}$‎, ‎satisfying‎ ‎the condition that every vertex $u$ with $f(u) = 0$ is adjacent with at‎ ‎least one vertex $v$ such that $f(v) = 1$‎, ‎is called a dominating function $(DF)$‎. ‎The weight of $f$ is defined as $wet(f)=Sigma_{v in V(G)} f(v)$‎. ‎The minimum weight of a dominating function of $G$‎ ‎is denoted by‎ ‎$gamma (G)$‎, ‎and is called the domination number of $G$‎. ‎A dominating‎ ‎function $f$ is called a global dominating function $(GDF)$ if $f$ is‎ ‎also a $DF$ of $overline{G}$‎. ‎The minimum weight of a global dominating function is denoted by‎ ‎$gamma_{g}(G)$ and is called global domination number of $G$‎. ‎In this paper we introduce a generalization of global dominating function‎. ‎Suppose $G$ is a graph and $sgeq 2$ and $K_n$ is the complete graph on $V(G)$‎. ‎A function $ f:V(G)longrightarrow { 0,1} $ on $G$ is $s$-dominating function $(s-DF)$‎, ‎if there exists some factorization ${G_1,ldots,G_s }$ of $K_n$‎, ‎such that $G_1=G$ and $f$ is dominating function of each $G_i$‎.
    Keywords: ‎‎dominating function‎, ‎global dominating function‎, ‎$s$-dominating function‎, ‎$gamma-$function‎, ‎$gamma, s-$function