All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 13 of 13

Showing per page

Edge cycle extendable graphs

Terry A. McKee (2012)

Discussiones Mathematicae Graph Theory

A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C⁺ is also formed from edges and one chord of a cycle C' of length one greater than C with V(C') ⊆ V(C⁺). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.

Edge-connectivity of strong products of graphs

Bostjan Bresar, Simon Spacapan (2007)

Discussiones Mathematicae Graph Theory

The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ 1,2 either x i = y i or x i y i ∈ E ( G i ) . In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals minδ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|). In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for g ( n , l ) , the biggest number k guaranteeing that there exist l graphs on n vertices, each two having edit distance at least k . By edit distance of two graphs G , F we mean the number of edges needed to be added to or deleted from graph G to obtain graph F . This new extremal number g ( n , l ) is closely linked to the edit distance of graphs. Using probabilistic methods we show that g ( n , l ) is close...

End Simplicial Vertices in Path Graphs

Marisa Gutierrez, Silvia B. Tondato (2016)

Discussiones Mathematicae Graph Theory

A graph is a path graph if there is a tree, called UV -model, whose vertices are the maximal cliques of the graph and for each vertex x of the graph the set of maximal cliques that contains it induces a path in the tree. A graph is an interval graph if there is a UV -model that is a path, called an interval model. Gimbel [3] characterized those vertices in interval graphs for which there is some interval model where the interval corresponding to those vertices is an end interval. In this work, we...

Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)

Jan Florek (2015)

Colloquium Mathematicae

Let be the family of all 2-connected plane triangulations with vertices of degree three or six. Grünbaum and Motzkin proved (in dual terms) that every graph P ∈ has a decomposition into factors P₀, P₁, P₂ (indexed by elements of the cyclic group Q = 0,1,2) such that every factor P q consists of two induced paths of the same length M(q), and K(q) - 1 induced cycles of the same length 2M(q). For q ∈ Q, we define an integer S⁺(q) such that the vector (K(q),M(q),S⁺(q)) determines the graph P (if P is...

Existence of perfect matchings in a plane bipartite graph

Zhongyuan Che (2010)

Czechoslovak Mathematical Journal

We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).

Currently displaying 1 – 13 of 13

Page 1