The bipartite-splittance of a bipartite graph | Zendy

Jing-Xin Guan | Zendy; Jianhua Yin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The bipartite-splittance of a bipartite graph

Author(s) -

Jing-Xin Guan,

Jianhua Yin

Publication year - 2018

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.2057

Subject(s) - bipartite graph , mathematics , complete bipartite graph , combinatorics , edge transitive graph , graph , discrete mathematics , voltage graph , line graph

A bipartite-split graph is a bipartite graph whose vertex set can be partitioned into a complete bipartite set and an independent set. The bipartite- splittance of an arbitrary bipartite graph is the minimum number of edges to be added or removed in order to produce a bipartite-split graph. In this paper, we show that the bipartite-splittance of a bipartite graph depends only on the degree sequence pair of the bipartite graph, and an easily computable formula for it is derived. As a corollary, a simple characterization of the degree sequence pair of bipartite-split graphs is also given.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research