Displaying similar documents to “Notes on the independence number in the Cartesian product of graphs”

Note on enumeration of labeled split graphs

Vladislav Bína, Jiří Přibil (2015)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

The paper brings explicit formula for enumeration of vertex-labeled split graphs with given number of vertices. The authors derive this formula combinatorially using an auxiliary assertion concerning number of split graphs with given clique number. In conclusion authors discuss enumeration of vertex-labeled bipartite graphs, i.e., a graphical class defined in a similar manner to the class of split graphs.

Light Graphs In Planar Graphs Of Large Girth

Peter Hudák, Mária Maceková, Tomáš Madaras, Pavol Široczki (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w...