EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 4, 2022, 1536-1548 ISSN 1307-5543 – ejpam.com Published by New York Business Global On some properties of Non-traceable Cubic Bridge Graph Alex Ralph Baisa Nieva1,∗, Karen P. Nocum2 1 College of Arts and Sciences, Faculty/Camarines Sur Polytechnic Colleges, Nabua, Philippines 2 College of Arts and Sciences, Faculty/Batangas State University, Batangas City, Philippines Abstract. Graphs considered in this paper are simple finite undirected graph without loops or multiple edges. A simple graph where each vertex has degree 3 is called a cubic graph. A cubic graph, that is, 1-connected or cubic bridge graph is traceable if it contains a Hamiltonian path. Otherwise, we called it non-traceable. In this paper, we introduce a new family of cubic graphs called Non-Traceable Cubic Bridge Graph (NTCBG) that satisfies the conjecture of Zoeram and Yaqubi (2017). In addition, we define two important connected components of NTCBG those are the central fragment that gives assurance for a graph to be non-traceable and its branch. Some properties of a NTCBG such as chromatic number and clique number are also provided. 2020 Mathematics Subject Classifications: 05C07,05C15,05C62 Key Words and Phrases: Cubic graph, bridge graph, non-traceable, central fragment, NTCBG 1. Introduction Cubic graph is one of the classes of graphs that fascinates graph theorist over the years because of its interesting application and appearances as a counterexample in so many areas of the subject. A cubic graph can be classified into 3 different types namely, 1- connected, 2-connected and 3-connected. Several papers in graph theory discussed certain types of cubic graphs, that is, 1-connected or cubic bridge graph. Fillar et al. in 2010 presented in their paper the ratio of cubic bridge graphs over cubic non-Hamiltonian graph and observed that the ratio is closer to 1 [4]. This observation gave rise to a conjecture that almost all cubic non-Hamiltonian graphs are bridge graphs. A cubic bridge graph can be divided into two classes namely, traceable which contains a Hamiltonian path and non-traceable which does not contain Hamiltonian path. Zoeram and Yaqubi in 2017 gave a construction sequence of a cubic graph and presented a conjecture that there exist an n ∈ N such that each cubic graph with at least n vertices has a spanning ⌊ n+2 6 ⌋ -ended tree [7]. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i4.4453 Email addresses: alexralph.nieva08@gmail.com (A.R Nieva), karen.nocum@g.batstate-u.edu.ph (K.Nocum) https://www.ejpam.com 1536 © 2022 EJPAM All rights reserved. A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1537 2. Preliminaries Throughout this article, we only consider a finite simple undirected graph. For graph- theoretic terms that have not been defined but are used in the paper, see Bollobas and Chartrand [2, 5]. A graph G is an ordered pair G = (V (G), E(G)) where V (G) is a nonempty set of elements called vertices, and E(G) is a set of unordered pairs of vertices called edges. The number |V (G)| is called the order of G and the number |E(G)| is called the size of G. The degree of a vertex u in a graph G is the number of edges incident with u and denoted by degG(u). A vertex in a graph with degree 1 is called a pendant vertex or end-vertex denoted by End(G) while an edge of the graph incident to a pendant vertex is called pendant edge. If the vertices of a graph G of order n can be labeled x1, x2, ..., xn so that the edges are [x1, x2], [x2, x3], ..., [xn−1, xn], then G is called a path of order n, denoted by Pn. A path in G that contains every vertex of G is called a Hamiltonian path of G, while a cycle in G that contains every vertex of G is called a Hamiltonian cycle of G. A graph that contains a Hamiltonian cycle is itself called Hamiltonian. A graph H is a subgraph of a graph G if V (H) ⊆ V (G) and E(H) ⊆ E(G), in which case we write H ⊆ G. If H is a subgraph of G, then G is a supergraph of H. If V (H) = V (G), then H is a spanning subgraph of G. The union G = G1 ⊕G2 of graphs G1 and G2 has vertex set V (G) = V (G1) ∪ V (G2) and edge set E(G) = E(G1) ∪ E(G2). A graph containing exactly one cycle as a subgraph is called unicyclic graph. A unicyclic graph G, other than a cycle, is called a hairy cycle if the deletion of any edge e in the cycle of G results in a caterpillar [1]. In other words, all the graphs that are constructed by attaching pendants to the vertices of a cycle is called hairy cycles. The cycle Cn with m pendants attached to each cycle vertex is called m-hairy n-cycle for all m,n ∈ N with n ≥ 3, and denoted by Cn ⊙ Sm. In the definition, the symbol ⊙ indicates that we attach a copy of the Sm at its vertex of degree m to each cycle vertex of Cn. The new graph will have m pendant at each cycle vertex. Theorem 1. [5] A 3-regular graph must have an even number of vertices. The next theorem gives an upper bound for the chromatic number of any connected graph. Theorem 2. [5] For every graph G, χ(G) ≤ 1 + ∆(G). Corollary 1. [5] For every graph G, χ(G) ≥ ω(G). Brooks’ suggests that Theorem 2 occurs only in very special cases such as an odd cycle graph, that is, a cycle of odd order and a complete graph. The next theorem will discuss about restriction of particular types of graphs. Theorem 3. [3] (Brooks’ Theorem) For every connected graph G that is not an odd cycle or a complete graph, χ(G) ≤ ∆(G) A rather obvious, but often useful, lower bound for the chromatic number of a graph involves the chromatic numbers of its subgraphs. A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1538 Theorem 4. [5] If H is a subgraph of G ,then χ(H) ≤ χ(G). The following theorem of Zeoram and Yaqubi [7] gives an important characteristic of a tree with maximum degree equal to 3. Theorem 5. [7] Let T be a tree with n vertices such that ∆(T ) ≤ 3. If |leaf(T )| = k and p be the number of vertices of degree 3 in T , then k = p+ 2. Theorem 6. [7] Let G be a graph and k ≤ 3 be the smallest integer such that G has a spanning tree T with k leaves. Then, no two leaves of T are adjacent in G. The next theorem is a necessary condition for Hamiltonian graphs. Recall k(G − S) which is the number of components in G− S. Theorem 7. [5] If G is a Hamiltonian graph, then k(G − S) ≤ |S| for every nonempty proper subset S of V (G). Since Theorem 7 gives a necessary condition for a graph to be Hamiltonian, that is, this theorem describes a property possessed by every Hamiltonian graph. This theorem is most useful in its contrapositive statement: If there exist a nonempty proper subset S of the vertex set of a graph G such that k(G− S) > |S|, then G is not Hamiltonian The next theorem is analogous to Theorem 7 which is a necessary condition for a graph to contain a Hamiltonian path. This theorem describes a property possessed by every graph that contains a Hamiltonian path. It is stated as follows. Theorem 8. [6] If G contains a Hamiltonian path, then k(G − S) ≤ |S| + 1 for every nonempty proper subset S of V (G). Since Theorem 8 is a necessary condition for the existence of a Hamiltonian path in a graph, the contrapositive to this statement is given by: If there exist a nonempty proper subset S of the vertex set of a graph G such that k(G − S) > |S| + 1, then G does not contains Hamiltonian path. In particular, if removing a set of vertices S to a graph results to k(G − S) > |S| + 1 then we can say that the graph does not contain a Hamiltonian path. 3. Construction of NTCBG In this section we will define a Non-Traceable Cubic Bridge Graph G together with its two important connected components, that is, its central fragment that provides an assurance that G will be non-traceable and the set of branches that are also a cubic graph. Throughout this paper, we denote G as non-traceable cubic bridge graph. Definition 1. A 3-regular graph G is said to be non-traceable cubic bridge graph if G is a cubic bridge graph such that G does not contain a Hamiltonian path, otherwise G is traceable cubic bridge graph. A central fragment of a non-traceable cubic bridge graph G denoted by C , where C is a subgraph of G satisfying the following properties, (i) C is connected, (ii) C is a bridge graph, (iii) C is non-traceable and (iv) C must contain vertices of degree 1 and of degree 3 only. A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1539 Consider the graph G in Figure 1 which is a cubic bridge graph since it is a cubic graph contains a cut edge. Notice that if we let S = {u} then G satisfies the contrapositive of Theorem 8. This implies that G is a non-traceable cubic bridge graph. G u ......................... .......... ............................................. . .......................................... .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ............ ........... .. .......... ............................................. . ....................... ............................................. . ....................... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . ............ ........... .. .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......................................... .......... ............................................. . ......................... .......... ............................................. . .......... ............................................. . ............ ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. . ......... .... .......... ............................................. . ......................... .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ............ ........... .. .......... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . G− S .................... ............................................ ................................. ............................................ .................. ............... ............................................ ............................................................................. ................................................................ ............................................ ................................................... ............................................ .................................................................... ....................... .... ............................................ ............................................ ................................................................ ............................................................................. .................. ............... ............................................ ................................. ............................................ .................... ............................................ ............................................ ........................ ....................... .... ............................................ ............................................ ................................................... ............................................ ............................................ .................... ............................................ .................. ............... ............................................ ............................................................................. .................. ............... ............................................ .................... ........................................................................................ ................................................... ............................................ .................................................................... ....................... .... ............................................ ............................................ Figure 1: Example of NTCBG Since a central fragment must be connected and contains vertices of degree 1 and 3 only, the smallest possible graphs are those with 4 vertices which are shown in Figure 2. We may notice from Figure 2 that H1 and H2 are the only bridge graphs. Furthermore, H2 is the only non-traceable graph by the contrapositive of Theorem 8. We can also say that since a Hamiltonian path must contain 2 end-vertices and H2 contains 3 end-vertices, thus H2 does not contains a Hamiltonian path which implies that it is non-traceable. Since H2 satisfies Definition 1, then H2 is the smallest possible central fragment. Hence, we can use this as our basis of central fragment construction. ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . H1 .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . H2 ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... H3 ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. ........................................... H4 ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. ....................................................... ........... ........... ........... ........... ......... H5 ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. ....................................................... ........... ........... ........... ........... .......................................................................... H6 Figure 2: All possible connected graphs with 4 vertices There are two possible classes of graphs that can be formed satisfying the definition of central fragment. These are a central fragment which is a tree or a central fragment which is not a tree. For simplicity, we write a general central fragment, a central fragment which is a tree, and not a tree as C , C ∗, and C ∗∗, respectively. Since we know that C ∗ 1 is the smallest order of a central fragment shown in Figure 3, we can extend C ∗ 1 our basis which preserves its tree structure (see Figure 3). From this, we have the following proposition. .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . C ∗ 1 . .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . C ∗ 2 .. .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . C ∗ 3 ... .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ........................................... ............................................. . .......... ............................................. ........................................... ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . C ∗ n ..................................... Figure 3: Possible central fragment which is a tree Proposition 1. Any central fragment C ∗ with kc-leaves has |V (C ∗)| = 2(kc − 1) where kc ≥ 3. Proof. Suppose we have C ∗. Then it contains vertices of degree 1 and of degree 3 only. Now, let p be the number of vertices of degree 3. Since C ∗ has kc-leaves and by Theorems A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1540 5 and 6, p = kc − 2 where kc ≥ 3 . Hence |V (C )| = |leaf(C ∗)| + p and it implies that |V (C ∗)| = kc + kc − 2 = 2kc − 2 = 2(kc − 1). Therefore |V (C ∗)| = 2(kc − 1) where kc ≥ 3. Remark 1. The order of the central fragment which is a tree can be simply determined by the number of its end-vertices, that is, |V (C ∗)| = 2(kc − 1) where kc is the number of its end-vertices. We can also determine it by the number of its vertices of degree 3, that is, |V (C ∗)| = 2(p+ 1) where p is the number of its vertices of degree 3. For instance, C is no longer a tree as illustrated in Figure 4 (b) and (c). This can be done by extending a tree C while preserving the number of its end-vertices. Now, consider a central fragment having fixed number of end-vertices that is 3 shown in Figure 4 (a). Here, the new formed graph should have equal number of end-vertices as the base graph which forms a new central fragment. .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . p = 1 (a) ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. .. (b) p = 3 .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. . v1 v2 ... p = 5 (c) .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ..................................................................................................................................... ................ ............. ............ ........... ........... .. v4 v1 v2 v3 .... . Figure 4: Construction sequence from C ∗ to C ∗∗ where kc = 3 We can further extend a central fragment which is a tree with n end-vertices as shown in Figures 5 and 6. Noticed that each time we extend a central fragment we add 2(m− 1) vertices to preserve the number of its end-vertices and to satisfy Definition 1. p = 2 .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. ... p = 4 .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . .......................................... .................................................... ............................................. . .......... ............................................. .v1v2.... p = 6 .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . .......................................... .................................................... ............................................. . .......... ............................................. . ................................................................................................................................. ..................... ................. v1v2 v3 v2 ..... . Figure 5: Construction sequence from C ∗ to C ∗∗ where kc = 4 .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......................................... .......................................... ......... ........ ........ ........ ........ . ......... ........ ........ ........ ........ . .......................................... ......... ........ ........ ........ ........ . .......................................... ......... ........ ........ ........ ........ . p = k − 2 ..................................... p = k .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......................................... .......................................... ......... ........ ........ ........ ........ . ......... ........ ........ ........ ........ . ......... ........ ........ ........ ........ . ............................................................................................................................................................ .......................................... ......... ........ ........ ........ ........ . .......................................... ......... ........ ........ ........ ........ . ......... ........ ........ ........ ........ . ...................................... . p = k + 2 .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......... ............................................. . .......................................... .......................................... ......... ........ ........ ........ ........ . ......... ........ ........ ........ ........ . ......... ........ ........ ........ ........ . ............................................................................................................................................................ .......................................... ......... ........ ........ ........ ........ . .......................................... ......... ........ ........ ........ ........ . ......... ........ ........ ........ ........ . ............................................................................................................................................................ ...................................... .. . Figure 6: Construction sequence from C ∗ to C ∗∗ where kc = n By this observation, we have the following proposition. A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1541 Proposition 2. Let C ∗∗ be a central fragment with kc-leaves such that kc ≥ 3 and p′ be the number of vertices of degree 3 in C ∗∗. Then p′ = kc − 2(2−m) where m ∈ N. Proof. Let C ∗∗ be a central fragment. Suppose kc ≥ 3 be the number of end-vertices and p′ the number of vertices of degree 3 in C ∗∗. By the remark of Proposition 1, we have |V (C ∗)| = kc + p′. Also, note that for m ∈ N we add 2(m− 1) vertices to C ∗ to form C ∗∗ that preserves the order of the leaf of C ∗. Thus, we have kc + p′ = |V (C ∗)| kc + p′ = |V (C ∗)|+ 2(m− 1) (we add 2(m− 1) vertices) kc + p′ = kc + p+ 2(m− 1) (since C ∗ is the base graph) p′ = kc + kc − 2 + 2(m− 1)− kc p′ = kc − 2 + 2m− 2 p′ = kc + 2m− 4 p′ = kc − 2(2−m) Therefore p′ = kc − 2(2−m) where m ∈ N. Proposition 3. Any central fragment C with kc-leaves has |V (C )| ≥ 2(kc − 1) where kc ≥ 3. Proof. Suppose C is a central fragment. Then |V (C )| = kc + p′. Note that by Proposition 2, the value of p′ increases whenever m increases in the equation p′ = kc − 2(2−m). It is clear that p′ ≥ kc − 2. Thus, we have |V (C )| = kc + p′ which implies that |V (C )| ≥ kc + kc − 2 = 2kc − 2 = 2(kc − 1) Now, recall the notion of hairy cycle. Observe that the family of hairy cycles in the form of Ck⊙1K1 can be classified as a central fragment. For simplicity, we use Hk instead of Ck ⊙ 1K1 to represent a hairy cycle see Figure 7. In the next theorem, we will show that every Hk is indeed a central fragment of some NTCBG, stated as follows. ........................................................... .......... ............................................. . ............ ........... ........... ........... ........ .......... ............................................. . ......... ........ ........ ........ ........ ........ ........ .. .......... ............................................. . ..................................................... .......... ............................................. . ..................................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ ........ ........ .. .......... ............................................. . ..................................................... .......... ............................................. . .......... ............................................. . .......... ......... ......... ......... .... c1c2 c3 c4 c5 c6 ck−1 ck Ck .......... ............................................. . K1 ........................................................... .......... ............................................. . ............ ........... ........... ........... ........ .......... ............................................. . ......... ........ ........ ........ ........ ........ ........ .. .......... ............................................. . ..................................................... .......... ............................................. . ..................................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ ........ ........ .. .......... ............................................. . ..................................................... .......... ............................................. . .......... ............................................. . .......... ......... ......... ......... .... c1c2 c3 c4 c5 c6 ck−1 ck ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ...................................................................... .......... ............................................. ........... ............................................. . ...................................................................... .......... ............................................. ........... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . ................................................................................ ............................................. . .......... ............................................. . ................................................................................ ............................................. . .......... ............................................. . a1a2 a3 a4 a5 a6 ak−1 ak Ck ⊙ 1K1 = Hk Figure 7: General form of a Hairy Cycle Theorem 9. Any hairy cycle Hk is a central fragment of NTCBG. A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1542 Proof. Let Hk be a graph. We will show that Hk satisfies all properties of a central fragment. By definition of a hairy cycle, Hk is connected and is also a bridge graph. By definition of a hairy cycle, every vertex of a cycle Ck is attached to one copy of K1 such that it forms a pendant edge. It follows that each vertex in the cycle has degree 3 and each end-vertex of a pendant edge has degree 1. Thus, every vertex of Hk must contain vertices is of degree 1 and of degree 3 only. We need to show that Hk is non-traceable. Suppose Hk is traceable. Then it implies that it contains a Hamiltonian path. Since Hk contains atleast 3 end-vertices and a Hamiltonian path contains 2 end-vertices it follows that Hk is non-traceable. Since all the properties of a central fragment are satisfied, therefore Hk is a central fragment. Here are some important properties of a central fragment being a hairy cycle. We present it as a remark as follows. Remark 2. Every hairy cycle Hk is unique up to isomorphism. Proposition 4. Let Hk be a central fragment. Then |V (Hk)| = |E(Hk)| = 2k, where k is the order and size of Ck, respectively. Proof. Let Hk be a central fragment. It follows that we have a cycle Ck of order k. By definition of a hairy cycle, Hk can be constructed by attaching one copy of K1 to the vertices of the cycle such that it forms a pendant edge. It follows that we have k pendant edges, thus it must have k end-vertices as well. Thus, |V (Hk)| = k + k = 2k, where k is the order of Ck. Analogous to the argument above, we can show that |E(Hk)| = 2k. Thus, |V (Hk)| = |E(Hk)| = 2k, where k is the order and size of Ck, respectively. Now we are ready to discuss the branch of a NTCBG. Definition 2. Let G be a NTCBG. A branch of a graph G denoted by Bi, such that every Bi is a subgraph of G is a cubic graph. A cubic graph whose one edge is subdivided which produces a path of length 2 such that the new vertex should equal to exactly one end-vertex in the central fragment is called constructed B̂i of Bi. Now, we will discuss the construction of a NTCBG. First, consider a central fragment with S = {v1, v2, v3}, where S is the set of end-vertices of the central fragment as shown in Figure 8 (a). Secondly, consider an arbitrary branch of NTCBG, say Bi, shown in Figure 8(b). Choose any edge for each graph. Then divide this edge into two such that it produces a path of length 2. Now, the new vertex should be equal to exactly one of the vertices in S. This will produce the graph in Figure 8 (b). Take the union to the central fragment C and 3 copies of branch Bi. The resulting graph is shown in Figure 8 (c). Observe that the result is a non-traceable cubic graph of order |V (G)| = |V (C )|+ ∑ |V (Bi)|. Proposition 5. Let Bi, i ∈ N, be the branch of NTCBG G then |V (Bi)| = 2(b−1) where b ≥ 3. A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1543 (a) v1 v2 v3....................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. . v1 ........................................... ............................................................................................................ ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. .................... .......... ......... ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......................................... .......... ............................................. ........... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . v2 . (b) ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. .................... .......... ......... ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......................................... .......... ............................................. ........... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . v3 ........................................... ............................................................................................................ ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......... ............................................. .................... .......... ......... ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......................................... .......... ............................................. ........... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . (c) . .. v1 v2 v3 ......................... .......... ............................................. . .......................................... .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ............ ........... .. .......... ............................................. . .................................................... ............................................. . .................................................... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . ............ ........... .. .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .......................................... .......... ............................................. . ......................... .......... ............................................. . .......... ............................................. . ............ ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ......................... .......... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . .................................................... ............................................. . ......... ........ ........ ........ ........ . .......... ............................................. . ............ ........... .. .......... ............................................. . .......... ............................................. . ................................................................. .......... ............................................. . .......... ............................................. ............. ........... ........... ........... ........... ......... .......... ............................................. . .......... ............................................. . Figure 8: Construction of NTCBG Proof. Note that every Bi is a cubic graph. Then by Theorem 1, Bi has even order. Hence, |V (Bi)| can be represented as 2b where b ∈ N. Since K4 is the smallest cubic graph, |V (Bi)| ≥ 4. It follows that we have |V (Bi)| = 2(b− 1) where b ≥ 3. Proposition 6. Let G be a NTCBG with kc-leaves. Then ∑ |V (Bi)| ≥ 4kc. Proof. Suppose Bi is a branch of a NTCBG. Then by Proposition 5, each Bi has order equal to 2(b− 1). Now, let kc be the order of end-vertices of Ci. Then, we have∑ |V (Bi)| = 2(b1 − 1) + 2(b2 − 1) + ...+ 2(bkc − 1)∑ |V (Bi) = 2(b1 + b2 + ...+ bkc)− 2kc (since b ≥ 3)∑ |V (Bi)| ≥ 2(3kc)− 2kc∑ |V (Bi)| ≥ 4kc Therefore, if G is a NTCBG, then ∑ |V (Bi)| ≥ 4kc. 4. Minimum leaf number of NTCBG Now, we present the following lemma that is necessary to prove one of the main result of the paper. Lemma 1. Let G be a simple undirected graph with a spanning tree T with minimum k-leaves such that ∆(T ) ≤ 3. Then k ≥ 3 if and only if G is non-traceable. Proof. Assume that a spanning tree T of G has minimum k ≥ 3 leaves. It follows that T is not a path, since the only tree that admits a Hamiltonian path are paths. In other words, the only tree that admits traceability is a path, then T is non-traceable. For the converse, suppose G is non-traceable graph. It implies that G does not contain any Hamiltonian path. Now, let Pn = [v1, v2, ..., vn] be the longest path that almost visits all the vertices of G such that v1 and vn are not adjacent. It follows that there exist at least vi ∈ G such that vi /∈ Pn. Since T is connected, vi must be connected to any vertex in Pn except for v1 and vn since it will contradict that Pn is the longest path that almost visits all the vertices of G. Thus vi must be connected to one of v2, v3, ..., vn−1. Thus, A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1544 By Theorem 5 we have k = p + 2 ≥ 1 + 2 = 3. Therefore, the spanning tree T of G has minimum k ≥ 3 leaves. Lemma 2. If G is a NTCBG with kc-leaves, then |V (G)| ≥ 6kc − 2. Proof. Suppose G is a NTCBG. Then it has a central fragment C and a branch Bi. It follows that |V (G)| = |V (C )|+ ∑ |V (Bi)|. By Proposition 3 and Proposition 6, we have |V (G)| = |V (C )|+ ∑ |V (Bi)| |V (G)| ≥ 2(kc − 1) + 4kc |V (G)| ≥ 2kc − 2 + 4kc |V (G)| ≥ 6kc − 2 Therefore, if G is a NTCBG with kc-leaves, then |V (G)| ≥ 6kc − 2. Remark 3. The smallest non-traceable Cubic Bridge graph is of order 16. Lemma 3. Let G be a NTCBG with spanning tree T and let A1, A2, and A3 be the set of vertices of T of degree 1, degree 2 and degree 3 respectively. Then A2 ≥ 4A1. Proof. Suppose G is a NTCBG with spanning tree T . Note that by Lemma 2 the order of non-traceble cubic bridge graph G is |V (G)| ≥ 6kc − 2. It follows that the spanning tree T of G has |V (T )| ≥ 6kc − 2. By Theorem 5 we know that A1 = kc and A3 = kc − 2. Since n = A1 +A2 +A3, it follows that, |V (T )| = A1 +A2 +A3 ≥ 6kc − 2 kc +A2 + kc − 2 ≥ 6kc − 2 A2 ≥ 6kc − 2− 2kc + 2 = 4kc Since A1 = kc, therefore A2 ≥ 4A1. Theorem 10. Let G be a NTCBG such that |V (G)| = n with spanning tree T . Then 3 ≤ |leaf(T )| ≤ ⌊ n+2 6 ⌋ . Proof. Since T is spanning tree of G, |V (T )| = |V (G)|. Since G is non-traceable, by Lemma 1, the spanning tree of G can be represented as a 3-ended tree. It follows that 3 ≤ |leaf(T )|. We only need to show that |leaf(T )| ≤ ⌊ n+2 6 ⌋ . By Lemma 2, the order of T is n ≥ 6kc − 2 and by Lemma 3, A2 ≥ 4A1. Thus, |V (T )| = n = A1 +A2 +A3 n = A1 + 4A1 +A3 n ≥ kc + 4k + kc − 2 6kc ≤ n+ 2 A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1545 kc ≤ n+ 2 6 Since kc is the number of end-vertices or leaves of a spanning tree, kc should be an element of N. Therefore 3 ≤ |leaf(T )| ≤ ⌊ n+2 6 ⌋ . Corollary 2. Let G be a NTCBG with spanning tree T . Then we can find a NTCBG G′ with spanning tree T ′ where |V (G′)| ≤ |V (G)| such that 3 ≤ |leaf(T ′)| ≤ |leaf(T )| ≤⌊ n+2 6 ⌋ . The proof of this corollary follows from Theorem 10. 5. Chromatic number and coloring of NTCBG Note that a NTCBG can be partitioned into two subgraphs, those are, the central fragment and its branch. The next lemma will discuss the possible coloring of an arbitrary branch of NTCBG. Theorem 11. For any branch Bi of a NTCBG, the constructed B̂i has chromatic number 3. Proof. Let Bi be any branch of a NTCBG. By Theorem 2, χ(Bi) ≤ ∆(Bi) + 1. It follows that χ(Bi) ≤ 4. Note that the only possible chromatic number for Bi is 2,3 and 4 only. Now, we will show that for every possible chromatic number of Bi, B̂i has chromatic number 3. Then we have the following cases to consider. Case 1: If for every vertex v of Bi, each neighborhood of v have the same color different from v. It follows that Bi is 2-colorable which implies that χ(Bi) = 2. Now, we need to show that B̂i has chromatic number 3. Since χ(Bi) = 2, we can color the vertices of Bi with color 1 and 2. Also, for every vertex vi ∈ Bi, the three neighborhoods of vi must share the same color different from vi. Now, recall the constructed B̂i of Bi. Note that we pick any edge in Bi then subdivide it such that it produces a path of length 2. Let vj be the new vertex in the subdivision of constructed B̂i. Then vj must be colored differently from 1 and 2, since vj is adjacent to both of this color. Without loss of generality, we must color vj using color 3. Thus, the constructed B̂i of Bi has chromatic number 3. Case 2: If for every vertex v of Bi, each neighborhood of v has two vertices of the same color different from v which is also a different color from the last vertex which is also a neighbor of v. It follows that Bi is 3-colorable which implies that χ(Bi) = 3. Now, we need to show that B̂i has chromatic number 3. Since χ(Bi) = 3, we can color the vertices of Bi with color 1,2 and 3. Also, for every vertex vi ∈ Bi, two vertices in neighborhood of vi must share the same color different from vi which is also a different color from the last vertex which is also a neighbor of v. Now, recall the constructed B̂i of Bi. Note that we pick any edge in Bi, then subdivide it such that it produces a path of length 2. Let vj be the new vertex in the subdivision of constructed B̂i. Since vj is adjacent to two colors, A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1546 we can color vj using colors either 1,2, or 3 depending on which two adjacent vertices it lies. Thus, the constructed B̂i of Bi has chromatic number 3. Case 3: If for every vertex v of Bi, each neighborhood of v has different color which is also different from the color of v. It follows that Bi is 4-colorable which implies that χ(Bi) = 4. By Brooks Theorem and Theorem 2, Bi ∼= K4. Now, we need to show that B̂i has chromatic number 3. Since χ(Bi) = 4, it implies that each neighborhood of v has a different color which is also a different from the color of v. Now, recall the constructed B̂i of Bi, note that we choose any edge in Bi such that it produces a path of length 2. Suppose we choose an edge e = [x, y] ∈ E(Bi) and let vi be the new vertex in the subdivision of the edge e in B̂i. Then vi must be adjacent to only two colors in Bi. Suppose we color Bi with 1,2,3 and 4. Without loss of generality, let 1 and 2 be the colors of vertices x and y which are adjacent in vi. Then we can color vi with the remaining colors in Bi, 3 and 4. Note that the vertices x and y are no longer adjacent in B̂i. Hence, we can color x, y by the same color as 1 or 2. By this argument, the possible coloring of constructed B̂i is 3,4 and either 1 or 2. This implies that the constructed B̂i has chromatic number 3. Therefore for any constructed B̂i of Bi has chromatic number 3. Consider the graph representation in Figure 9 (a). A cubic graph that has 2 coloring can be presented as (a) where a vertex color 1 has neighbors having the same color 2. Recall that for any branch of NTCBG, we pick any edge in particular branch since any edge has color 1 and 2. Then the new vertex must be different from 1 and 2, See Figure 9 (b). Hence, for any cubic graph that admits 2-coloring the constructed B̂i has chromatic number 3. For a cubic graph that admits 3-coloring, we have an example as shown in Figure 10. Note that for any vertex vi in (a), the neighbor vi has two vertices that have the same color. It is clear that for any edge we pick in (a), we can color it by different colors than its two adjacent vertices. Thus, for any cubic graph that admits 3-coloring, the constructed B̂i has also chromatic number 3. Lastly, Figure 11 illustrates case 3 of Theorem 11 since K4 is the only 3-regular graph that admits 4-coloring. (a) ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... 1 2 2 2 ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ . ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ..... .............................................................................................................................................................................. ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... .............................................................................................................................. ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ....... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ....... .................................................................................................................... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ....... .................................................................................................................... 1 1 1 1 11 (b) ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... 1 2 2 2 ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ . ............... .............. .............. .............. ............. ............... .............. .............. .............. ............. ...................................................................... ...................................................................... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... .......................................... ......................................... ......... ........ ........ ........ ........ .......... ......... ......... ......... ...... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ....... .................................................................................................................... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ....... .................................................................................................................... 1 1 1 1 11 ......... .............................................................. ..... ......... .............................................................. ..... ......... .............................................................. ..... ......... .............................................................. ..... 3 3 3 3 Figure 9: Coloring of branch Bi with 2 colors Theorem 12. Let G be a NTCBG graph of order n. Then the chromatic number of G is χ(G) = 3. A.R Nieva and K.Nocum / Eur. J. Pure Appl. Math, 15 (4) (2022), 1536-1548 1547 .............................................................. ............. ............................................................................. ......... ............................... ......... ............. ............................................................................. ......... .......... ......... ......... ... ......... ............. ............................................................................. ......... ..................................................... ......... ............. ............................................................................. ......... ............................... ......... ............. ............................................................................. ......... .......... ......... ......... ... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ . ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ . ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ....................................................................................................................... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... 1 2 3 2 3 1 (a) b) ......... .............................................................. ..... ......... .............................................................. ..... .......... .......... ............................... ......... ............. ............................................................................. ......... .......... ......... ......... ... ......... ............. ............................................................................. ......... ..................................................... ......... ............. ............................................................................. ......... ............................... ......... ............. ............................................................................. ......... .......... ......... ......... ... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ . ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ . ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ....................................................................................................................... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... 31 2 3 2 3 1 Figure 10: Coloring of branch Bi with 3 colors ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... (a) 1 4 3 1 ......... ........ ........ ........ ...... ................. ................ ................ .. .............................................................. .......... .......... .......... .......... .......... .......... .......... .......... .......... . ...................................................................................................... .............................................................................................................. ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... (b) 1 4 3 2 3, 4......... ........ ........ ........ ...... ................. ................ ................ .. .............................................................. .......... .......... .......... .......... .......... .......... .......... .......... .......... . ................................... ................................... .............................................................................................................. ......... .............................................................. ..... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... ......... ............. ............................................................................. ......... (c) 1, 2 4 3 1, 2 3, 4......... ........ ........ ........ ...... ................. ................ ................ .. .............................................................. .......... .......... .......... .......... .......... .......... .......... .......... .......... . ................................... ................................... .............................................................................................................. ......... .............................................................. ..... Figure 11: Coloring of the only branch with 4 colors Proof. Let G be a NTCBG and suppose B̂i be an arbitrary branch of G. Since B̂i is a subgraph of G, by Theorem 4 χ(B̂i) ≤ χ(G). Now, recall Theorem 11. Since χ(B̂i) = 3, χ(B̂i) ≤ χ(G) implying 3 ≤ χ(G). Since G is a cubic gaph it implies that ∆(G) = 3 By Brooks’ Theorem, χ(G) ≤ ∆(G) hence χ(G) ≤ 3. Taking the lower and upper bounds we have 3 ≤ χ(G) ≤ 3. Therefore, the least number of coloring of a cubic bridge graph is 3. 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 G1 ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... .................................... ....................................... ...................... ....................................... ............ ........... ........... ..... ....................................... ......... ........ ..... ......... ........ ........ ........ ........ ........ ........ ....... ................................................................ ............ ........... ........... ..... ........... .......... ......... ...................... ............ ........... ........... ..... ................................................... ........... ........... ..... ......... ........ ..... ......... ........ ........ ........ ........ ........ ........ ....... ................................................................ ......... ........ ..... .............................. ............ ........... ........... ..... ......... ........ ..... ................... .................. .................. .................. . ......... ........ ..... .......................................................................... ....................................... ................................................................ 1 1 1 1 1 1 2 2 2 2 3 3 3 3 G2 ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... .................................... ....................................... ...................... ....................................... ............ ........... ........... ..... ....................................... ......... ........ ..... ......... ........ ........ ........ ........ ........ ........ ....... ................................................................ ............ ........... ........... ..... ........... .......... ......... ...................... ............ ........... ........... ..... ................................................... ........... ........... ..... ......... ........ ..... ......... ........ ........ ........ ........ ........ ........ ....... ................................................................ .............................. ......... ........ ..... 1 1 1 2 2 3 3 3 ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ................................................................................................ ............................................................................................. ....... ....... .................................... ........... .......... ......... .............................. .............................. ........... .......... ......... .............. ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... G3 1 1 1 1 1 1 2 2 2 2 2 22 3 3 3 3 3 33 ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ...................... ....................................... ............ ........... ........... ..... ....................................... ......... ........ ..... ......... ........ ........ ........ ........ ........ ........ ....... ................................................................ ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ...................... ............ ........... ........... ..... ................................................... ........... ........... ..... ......... ........ ..... ......... ........ ........ ........ ........ ........ ........ ....... ................................................................ ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ............ ........... ........... ..... ......... ........ ..... ................... .................. .................. .................. . ......... ........ ..... .......................................................................... ....................................... ................................................................ ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ......... ............................................................ ... ................................................................ ...... ...... .......................... .................... ...... .................................... ....................................... ............ ........... ........... ..... ......... ........ ..... Figure 12: Example of NTCBG minimum coloring Remark 4. Every NTCBG of order n has proper k-coloring where 3 ≤ k ≤ n. Corollary 3. Let G be a NTCBG, Then ω(G) ≤ 3. Proof. By Corollary 1, χ(G) ≥ ω(G). By Theorem 12, χ(G) = 3. Therefore 3 ≥ ω(G) From this corollary, we can say that there are only two possibilities of ω(G), one is, if G is a triangle free graph then we have ω(G) = 2. Otherwise, G has ω(G) = 3. REFERENCES 1548 6. Summary and Conclusion In this paper, a new classification of cubic graphs called Non-traceable Cubic Bridge graph (NTCBG) is provided. Here, basic construction of a NTCBG were discussed. The concept of a central fragment was introduced as the main component of a NTCBG. The order, size, and classes of the central fragments were also determined. We also show that the family of hairy cycles Hk is a central fragment. In addition, the lower and upper bounds for a NTCBG to have a spanning k-trees were determined. It was found out that a NTCBG has spanning k-trees where 3 ≤ k ≤ ⌊ n+2 6 ⌋ . Lastly, the chromatic number, coloring and clique number of a NTCBG were discussed. Acknowledgements We sincerely thank the anonymous referees of European Journal of Pure and Applied Mathematics, for their useful comments to improve the paper. Furthermore, we thank the Department of Science and Technology (DOST-SEI) for the financial support while this research was ongoing. References [1] C Barrientos. Graceful graphs with pendant edges. Australasian Journal of Combina- torics, 33:99–107, 2005. [2] B Bollobas. Graduate Texts in Mathematics, Modern Graph Theory. Springer Sci- ence+Business Media, Inc., New York, 1998. [3] R Brooks. On coloring the nodes of a network. Proc. Cambridge Philos. Soc., 37:194– 197, 1941. [4] J Filar M Haythorpe and G Nguyen. A conjecture on the prevalence of cubic bridge graphs. Discussiones Mathematicae. Graph Theory, 30(1):175–179, 2010. [5] G Chartrand L Lesniak and P Zhang. Textbook in Mathematics, Graph and Digraphs, Sixth Edition. CRC Press, Sound Parkway NW, Suite 300, 2016. [6] D West. Introduction to Graph Theory, Second Edition . Pearson Education, Inc, Singapore, 2001. [7] H Zoeram and D Yaqubi. Spanning k-ended trees of 3-regular connected graph. Elec- tronic Journal of Graph Theory and Application, 5(2):207–211, 2017.