Displaying similar documents to “The matching polynomial of a distance-regular graph.”

Supermagic Graphs Having a Saturated Vertex

Jaroslav Ivančo, Tatiana Polláková (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is called supermagic if it admits a labeling of the edges by pairwise different consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we establish some conditions for graphs with a saturated vertex to be supermagic. Inter alia we show that complete multipartite graphs K1,n,n and K1,2,...,2 are supermagic.

Polynomial time algorithms for two classes of subgraph problem

Sriraman Sridharan (2008)

RAIRO - Operations Research

Similarity:

We design a polynomial time algorithm for finding a -1)- regular subgraph in a -regular graph without any induced star (claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of -regular graphs with an induced star (, not containing any (-1)-regular subgraph is also constructed.

On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs

Dingguo Wang, Erfang Shan (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.