On the fold thickness of graphs
The graph G′ obtained from a graph G by identifying two nonadjacent vertices in G having at least one common neighbor is called a 1-fold of G. A sequence G, G1, G2, … , Gk of graphs such that G= G and Gi is a 1-fold of Gi-1 for each i= 1 , 2 , … , k is called a uniform k-folding of G if the graphs i...
Saved in:
Main Authors: | , |
---|---|
Format: | text |
Published: |
Animo Repository
2020
|
Subjects: | |
Online Access: | https://animorepository.dlsu.edu.ph/faculty_research/3265 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | De La Salle University |
id |
oai:animorepository.dlsu.edu.ph:faculty_research-4230 |
---|---|
record_format |
eprints |
spelling |
oai:animorepository.dlsu.edu.ph:faculty_research-42302023-04-25T00:36:38Z On the fold thickness of graphs Campeña, Francis Joseph H. Gervacio, Severino V. The graph G′ obtained from a graph G by identifying two nonadjacent vertices in G having at least one common neighbor is called a 1-fold of G. A sequence G, G1, G2, … , Gk of graphs such that G= G and Gi is a 1-fold of Gi-1 for each i= 1 , 2 , … , k is called a uniform k-folding of G if the graphs in the sequence are all singular or all nonsingular. The fold thickness of G is the largest k for which there is a uniform k-folding of G. We show here that the fold thickness of a singular bipartite graph of order n is n- 3. Furthermore, the fold thickness of a nonsingular bipartite graph is 0, i.e., every 1-fold of a nonsingular bipartite graph is singular. We also determine the fold thickness of some well-known families of graphs such as cycles, fans and some wheels. Moreover, we investigate the fold thickness of graphs obtained by performing operations on these families of graphs. Specifically, we determine the fold thickness of graphs obtained from the cartesian product of two graphs and the fold thickness of a disconnected graph whose components are all isomorphic. 2020-02-01T08:00:00Z text https://animorepository.dlsu.edu.ph/faculty_research/3265 Faculty Research Work Animo Repository Bipartite graphs Graph theory Mathematics |
institution |
De La Salle University |
building |
De La Salle University Library |
continent |
Asia |
country |
Philippines Philippines |
content_provider |
De La Salle University Library |
collection |
DLSU Institutional Repository |
topic |
Bipartite graphs Graph theory Mathematics |
spellingShingle |
Bipartite graphs Graph theory Mathematics Campeña, Francis Joseph H. Gervacio, Severino V. On the fold thickness of graphs |
description |
The graph G′ obtained from a graph G by identifying two nonadjacent vertices in G having at least one common neighbor is called a 1-fold of G. A sequence G, G1, G2, … , Gk of graphs such that G= G and Gi is a 1-fold of Gi-1 for each i= 1 , 2 , … , k is called a uniform k-folding of G if the graphs in the sequence are all singular or all nonsingular. The fold thickness of G is the largest k for which there is a uniform k-folding of G. We show here that the fold thickness of a singular bipartite graph of order n is n- 3. Furthermore, the fold thickness of a nonsingular bipartite graph is 0, i.e., every 1-fold of a nonsingular bipartite graph is singular. We also determine the fold thickness of some well-known families of graphs such as cycles, fans and some wheels. Moreover, we investigate the fold thickness of graphs obtained by performing operations on these families of graphs. Specifically, we determine the fold thickness of graphs obtained from the cartesian product of two graphs and the fold thickness of a disconnected graph whose components are all isomorphic. |
format |
text |
author |
Campeña, Francis Joseph H. Gervacio, Severino V. |
author_facet |
Campeña, Francis Joseph H. Gervacio, Severino V. |
author_sort |
Campeña, Francis Joseph H. |
title |
On the fold thickness of graphs |
title_short |
On the fold thickness of graphs |
title_full |
On the fold thickness of graphs |
title_fullStr |
On the fold thickness of graphs |
title_full_unstemmed |
On the fold thickness of graphs |
title_sort |
on the fold thickness of graphs |
publisher |
Animo Repository |
publishDate |
2020 |
url |
https://animorepository.dlsu.edu.ph/faculty_research/3265 |
_version_ |
1764211145952985088 |