All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 30

Showing per page

Odd and residue domination numbers of a graph

Yair Caro, William F. Klostermeyer, John L. Goldwasser (2001)

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a simple, undirected graph. A set of vertices D is called an odd dominating set if |N[v] ∩ D| ≡ 1 (mod 2) for every vertex v ∈ V(G). The minimum cardinality of an odd dominating set is called the odd domination number of G, denoted by γ₁(G). In this paper, several algorithmic and structural results are presented on this parameter for grids, complements of powers of cycles, and other graph classes as well as for more general forms of "residue" domination.

On co-bicliques

Denis Cornaz (2007)

RAIRO - Operations Research

A co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G. (A co-biclique is the complement of a biclique.) A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.) It is showed that a minimum-cost dependent set of G can be determined in polynomial...

On •-Line Signed Graphs L•(S)

Deepa Sinha, Ayushi Dhama (2015)

Discussiones Mathematicae Graph Theory

A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the...

On non-z(mod k) dominating sets

Yair Caro, Michael S. Jacobson (2003)

Discussiones Mathematicae Graph Theory

For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 1, a subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x ∈ V(G), |N[x]∩D| ≢ z (mod k).For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with...

On Path-Pairability in the Cartesian Product of Graphs

Gábor Mészáros (2016)

Discussiones Mathematicae Graph Theory

We study the inheritance of path-pairability in the Cartesian product of graphs and prove additive and multiplicative inheritance patterns of path-pairability, depending on the number of vertices in the Cartesian product. We present path-pairable graph families that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.

On Sequential Heuristic Methods for the Maximum Independent Set Problem

Ngoc C. Lê, Christoph Brause, Ingo Schiermeyer (2017)

Discussiones Mathematicae Graph Theory

We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6] , are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3]. Induced forbidden subgraph sets, under which the algorithms give maximum independent sets, are described. The Caro-Wei bound [4,14] is verified and performance of the algorithms on some special graphs is considered.

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for 2 -coloring...

On the parallel complexity of the alternating Hamiltonian cycle problem

E. Bampis, Y. Manoussakis, I. Milis (2010)

RAIRO - Operations Research

Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...

Currently displaying 1 – 20 of 30

Page 1 Next