Results 31 to 40 of about 1,930 (230)
自余弱弦图(On self-complementary weakly chordal graphs)
Zhejiang Daxue xuebao. Lixue ban, 2010 The class of self-complementary (sc) weakly chordal graphs is studied, which is a generalization of self-complementary chordal graphs, lower and upper bounds for the number of two-pairs in sc weakly chordal graphs have been obtained.
MERAJUDDIN() +3 more
doaj +1 more source
Computing a Clique Tree with the Algorithm Maximal Label Search
Algorithms, 2017 The algorithm MLS (Maximal Label Search) is a graph search algorithm that generalizes the algorithms Maximum Cardinality Search (MCS), Lexicographic Breadth-First Search (LexBFS), Lexicographic Depth-First Search (LexDFS) and Maximal Neighborhood Search (
Anne Berry, Geneviève Simonet
doaj +1 more source
Discrete Applied Mathematics, 2003 AbstractIn this paper, we introduce the class of chordal probe graphs which are a generalization of both interval probe graphs and chordal graphs. A graph G is chordal probe if its vertices can be partitioned into two sets P (probes) and N (non-probes) where N is a stable set and such that G can be extended to a chordal graph by adding edges between ...
Marina Lipshteyn +1 more
openaire +3 more sources
Representations of Edge Intersection Graphs of Paths in a Tree [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 Let $\mathcal{P}$ be a collection of nontrivial simple paths in a tree $T$. The edge intersection graph of $\mathcal{P}$, denoted by EPT($\mathcal{P}$), has vertex set that corresponds to the members of $\mathcal{P}$, and two vertices are joined by an ...
Martin Charles Golumbic +2 more
doaj +1 more source
Complexity of Hamiltonian Cycle Reconfiguration
Algorithms, 2018 The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C 0 and C t of a graph G, whether there is a sequence of Hamiltonian cycles C 0 , C 1 , … , C t such that C i can be obtained ...
Asahi Takaoka
doaj +1 more source
Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs
Discussiones Mathematicae Graph Theory, 2014 Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new ...
Caria Pablo De, McKee Terry A.
doaj +1 more source
The leafage of a chordal graph
Discussiones Mathematicae Graph Theory, 1998 19 pages, 3 ...
Douglas B. West +2 more
openaire +3 more sources
On the multipacking number of grid graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 In 2001, Erwin introduced broadcast domination in graphs. It is a variant of classical domination where selected vertices may have different domination powers. The minimum cost of a dominating broadcast in a graph $G$ is denoted $\gamma_b(G)$.
Laurent Beaudou, Richard C. Brewster
doaj +1 more source
Token Sliding on Chordal Graphs [PDF]
, 2017 Let I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent ...
Bousquet, Nicolas, Bonamy, Marthe
openaire +3 more sources
Forbidden subgraphs in reduced power graphs of finite groups
AIMS Mathematics, 2021 Let G be a finite group. The reduced power graph of G is the undirected graph whose vertex set consists of all elements of G, and two distinct vertices x and y are adjacent if either ⟨x⟩⊂⟨y⟩ or ⟨y⟩⊂⟨x⟩. In this paper, we show that the reduced power graph
Huani Li , Ruiqin Fu, Xuanlong Ma
doaj +1 more source