Displaying similar documents to “Factoring directed graphs with respect to the cardinal product in polynomial time”

Factoring directed graphs with respect to the cardinal product in polynomial time II

Wilfried Imrich, Werner Klöckl (2010)

Discussiones Mathematicae Graph Theory

Similarity:

By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we...

An attractive class of bipartite graphs

Rodica Boliac, Vadim Lozin (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.

Line graphs: their maximum nullities and zero forcing numbers

Shaun Fallat, Abolghasem Soltani (2016)

Czechoslovak Mathematical Journal

Similarity:

The maximum nullity over a collection of matrices associated with a graph has been attracting the attention of numerous researchers for at least three decades. Along these lines various zero forcing parameters have been devised and utilized for bounding the maximum nullity. The maximum nullity and zero forcing number, and their positive counterparts, for general families of line graphs associated with graphs possessing a variety of specific properties are analysed. Building upon earlier...

Arithmetically maximal independent sets in infinite graphs

Stanisław Bylka (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Families of all sets of independent vertices in graphs are investigated. The problem how to characterize those infinite graphs which have arithmetically maximal independent sets is posed. A positive answer is given to the following classes of infinite graphs: bipartite graphs, line graphs and graphs having locally infinite clique-cover of vertices. Some counter examples are presented.