Results 21 to 30 of about 3,632 (158)
Open k-monopolies in graphs: complexity and related concepts [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis ...
Dorota Kuziak +2 more
doaj +1 more source
Total Roman {3}-Domination: The Complexity and Linear-Time Algorithm for Trees
Mathematics, 2021 For a simple graph G=(V,E) with no isolated vertices, a total Roman {3}-dominating function(TR3DF) on G is a function f:V(G)→{0,1,2,3} having the property that (i) ∑w∈N(v)f(w)≥3 if f(v)=0; (ii) ∑w∈N(v)f(w)≥2 if f(v)=1; and (iii) every vertex v with f(v ...
Xinyue Liu +3 more
doaj +1 more source
Line graphs of directed graphs I [PDF]
Transactions on CombinatoricsWe determine the forbidden induced subgraphs for the intersection of the classes of chordal bipartite graphs and line graphs of acyclic directed graphs. This is a first step towards finding the forbidden induced subgraphs for the class of line graphs of ...
Vaidyanathan Sivaraman, Daniel Slilaty
doaj +1 more source
TDMA is Optimal for All-unicast DoF Region of TIM if and only if Topology is Chordal Bipartite [PDF]
, 2017 The main result of this work is that an orthogonal access scheme such as TDMA achieves the all-unicast degrees of freedom (DoF) region of the topological interference management (TIM) problem if and only if the network topology graph is chordal bipartite,
Gesbert, David +3 more
core +4 more sources
Strongly chordal and chordal bipartite graphs are sandwich monotone
Journal of Combinatorial Optimization, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Heggernes, Pinar +3 more
openaire +3 more sources
Several results on chordal bipartite graphs [PDF]
Czechoslovak Mathematical Journal, 1997 A bipartite graph \(G\) is called chordal, if in each circuit in \(G\) of length greater then 4 there is a pair of vertices joined by an edge which does not belong to that circuit. An edge of a bipartite graph \(G\) is called bisimplicial, if the subgraph of \(G\) induced by the union of neighbourhoods of its end vertices is a complete bipartite graph.
Bakonyi, Mihály, Bono, Aaron
openaire +2 more sources
Hadwiger number of graphs with small chordality [PDF]
, 2014 The Hadwiger number of a graph G is the largest integer h such that G has the complete graph K_h as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on
Golovach, Petr A. +3 more
core +4 more sources
Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
Discrete Applied Mathematics, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Uehara, Ryuhei +2 more
openaire +1 more source
Maximal 2-rainbow domination number of a graph
AKCE International Journal of Graphs and Combinatorics, 2016 A 2-rainbow dominating function (2RDF) of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set {1,2} such that for any vertex v∈V(G) with f(v)=0̸ the condition ⋃u∈N(v)f(u)={1,2} is fulfilled, where N(v) is the open ...
H. Abdollahzadeh Ahangar +3 more
doaj +1 more source
On the Threshold of Intractability [PDF]
, 2015 We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph.
A. Brandstädt +14 more
core +1 more source