Results 1 to 10 of about 3,632 (158)
The Dilworth Number of Auto-Chordal-Bipartite Graphs [PDF]
Graphs and Combinatorics, 2013 The mirror (or bipartite complement) mir(B) of a bipartite graph B=(X,Y,E) has the same color classes X and Y as B, and two vertices x in X and y in Y are adjacent in mir(B) if and only if xy is not in E. A bipartite graph is chordal bipartite if none of
Berry, Anne +2 more
core +3 more sources
Bipartite powers of k-chordal graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 Let k be an integer and k \geq 3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive
Chandran, L. Sunil, Mathew, Rogers
core +6 more sources
Hop domination in chordal bipartite graphs
Discussiones Mathematicae Graph Theory, 2023 Summary: In a graph \(G\), a vertex is said to 2-step dominate itself and all the vertices which are at distance 2 from it in \(G\). A set \(D\) of vertices in \(G\) is called a hop dominating set of \(G\) if every vertex outside \(D\) is 2-step dominated by some vertex of \(D\).
Michael A. Henning +2 more
doaj +3 more sources
Recognizing Chordal-Bipartite Probe Graphs [PDF]
, 2007 A graph G is chordal-bipartite 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-bipartite graph by adding edges between non-probes. A bipartite graph
Berry, Anne +6 more
core +3 more sources
Feedback vertex set on chordal bipartite graphs [PDF]
, 2011 Let G=(A,B,E) be a bipartite graph with color classes A and B. The graph G is chordal bipartite if G has no induced cycle of length more than four. Let G=(V,E) be a graph. A feedback vertex set F is a set of vertices F subset V such that G-F is a forest.
Kloks, Ton +2 more
core +2 more sources
On the monophonic rank of a graph [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 A set of vertices $S$ of a graph $G$ is {\em monophonically convex} if every induced path joining two vertices of $S$ is contained in $S$. The {\em monophonic convex hull of $S$}, $\langle S \rangle$, is the smallest monophonically convex set containing $
Mitre C. Dourado +2 more
doaj +1 more source
Treewidth of Chordal Bipartite Graphs [PDF]
Journal of Algorithms, 1993 Summary: Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one.
Kloks, A.J.J., Kratsch, D.
openaire +6 more sources
Independent roman $\{3\}$-domination [PDF]
Transactions on Combinatorics, 2022 Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman $\{3\}$-domination. A function $g : V(G) \rightarrow \lbrace 0, 1, 2, 3 \rbrace$ having the property that $\sum_{v \in N_G(u)}^{} g(v) \geq 3$, if $g(u) = 0$,
P. Chakradhar, P. Venkata Subba Reddy
doaj +1 more source
Algorithmic Aspects of Secure Connected Domination in Graphs
Discussiones Mathematicae Graph Theory, 2021 Let G = (V, E) be a simple, undirected and connected graph. A connected dominating set S ⊆ V is a secure connected dominating set of G, if for each u ∈ V \ S, there exists v ∈ S such that (u, v) ∈ E and the set (S \ {v}) ∪ {u} is a connected dominating ...
Kumar Jakkepalli Pavan +1 more
doaj +1 more source
Simultaneously dominating all spanning trees of a graph
Electronic Journal of Graph Theory and Applications, 2022 We investigate the problem of simultaneously dominating all spanning trees of a given graph. We prove that on 2-connected graphs, a subset of the vertices dominates all spanning trees of the graph if and only if it is a vertex cover.
Sebastian Johann +2 more
doaj +1 more source