Tag

Sort by:

Maximum independent vertex set

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of . Given a vertex cover of a graph, all vertices not in the cover define a independent vertex set (Skiena 1990, p. 218). A maximum independent vertex set is an independent vertex set containing the largest possible number of vertices for a given graph.A maximum independent vertex set is not equivalent to a maximal independent vertex set, which is simply an independent vertex set that cannot be extended to a larger independent vertex set. Every maximum independent vertex set is also an independent vertex set, but the converse is not true.The independence number of a graph is thecardinality of the maximum independent set.Maximum independent vertex sets correspond to the complements of minimumvertex covers.A maximum independent vertex set in a given graph can be found in the Wolfram Language using FindIndependentVertexSet[g][[1]]...

Maximum independent edge set

An independent edge set, also called a matching, of a graph is a subset of the edges such that no two edges in the subset share a vertex in . A maximum independent edge set an independent edge set containing the largest possible number of edges among all independent edge sets for a given graph.A maximum independent edge set, also called a maximum matching, of a graph can be computed in the Wolfram Language with FindIndependentEdgeSet[g].The size of a maximum independent edge set is known as the matchingnumber or edge independence number.A maximum independent edge set is not equivalent to a maximal independent edge set, which is simply an independent edge set that cannot be extended to a larger independent edge set. Every maximum independent edge set is also a maximal independent edge set, but the converse is not true.Given an edge cover of a graph, all edges not in the cover define an independent set (Skiena 1990, p. 218). Gallai (1959) showed..

Maximal independent vertex set

A maximal independent vertex set of a graph is an independent vertex set that cannot be expanded to another independent vertex set by addition of any vertex in the graph.A maximal independent vertex set of a graph is equivalent to a maximal clique on the graph complement .Note that a maximal independent vertex set is not equivalent to a maximum independent vertex set, which is an independent vertex set containing the largest possible number of vertices among all independent vertex sets. A maximum independent vertex set is always maximal, but the converse does not hold.A maximal independent vertex set of a graph can be computed in the Wolfram Language using FindIndependentVertexSet[g, Infinity], and all maximal independent vertex sets can be computed using FindIndependentVertexSet[g, Infinity, All]...

Maximal independent edge set

A maximal independent edge set of a graph is an independent edge set that cannot be expanded to another independent edge set by addition of any edge in the graph.Note that a maximal independent edge set is not equivalent to a maximum independent edge set, which is an independent edge set containing the largest possible number of edges among all independent edge sets. A maximum independent edge set is always maximal, but the converse does not hold.A maximal independent edge set of a graph can be computed in the WolframLanguage using FindIndependentEdgeSet[g].

Independent set

Two sets and are said to be independent if their intersection , where is the empty set. For example, and are independent, but and are not. Independent sets are also called disjoint or mutually exclusive.An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of . The figure above shows independent vertex sets consisting of two subsets for a number of graphs (the wheel graph , utility graph , Petersen graph, and Frucht graph).An independent edge set can be defined similarly(Skiena 1990, p. 219).

Independent edge set

An independent edge set (also called a matching) of a graph is a subset of the edges such that no two edges in the subset share a vertex of (Skiena 1990, p. 219). The counts of independent edge sets of size in a graph are encoded through its matching-generating polynomial.The number of independent edge sets in a graph is sometimes called the Hosoyaindex.An independent edge set of maximum size is called a maximum independent edge set, and an independent edge set that cannot be expanded to another independent edge set by addition of any other edge in the graph is called a maximal independent edge set.A maximum independent edge set can be computed in the WolframLanguage using FindIndependentEdgeSet[g].The size of the largest independent edge set (i.e., of any maximum independent edge set) in a graph is known as its matching (or edge independence) number...

Independence ratio

The ratio of the independence number of a graph to its vertex count is known as the independence ratio of (Bollobás 1981).The product of the chromatic number and independenceratio of a graph is at least 1 (Bollobás 1981).Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "IndependenceRatio"].

Independence polynomial

Let be the number of independent vertex sets of cardinality in a graph . The polynomial(1)where is the independence number, is called the independence polynomial of (Gutman and Harary 1983, Levit and Mandrescu 2005). It is also goes by several other names, including the independent set polynomial (Hoede and Li 1994) or stable set polynomial (Chudnovsky and Seymour 2004).The independence polynomial is closely related to the matching polynomial. In particular, since independent edge sets in the line graph correspond to independent vertex sets in the original graph , the matching-generating polynomial of a graph is equal to the independence polynomial of the line graph of (Levit and Mandrescu 2005):(2)The independence polynomial is also related to the clique polynomial by(3)where denotes the graph complement (Hoede and Li 1994), and to the vertex cover polynomial by(4)where is the vertex count of (Akban and Oboudi 2013).The independence..

Independence number

The vertex independence number of a graph, often called simply "the" independence number, is the cardinality of the largest independent vertex set, i.e., the size of a maximum independent vertex set. The independence number is most commonly denoted , but may also be written (e.g., Bollobás 1981). Formally,(1)for a graph , where is the vertex set of and denotes the cardinal number of the set .The independence number of a graph is equal to the largest exponent in the graph'sindependence polynomial.The ratio of the independence number of a graph to its vertex count is known as the independence ratio of (Bollobás 1981).For a connected regular graph on vertices with vertex degree and smallest graph eigenvalue ,(2)(A. E. Brouwer, pers. comm., Dec. 17, 2012).The matching number of a graph is equal to the independence number of its line graph .By definition,(3)where is the vertex cover number of and its..

Check the price
for your project
we accept
Money back
guarantee
100% quality