Refine my results

Specific Collection

Language

Université de Fribourg

Reducing the Domination Number of Graphs via Edge Contractions

Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - LIPICS Vol. 138, 2019, p. 41:1-41:13

In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k <= 2, the problem is coNP-hard. We further prove that for k=1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and that...

Public access from Sep 15, 2021
Université de Fribourg

Maximum eccentric connectivity index for graphs with given diameter

Hauweele, Pierre ; Hertz, Alain ; Mélot, Hadrien ; Ries, Bernard ; Devillez, Gauvain

In: Discrete Applied Mathematics, 2019, vol. 268, p. 102-111

The eccentricity of a vertex v in a graph G is the maximum distance between v and any other vertex of G. The diameter of a graph G is the maximum eccentricity of a vertex in G. The eccentric connectivity index of a connected graph is the sum over all vertices of the product between eccentricity and degree. Given two integers n and D with D ≤ n−1, we characterize those graphs which have...

Université de Fribourg

Reducing the Domination Number of Graphs via Edge Contractions

Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2014, no. 41, p. 1-13

In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >=0? We show that for k <=2, the problem is coNP-hard. We further prove that for k = 1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and...

Public access from Jul 9, 2021
Université de Fribourg

Detecting strong cliques

Hujdurovic, Ademir ; Milanic, Martin ; Ries, Bernard

In: Discrete Mathematics, 2019, vol. 342, no. 9, p. 2738-2750

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely...

Université de Fribourg

Bicolored Matchings in Some Classes of Graphs

Costa, Marie-Christine ; de Werra, Dominique ; Picouleau, Christophe ; Ries, Bernard

In: Graphs and Combinatorics, 2007, vol. 23, no. 1, p. 47-60

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R| = n + 1 such that perfect matchings with k red edges exist for all k, 0 ≤ k ≤ n. Given two integers p...

Université de Fribourg

On a graph coloring problem arising from discrete tomography

Bentz, Cédric ; Costa, Marie-Christine ; de Werra, Dominique ; Picouleau, Christophe ; Ries, Bernard

In: Networks, 2008, vol. 51, no. 4, p. 256-267

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family equation image of chains Pi together with vectors h(Pi) = (h1, . . . , hik), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = hij. An interpretation in terms of scheduling is presented. We consider special cases of...

Université de Fribourg

Degree-constrained edge partitioning in graphs arising from discrete tomography

Bentz, Cédric ; Costa, Marie-Christine ; Picouleau, Christophe ; Ries, Bernard ; de Werra, Dominique

In: Journal of Graph Algorithms and Applications, 2009, vol. 13, no. 2, p. 99-118

Starting from the basic problem of reconstructing a 2-dimensional im- age given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k = 3 colors is open. Variations and special cases are considered for the case k = 3 colors where the graph corresponding to the union of some color classes (for instance colors 1...

Université de Fribourg

Claw-free graphs with strongly perfect complements : Fractional and integral version, Part II: Nontrivial strip-structures

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

In: Discrete applied mathematics, 2011, vol. 159, no. 17, p. 1996-2029

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the...

Université de Fribourg

A note on chromatic properties of threshold graphs

Ries, Bernard ; de Werra, Dominique ; Zenklusen, Rico

In: Discrete Mathematics, 2012, vol. 312, no. 10, p. 1838-1843

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a similar question about vertex colorings: given an integer p, when is it possible to find weights (in general depending on p) for the vertices and...

Université de Fribourg

Claw-free graphs with strongly perfect complements : Fractional and integral version. Part I. Basic graphs

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

In: Discrete Applied Mathematics, 2011, vol. 159, no. 17, p. 1971-1995

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the...