جستجوی مقالات مرتبط با کلیدواژه « Independent Set » در نشریات گروه « علوم پایه »

In a graph G=(V,E), an independent set I(G) is a subset of the vertices of G such that no two vertices in I(G) are adjacent. Any maximum independent set of a graph is called a diagonal of the graph. Let c be a proper (r+1)-coloring of an r-regular graph G. A vertex v in G is said to be rainbow with respect to c if every color appears in the closed neighborhood N[v]=N(v)∪{v}. Given a diagonal I of G, the coloring c is said to be silver with respect to I if every v∈I is rainbow with respect to c. G is called silver if it admits a silver coloring with respect to some diagonal. In [1], the authors introduced silver coloring and the following question is raised “Find classes of r-regular graphs G, that G is a silver graph". This paper is aimed toward study this question for the generalized Petersen graphs. In this paper we show that, if n≡0 (mod4) and k is odd, then P(n,k) is a totally silver graph. Also, for every natural number n, the existence of silver coloring for generalized Petersen graphs P(n,1), P(n,2) except for n=5, this is well-known petersen graph, P(n,3) except for n=10,14 and 26. Also, for any k>2,P(2k+1,k), and for any k>3,P(3k+1,k), and for any k>3, k ≠5,9 P(3k-1,k) are silver graphs.

The unit disk graph is used to model a wireless sensor network when all sensors have the same communication radius. Hence, the following two optimization problems have been investigated by the researchers: maximal independent set in the network and minimal network dominating set. Since these problems are Np-hard, several algorithms have been presented for their approximation. In this paper, we have presented a honeycomb graph and algorithmic matrix methods for approximating the maximal independent set in the network. Finally, we have confirmed the validity of the algorithm and its complexity and studied it with a numerical example. Keywords: Wireless network, Independent set, Dominating set, Algorithm, Honeycomb network E. Leeuwen, Approximation Algorithms for Unit Disk Graphs, technical report, institute of information and computing sciences, utrecht university, (2004), UU-CS-2004-066. N. Bourgeois, F. Della Croce, B. Escoffier. V.Th. Paschos, Fast algorithms for min independent dominating set, Discrete Applied Mathematics 161, (2013), pp. 558-572

In this paper we initialize the study of independent domination in directed graphs. We show that an independent dominating set of an orientation of a graph is also an independent dominating set of the underlying graph, but that the converse is not true in general. We then prove existence and uniqueness theorems for several classes of digraphs including orientations of complete graphs, paths, trees, DAGs, cycles, and bipartite graphs. We also provide the idomatic number for special cases of some of these families of digraphs.

Let G=(V,E) be a simple graph. A set S⊆V is independent set of G, if no two vertices of S are adjacent. The independence number α(G) is the size of a maximum independent set in the graph. In this paper we study and characterize the independent sets of the zero-divisor graph Γ(R) and ideal-based zero-divisor graph ΓI(R) of a commutative ring R .

Let R be a commutative ring. In this paper, by using algebraic properties of R, we study the Hase digraph of prime ideals of R.

In this note we are going to survey several invariants of finite groups related either to theirorders or to generating sets or to lattices of subgroups. Some relations among these invariants will be exhibited. Special attention will be paid to monotonicity of them.