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 – 10 of 10

Showing per page

Paired-domination

S. Fitzpatrick, B. Hartnell (1998)

Discussiones Mathematicae Graph Theory

We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of girth seven...

Pairs Of Edges As Chords And As Cut-Edges

Terry A. McKee (2014)

Discussiones Mathematicae Graph Theory

Several authors have studied the graphs for which every edge is a chord of a cycle; among 2-connected graphs, one characterization is that the deletion of one vertex never creates a cut-edge. Two new results: among 3-connected graphs with minimum degree at least 4, every two adjacent edges are chords of a common cycle if and only if deleting two vertices never creates two adjacent cut-edges; among 4-connected graphs, every two edges are always chords of a common cycle.

Path-Neighborhood Graphs

R.C. Laskar, Henry Martyn Mulder (2013)

Discussiones Mathematicae Graph Theory

A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G , denoted by pc ( G ) , is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc ( G ) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2 -coloring for a connected bipartite graph G having δ ( G ) ≥ 2 and a dominating cycle...

Currently displaying 1 – 10 of 10

Page 1