The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
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 weaken the...
In this paper we present factorization theorems for strong maps between matroids of arbitrary cardinality. Moreover, we present a new way to prove the factorization theorem for strong maps between finite matroids.
We study the concept of an -partition of the vertex set of a graph , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, -part,...
We study the concept of an H-partition of the vertex set of a graph G, which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph H, with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, 4-part, external...
A form-finding problem for tensegrity structures is studied; given an abstract graph, we show an algorithm to provide a necessary condition for it to be the underlying graph of a tensegrity in Rd (typically d=2,3) with vertices in general position. Furthermore, for a certain class of graphs our algorithm allows to obtain necessary and sufficient conditions on the relative position of the vertices in order to underlie a tensegrity, for what we propose both a geometric and a symbolic approach.
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the...
Let be a graph. A vertex subversion strategy of , say , is a set of vertices in whose closed neighborhood is removed from . The survival-subgraph is denoted by . The Neighbor-Integrity of , , is defined to be , where is any vertex subversion strategy of , and is the maximum order of the components of . In this paper we give some results connecting the neighbor-integrity and binary graph operations.
In this paper, we use the graphs as a tool to study nilpotent Lie algebras. It implies to set up a link betwcen graph theory and Lie theory. To do this, it is already known that every nilpotent Lie algebra of maximal rank is associated with a generalized Cartan matrix A and it ils isomorphic to a quotient of the positive part n+ of the KacMoody algebra g(A). Then, if A is affine, we can associate n+ with a directed graph (from now on, we use the term digraph) and we can also associate a subgraph...