Number of Edges
Every pseudoforest on a set of n vertices has at most n edges, and every maximal pseudoforest on a set of n vertices has exactly n edges. Conversely, if a graph G has the property that, for every subset S of its vertices, the number of edges in the induced subgraph of S is at most the number of vertices in S, then G is a pseudoforest. 1-trees can be defined as connected graphs with equally many vertices and edges.
Moving from individual graphs to graph families, if a family of graphs has the property that every subgraph of a graph in the family is also in the family, and every graph in the family has at most as many edges as vertices, then the family contains only pseudoforests. For instance, every subgraph of a thrackle (a graph drawn so that every pair of edges has one point of intersection) is also a thrackle, so Conway's conjecture that every thrackle has at most as many edges as vertices can be restated as saying that every thrackle is a pseudoforest. A more precise characterization is that, if the conjecture is true, then the thrackles are exactly the pseudoforests with no four-vertex cycle and at most one odd cycle.
Streinu and Theran generalize the sparsity conditions defining pseudoforests: they define a graph as being (k,l)-sparse if every nonempty subgraph with n vertices has at most kn − l edges, and (k,l)-tight if it is (k,l)-sparse and has exactly kn − l edges. Thus, the pseudoforests are the (1,0)-sparse graphs, and the maximal pseudoforests are the (1,0)-tight graphs. Several other important families of graphs may be defined from other values of k and l, and when l ≤ k the (k,l)-sparse graphs may be characterized as the graphs formed as the edge-disjoint union of l forests and k − l pseudoforests.
Almost every sufficiently sparse random graph is pseudoforest. That is, if c is a constant with 0 < c < 1/2, and Pc(n) is the probability that choosing uniformly at random among the n-vertex graphs with cn edges results in a pseudoforest, then Pc(n) tends to one in the limit for large n. However, for c > 1/2, almost every random graph with cn edges has a large component that is not unicyclic.
Read more about this topic: Pseudoforest
Famous quotes containing the words number of, number and/or edges:
“I am walking over hot coals suspended over a deep pit at the bottom of which are a large number of vipers baring their fangs.”
—John Major (b. 1943)
“Not too many years ago, a childs experience was limited by how far he or she could ride a bicycle or by the physical boundaries that parents set. Today ... the real boundaries of a childs life are set more by the number of available cable channels and videotapes, by the simulated reality of videogames, by the number of megabytes of memory in the home computer. Now kids can go anywhere, as long as they stay inside the electronic bubble.”
—Richard Louv (20th century)
“The essence of the physicality of the most famous blonde in the world is a wholesome eroticism blurred a little round the edges by the fact she is not quite sure what eroticism is. This gives her her tentative luminosity and what makes her, somehow, always more like her own image in the mirror than she is like herself.”
—Angela Carter (19401992)