BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The Grundy number of a graph is the maximal number of colors attained by a first-fit coloring of the graph. The class of Cameron graphs is the Seidel switching class of cographs. In this paper we show that the Grundy number is computable in polynomial time for Cameron graphs.
Without further ado, we present the P_3-game. The P_3-game is decidable for elementary classes of graphs such as paths and cycles. From an algorithmic point of view, the connected P_3-game is fascinating. We show that the connected P_3-game is polynomially decidable for classes such as trees, chordal graphs, ladders, cacti, outerplanar graphs and circular arc graphs.
Let G=(V,E) be a connected graph. A set U subseteq V is convex if G[U] is connected and all vertices of V\U have at most one neighbor in U. Let sigma(W) denote the unique smallest convex set that contains W subseteq V. Two players play the following game. Consider a convex set U and call it the `playground.' Initially, U = emptyset. When U=V, the player to move loses the game. Otherwise, that player chooses a vertex x in V\U which is at distance at most two from U. The effect of the move is that the playground U changes into sigma(U cup {x}) and the opponent is presented with this new playground. A graph is chordal bipartite if it is bipartite and has no induced cycle of length more than four. In this paper we show that, when G is chordal bipartite, there is a polynomial-time algorithm that computes the Grundy number of the P_3-game played on G. This implies that there is an efficient algorithm to decide whether the first player has a winning strategy.
A function f: V \rightarrow \{-1,0,1\} is a minus-domination function of a graph G=(V,E) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f(x) over all vertices x \in V. The minus-domination number γ^{-}(G) is the minimum weight over all minus-domination functions. The size of a minus domination is the number of vertices that are assigned 1. In this paper we show that the minus-domination problem is fixed-parameter tractable for d-degenerate graphs when parameterized by the size of the minus-dominating set and by d. The minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs. It is NP-complete for splitgraphs. Unless P=NP there is no fixed-parameter algorithm for minus-domination. 79,1 5%
Let G be a graph with vertex set V(G) and edge set E(G). A family S of nonempty sets {S1,…,Sn} is a set representation of G if there exists a one-to-one correspondence between the vertices v1,…,vn in V(G) and the sets in S such that vivj∈E(G) if and only if $S_i\cap S_j\neq \es$. A set representation S is a distinct (respectively, antichain, uniform and simple) set representation if any two sets Si and Sj in S have the property Si=Sj (respectively, Si⊈Sj, ∣Si∣=∣Sj∣ and ∣Si∩Sj∣⩽1). Let U(S)=⋃i=1nSi. Two set representations S and S′ are isomorphic if S′ can be obtained from S by a bijection from U(S) to U(S′). Let F denote a class of set representations of a graph G. The type of F is the number of equivalence classes under the isomorphism relation. In this paper, we investigate types of set representations for linegraphs. We determine the types for the following categories of set representations: simple-distinct, simple-antichain, simple-uniform and simple-distinct-uniform.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.