Displaying similar documents to “Graphs which are locally paths”

Orientation distance graphs revisited

Wayne Goddard, Kiran Kanakadandi (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The orientation distance graph 𝓓ₒ(G) of a graph G is defined as the graph whose vertex set is the pair-wise non-isomorphic orientations of G, and two orientations are adjacent iff the reversal of one edge in one orientation produces the other. Orientation distance graphs was introduced by Chartrand et al. in 2001. We provide new results about orientation distance graphs and simpler proofs to existing results, especially with regards to the bipartiteness of orientation distance graphs...

The crossing numbers of join products of paths with graphs of order four

Marián Klešč, Stefan Schrötter (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing...

Asteroidal Quadruples in non Rooted Path Graphs

Marisa Gutierrez, Benjamin Lévêque, Silvia B. Tondato (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this...

Graphs of low chordality.

Chandran, L.Sunil, Lozin, Vadim V., Subramanian, C.R. (2005)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

On Path-Pairability in the Cartesian Product of Graphs

Gábor Mészáros (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We study the inheritance of path-pairability in the Cartesian product of graphs and prove additive and multiplicative inheritance patterns of path-pairability, depending on the number of vertices in the Cartesian product. We present path-pairable graph families that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.

Statuses and double branch weights of quadrangular outerplanar graphs

Halina Bielak, Kamil Powroźnik (2015)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we study some distance properties of outerplanar graphs with the Hamiltonian cycle whose all bounded faces are cycles isomorphic to the cycle C4. We call this family of graphs quadrangular outerplanar graphs. We give the lower and upper bound on the double branch weight and the status for this graphs. At the end of this paper we show some relations between median and double centroid in quadrangular outerplanar graphs.

Statuses and double branch weights of quadrangular outerplanar graphs

Halina Bielak, Kamil Powroźnik (2015)

Annales UMCS, Mathematica

Similarity:

In this paper we study some distance properties of outerplanar graphs with the Hamiltonian cycle whose all bounded faces are cycles isomorphic to the cycle C4. We call this family of graphs quadrangular outerplanar graphs. We give the lower and upper bound on the double branch weight and the status for this graphs. At the end of this paper we show some relations between median and double centroid in quadrangular outerplanar graphs

Cycles in graphs and related problems

Antoni Marczyk

Similarity:

Our aim is to survey results in graph theory centered around four themes: hamiltonian graphs, pancyclic graphs, cycles through vertices and the cycle structure in a graph. We focus on problems related to the closure result of Bondy and Chvátal, which is a common generalization of two fundamental theorems due to Dirac and Ore. We also describe a number of proof techniques in this domain. Aside from the closure operation we give some applications of Ramsey theory in the research of cycle...