On the fold thickness of graphs
- PDF / 645,459 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 8 Downloads / 195 Views
Francis Joseph H. Campeña
Arabian Journal of Mathematics
· Severino V. Gervacio
On the fold thickness of graphs
Received: 28 January 2018 / Accepted: 1 February 2020 © The Author(s) 2020
Abstract 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 0 , G 1 , G 2 , . . . , G k of graphs such that G 0 = G and G i is a 1-fold of G i−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. Mathematics Subject Classification
05C76 · 05C50
1 Introduction The notion of folding a graph as defined by Gervacio et al. [2] was motivated by the following situation. Consider a finite number of unit bars joined together at the ends where they are free to turn. Some meter sticks are constructed with this kind of structure as shown in bottom drawing in Fig. 1. Note that this particular meter stick can be folded to look like the top drawing in Fig. 1. The meter stick with this structure can be viewed as a physical model of the path graph Pn . After a sequence of folding of the meter stick, it becomes a physical model of a complete graph K 2 . Based on this observation, they defined the notion of folding a graph as follows. Let x and y be nonadjacent vertices of a graph that have at least one common neighbor. Obtain a new graph G from G by identifying x and y and reducing any resulting multiple edges to simple edges. We say that G is a 1-fold of G. Note that folds of a graph are idempotent homomorphisms and also known as retracts. For more details on the connection between a 1-fold and retracts, please see [6]. Example 1.1 The vertices x and y in the graph G shown in Fig. 2 have two common neighbors, b and c. By identifying x and y, we obtain the graph G , a 1-fold of G. Consider a graph G that is not isomorphic to a complete graph. Suppose that G 1 is a 1-fold of G. If G 1 is not a complete graph, then there should be a pair of non-adjacent vertices in G 1 and a graph G 2 which is a 1-fold of G 1 can be obtained. Thus, we can consider a sequence of graphs G = G 0 , G 1 , G 2 , . . . , G k . The F. J. H. Campeña (B) · S. V. Gervacio De La Salle University, Manila, Philippines E-mail: [email protected] S. V. Gervacio E-
Data Loading...
