ترغب بنشر مسار تعليمي؟ اضغط هنا

Domination for latin square graphs

86   0   0.0 ( 0 )
 نشر من قبل Michele Torielli
 تاريخ النشر 2019
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

In combinatorics, a latin square is a $ntimes n$ matrix filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Associated to each latin square, we can define a simple graph called a latin square graph. In this article, we compute lower and upper bounds for the domination number and the k-tuple total domination numbers of such graphs. Moreover, we describe a formula for the 2-tuple total domination number.



قيم البحث

اقرأ أيضاً

For a graph $G=(V,E)$, we call a subset $ Ssubseteq V cup E$ a total mixed dominating set of $G$ if each element of $V cup E$ is either adjacent or incident to an element of $S$, and the total mixed domination number $gamma_{tm}(G)$ of $G$ is the min imum cardinality of a total mixed dominating set of $G$. In this paper, we initiate to study the total mixed domination number of a connected graph by giving some tight bounds in terms of some parameters such as order and total domination numbers of the graph and its line graph. Then we discuss on the relation between total mixed domination number of a graph and its diameter. Studing of this number in trees is our next work. Also we show that the total mixed domination number of a graph is equale to the total domination number of a graph which is obtained by the graph. Giving the total mixed domination numbers of some special graphs is our last work.
In this paper, we study the domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph. We also compute the domination number of some families of graphs such as star graphs, double start grap hs, path graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and friendship graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the domination number of middle graphs.
Given a graph $G$, a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$. The domination number of $G$, denoted $gamma(G)$, is the minimum size of a dominating set of $G$. The independent domination n umber of $G$, denoted $i(G)$, is the minimum size of a dominating set of $G$ that is also independent. Note that every graph has an independent dominating set, as a maximal independent set is equivalent to an independent dominating set. Let $G$ be a connected $k$-regular graph that is not $K_{k, k}$ where $kgeq 4$. Generalizing a result by Lam, Shiu, and Sun, we prove that $i(G)le frac{k-1}{2k-1}|V(G)|$, which is tight for $k = 4$. This answers a question by Goddard et al. in the affirmative. We also show that $frac{i(G)}{gamma(G)} le frac{k^3-3k^2+2}{2k^2-6k+2}$, strengthening upon a result of Knor, v{S}krekovski, and Tepeh. In addition, we prove that a graph $G$ with maximum degree at most $4$ satisfies $i(G) le frac{5}{9}|V(G)|$, which is also tight.
Let $P$ be a partial latin square of prime order $p>7$ consisting of three cyclically generated transversals. Specifically, let $P$ be a partial latin square of the form: [ P={(i,c+i,s+i),(i,c+i,s+i),(i,c+i,s+i)mid 0 leq i< p} ] for some distinct $c, c,c$ and some distinct $s,s,s$. In this paper we show that any such $P$ completes to a latin square which is diagonally cyclic.
We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n/g)<3n/10+O(n/g).
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا