Results 241 to 250 of about 12,115 (251)
Some of the next articles are maybe not open access.
Clique Partitions of Chordal Graphs
Combinatorics, Probability and Computing, 1993To partition the edges of a chordal graph on n vertices into cliques may require as many as n2/6 cliques; there is an example requiring this many, which is also a threshold graph and a split graph. It is unknown whether this many cliques will always suffice. We are able to show that (1 − c)n2/4 cliques will suffice for some c > 0.
Erdős, Paul +2 more
openaire +2 more sources
Dominating Sets in Chordal Graphs
SIAM Journal on Computing, 1982A set of vertices D is a dominating set for a graph if every vertex is either in D or adjacent to a vertex which is in D. We show that the problem of finding a minimum dominating set in a chordal graph is NP-complete, even when restricted to undirected path graphs, but exhibit a linear time greedy algorithm for the problem further restricted to ...
Booth, Kellogg S., Johnson, J. Howard
openaire +2 more sources
Graph searching on chordal graphs
1996Two variations of the graph searching problem, edge searching and node searching, are studied on several classes of chordal graphs, which include split graphs, interval graphs and k-starlike graphs.
Sheng-Lung Peng +4 more
openaire +1 more source
Matrix Completions and Chordal Graphs
Acta Mathematica Sinica, English Series, 2003This paper is an introduction to few problems and results in matrix completion problems. The topics which are considered here include questions on norm completions, rank completions, positive definite completions, numerical range completion properties and rank decomposability.
openaire +2 more sources
Coloring Powers of Chordal Graphs
SIAM Journal on Discrete Mathematics, 2004Summary: We prove that the \(k\)th power \(G^{k}\) of a chordal graph \(G\) with maximum degree \(\Delta\) is \(O(\sqrt{k}\Delta^{(k+1)/2})\)-degenerate for even values of \(k\) and \(O(\Delta^{(k+1)/2})\)-degenerate for odd values. In particular, this bounds the chromatic number \(\chi(G^k)\) of the \(k\)th power of \(G\).
openaire +1 more source
1988
Let P be an undirected graph with vertices V and edges E. Fix an enumeration, {v1,v2,...,vn}, of V and let M(P) = {A ∈ Mn (ℂ)| = 0 if (vi,vj) ∉ E where ei is the standard orthonormal basis of ℂn. Mn (ℂ)+ is the set of positive semi-definite n × n matrices with complex entries.
openaire +1 more source
Let P be an undirected graph with vertices V and edges E. Fix an enumeration, {v1,v2,...,vn}, of V and let M(P) = {A ∈ Mn (ℂ)| = 0 if (vi,vj) ∉ E where ei is the standard orthonormal basis of ℂn. Mn (ℂ)+ is the set of positive semi-definite n × n matrices with complex entries.
openaire +1 more source
What Is between Chordal and Weakly Chordal Graphs?
2008An (h ,s ,t )-representation of a graph G consists of a collection of subtrees {S v | v *** V (G )} of a tree T , such that (i) the maximum degree of T is at most h , (ii) every subtree has maximum degree at most s , and (iii) there is an edge between two vertices in the graph if and only if the corresponding subtrees in T have at least t vertices in ...
Elad Cohen +3 more
openaire +1 more source