Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE
View through CrossRef
The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.
World Scientific Pub Co Pte Lt
Title: BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE
Description:
The graph reconstruction conjecture is a long-standing open problem in graph theory.
The conjecture has been verified for all graphs with at most 11 vertices.
Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs.
We extend the list of graph classes for which the conjecture holds.
We give a proof that bipartite permutation graphs are reconstructible.
Related Results
Neighborhood Reconstruction and Cancellation of Graphs
Neighborhood Reconstruction and Cancellation of Graphs
We connect two seemingly unrelated problems in graph theory.Any graph $G$ has a neighborhood multiset $\mathscr{N}(G)= \{N(x) \mid x\in V(G)\}$ whose elements are precisely the ope...
Complete (2,2) Bipartite Graphs
Complete (2,2) Bipartite Graphs
A bipartite graph G can be treated as a (1,1) bipartite graph in the sense that, no two vertices in the same part are at distance one from each other. A (2,2) bipartite graph is an...
Efficient parallel algorithms for bipartite permutation graphs
Efficient parallel algorithms for bipartite permutation graphs
AbstractIn this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation gr...
Independent Set in Neutrosophic Graphs
Independent Set in Neutrosophic Graphs
New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...
Failed Independent Number in Neutrosophic Graphs
Failed Independent Number in Neutrosophic Graphs
New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...
Fidelity and entanglement of random bipartite pure states: insights and applications
Fidelity and entanglement of random bipartite pure states: insights and applications
Abstract
We investigate the fidelity of Haar random bipartite pure states from a fixed reference quantum state and their bipartite entanglement. By plotting the fide...
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Abstract
Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...
On Bipartite Distance-Regular Cayley Graphs with Small Diameter
On Bipartite Distance-Regular Cayley Graphs with Small Diameter
We study bipartite distance-regular Cayley graphs with diameter three or four. We give sufficient conditions under which a bipartite Cayley graph can be constructed on the semidire...