Forest decompositions of graphs with cyclomatic number 3.
Farrell, E.J. (1983)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Farrell, E.J. (1983)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Ivan Gutman (1998)
Publications de l'Institut Mathématique
Similarity:
Jason T. Hedetniemi (2015)
Discussiones Mathematicae Graph Theory
Similarity:
Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.
Jernej Azarija (2013)
Discussiones Mathematicae Graph Theory
Similarity:
Let G1 and G2 be simple graphs and let n1 = |V (G1)|, m1 = |E(G1)|, n2 = |V (G2)| and m2 = |E(G2)|. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G1 □G2 of G1 and G2. We show that: [...] and [...] . We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in Kn1 □Kn2 which turns out to be [...] .
Jiří Sedláček (1970)
Časopis pro pěstování matematiky
Similarity:
Marián Klešč (2005)
Discussiones Mathematicae Graph Theory
Similarity:
The exact values of crossing numbers of the Cartesian products of four special graphs of order five with cycles are given and, in addition, all known crossing numbers of Cartesian products of cycles with connected graphs on five vertices are summarized.
Farrell, E.J. (1983)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Caminiti, Saverio, Fusco, Emanuele G. (2007)
Journal of Integer Sequences [electronic only]
Similarity:
Marián Klešč (1999)
Discussiones Mathematicae Graph Theory
Similarity:
There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.
Tanja Gologranc (2014)
Discussiones Mathematicae Graph Theory
Similarity:
Tree-like partial cubes were introduced in [B. Brešar, W. Imrich, S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory, 23 (2003), 227-240] as a generalization of median graphs. We present some incorrectnesses from that article. In particular we point to a gap in the proof of the theorem about the dismantlability of the cube graph of a tree-like partial cube and give a new proof of that result, which holds also for a bigger class of graphs, so called tree-like...
Ziyu Hu, Ko-Wei Lih, Daphne Der-Fen Liu (2018)
Discussiones Mathematicae Graph Theory
Similarity:
The strong chromatic index of a graph G, denoted by χ′s(G), is the minimum number of vertex induced matchings needed to partition the edge set of G. Let T be a tree without vertices of degree 2 and have at least one vertex of degree greater than 2. We construct a Halin graph G by drawing T on the plane and then drawing a cycle C connecting all its leaves in such a way that C forms the boundary of the unbounded face. We call T the characteristic tree of G. Let G denote a Halin graph with...
Mounira Nekri, Abdelhafid Berrachedi (2010)
RAIRO - Operations Research
Similarity:
The problem of embedding graphs into other graphs is much studied in the graph theory. In fact, much effort has been devoted to determining the conditions under which a graph G is a subgraph of a graph H, having a particular structure. An important class to study is the set of graphs which are embeddable into a hypercube. This importance results from the remarkable properties of the hypercube and its use in several domains, such as: the coding theory, transfer of information, multicriteria...
Marián Klešč (1995)
Discussiones Mathematicae Graph Theory
Similarity:
In this article we determine the crossing numbers of the Cartesian products of given three graphs on five vertices with paths.
Brualdi, Richard A., Mellendorf, Stephen (1994)
The Electronic Journal of Combinatorics [electronic only]
Similarity: