1,720,970 research outputs found
The automorphism group of the s-stable Kneser graphs
Full text linkFor k,s≥2, the s-stable Kneser graphs are the graphs with vertex set the k-subsets S of {1,…,n} such that the circular distance between any two elements in S is at least s and two vertices are adjacent if and only if the corresponding k-subsets are disjoint. Braun showed that for n≥2k+1 the automorphism group of the 2-stable Kneser graphs (Schrijver graphs) is isomorphic to the dihedral group of order 2n. In this paper we generalize this result by proving that for s≥2 and n≥sk+1 the automorphism group of the s-stable Kneser graphs also is isomorphic to the dihedral group of order 2n.Fil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentin
The packing chromatic number of hypercubes
Full text linkThe packing chromatic number χρ (G) of a graph G is the smallest integer k needed to proper color the vertices of G in such a way that the distance in G between any two vertices having color i be at leasti+1. Goddard et al. (2008) found an upper bound for the packing chromatic number of hypercubes Qn. Moreover, they compute χρ (Qn) for n ≤ 5 leaving as an open problem the remaining cases. In this paper, we obtain a better upper bound for χρ (Qn) and we improve the lower bounds for χρ (Qn) for 6 ≤ n ≤ 11. In particular we compute the exact value of χρ (Qn) for 6 ≤ n ≤ 8.Fil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario; ArgentinaFil: Valencia Pabon, Mario. Centre National de la Recherche Scientifique; Francia. Université Paris-nord; Franci
On the complexity of { k } -domination and k-tuple domination in graphs
Full text linkWe consider two types of graph domination - {k}-domination and k-tuple domination, for a fixed positive integer k - and provide new NP-complete as well as polynomial time solvable instances for their related decision problems. Regarding NP-completeness results, we solve the complexity of the {k}-domination problem on split graphs, chordal bipartite graphs and planar graphs, left open in 2008. On the other hand, by exploiting Courcelle's results on Monadic Second Order Logic, we obtain that both problems are polynomial time solvable for graphs with clique-width bounded by a constant. In addition, we give an alternative proof for the linearity of these problems on strongly chordal graphs.Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario; ArgentinaFil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Torres, Pablo Daniel. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentin
Some links between identifying codes and separating, dominating and total dominating sets in graphs
Full text linkIn the search for a dynamic programming-based algorithm derived from the modular decomposition of graphs, we analyze the behavior of the identifying code number under disjoint union and join operations. This study lead us to investigate the behavior of new parameters related to separating, dominating and total dominating sets under the same operations. The obtained results and the modular decomposition of graphs easily result in a dynamic programming-based algorithm to calculate the identifying code number (and the related parameters) of a graph from the parameter values of its modular subgraphs. In particular, we obtain closed formulas for the parameters on spider and quasi-spider graphs which allow us to derive a simple and easy-to-implement linear time algorithm to obtain the identifying code number (and the related parameters) of P4-tidy graphs.Fil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; ArgentinaFil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentin
Shifts of the stable Kneser graphs and hom-idempotence
Full text linkA graph G is said to be hom-idempotent if there is a homomorphism from G2 to G, and weakly hom-idempotent if for some n≥1 there is a homomorphism from Gn+1 to Gn. Larose et al. (1998) proved that Kneser graphs KG(n,k) are not weakly hom-idempotent for n≥2k+1, k≥2. For s≥2, we characterize all the shifts (i.e., automorphisms of the graph that map every vertex to one of its neighbors) of s-stable Kneser graphs KG(n,k)s−stab and we show that 2-stable Kneser graphs are not weakly hom-idempotent, for n≥2k+2, k≥2. Moreover, for s,k≥2, we prove that s-stable Kneser graphs KG(ks+1,k)s−stab are circulant graphs and so hom-idempotent graphs. Finally, for s≥3, we show that s-stable Kneser graphs KG(2s+2,2)s−stab are cores, not χ-critical, not hom-idempotent and their chromatic number is equal to s+2.Fil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario; ArgentinaFil: Valencia Pabon, Mario. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universite de Paris 13-Nord; Franci
Grundy domination and zero forcing in Kneser graphs
Full text linkIn this paper, we continue the investigation of different types of (Grundy) dominating sequences. We consider four different types of Grundy domination numbers and the related zero forcing numbers, focusing on these numbers in the well-known class of Kneser graphs Kn,r. In particular, we establish that the Grundy total domination number γ t gr(Kn,r) equals 2r r for any r ≥ 2 and n ≥ 2r + 1. For the Grundy domination number of Kneser graphs we get γgr(Kn,r) = α(Kn,r) whenever n is sufficiently larger than r. On the other hand, the zero forcing number Z(Kn,r) is proved to be n r − 2r r when n ≥ 3r + 1 and r ≥ 2, while lower and upper bounds are provided for Z(Kn,r) when 2r + 1 ≤ n ≤ 3r. Some lower bounds for different types of minimum ranks of Kneser graphs are also obtained along the way.Fil: Bresar, Bostjan. University of Maribor; Eslovenia. Institute Of Mathematics, Physics And Mechanics Ljubljana; EsloveniaFil: Kos, Tim. Institute Of Mathematics, Physics And Mechanics Ljubljana; EsloveniaFil: Torres, Pablo Daniel. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentin
Complexity of k-tuple total and total {k}-dominations for some subclasses of bipartite graphs
Full text linkWe consider two variations of graph total domination, namely, k-tuple total domination and total {k}-domination (for a fixed positive integer k). Their related decision problems are both NP-complete even for bipartite graphs. In this work, we study some subclasses of bipartite graphs. We prove the NP-completeness of both problems (for every fixed k) for bipartite planar graphs and we provide an APX-hardness result for the total domination problem for bipartite subcubic graphs. In addition, we introduce a more general variation of total domination (total (r,m)-domination) that allows us to design a specific linear time algorithm for bipartite distance-hereditary graphs. In particular, it returns a minimum weight total {k}-dominating function for bipartite distance-hereditary graphs.Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; ArgentinaFil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Escuela de Ciencias Básicas; Argentin
The packing coloring problem for lobsters and partner limited graphs
Full text linkA packing k-coloring of a graph G is a k-coloring such that the distance between two vertices having color i is at least i + 1. To compute the packing chromatic number is NP-hard, even restricted to trees, and it is known to be polynomial time solvable only for a few graph classes, including cographs and split graphs. In this work, we provide upper bounds for the packing chromatic number of lobsters and we prove that it can be computed in polynomial time for an infinite subclass of them, including caterpillars. In addition, we provide superclasses of split graphs where the packing chromatic number can be computed in polynomial time. Moreover, we prove that the packing chromatic number can be computed in polynomial time for the class of partner limited graphs, a superclass of cographs, including also P4-sparse and P4-tidy graphsFil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario; ArgentinaFil: Nasini, Graciela Leonor. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Torres, Pablo Daniel. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentin
On the diameter of Schrijver graphs
Full text linkFor k ≥ 1 and n ≥ 2k, the well known Kneser graph KG(n, k) has all k-element subsets of an n-element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph SG(n, k) of KG(n, k) with the same chromatic number. In this paper, we compute the diameter of the graph SG(2k + r,k) with r ≥ 1. We obtain that the diameter of SG(2k + r, k) is equal to 2 if r ≥ 2k - 2; 3 if k≥ - 2 ≤ r ≤ 2k - 3; k if r = 1; and for 2 ≤ r ≤ k - 3, we obtain that the diameter of SG(2k + r, k) is at most equal to k - r + 1.Fil: Pastine, Adrián Gabriel. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - San Luis. Instituto de Matemática Aplicada de San Luis "Prof. Ezio Marchi". Universidad Nacional de San Luis. Facultad de Ciencias Físico, Matemáticas y Naturales. Instituto de Matemática Aplicada de San Luis "Prof. Ezio Marchi"; ArgentinaFil: Torres, Pablo Daniel. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Santa Fe; ArgentinaFil: Valencia Pabon, Mario. Universite Sorbonne Paris Nord; FranciaXI Latin and American Algorithms, Graphs and Optimization Symposium.Sao PauloBrasilUniversity of Sao Paul
On the complexity of the labeled domination problem in graphs
Full text linkIn 2008, a unified approach (labeled domination) to several domination problems (k-tuple domination, {k} -domination, and M-domination, among others) was introduced. The labeled domination problem is to find an L-dominating function of minimum weight in a graph. It is an NP-complete problem even when restricted to split graphs and bipartite graphs. On the other hand, it is known to be polynomial-time solvable for the class of strongly chordal graphs. In this paper, we state explicit formulas that relate the domination numbers considered. These relationships allow us to enlarge the family of graphs where the labeled domination problem is polynomial-time solvable to the class of graphs having cliquewidth bounded by a constant.Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; ArgentinaFil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; ArgentinaFil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentin
- …
