Proof We assume I S 3 0, R. In general, above theorem is valid for the sphere S 3 b, R with the center b. As well as S 3 0, R isometric to S 3 b, R , the truth can be avowable. Now, we give relationship between center and radius of the osculating sphere following. The radii of the osculating spheres at s for all s I is constant iff the centers of the osculating spheres at s are fixed. Proof We assume that the radius of the osculating sphere at s for all s I is constant. On the other hand derivating of the equation 3. Thus the center d s of the osculating sphere at s is fixed. Conversely, let the center d s of the osculating sphere at s for all s I be fixed.
Left hand side this equation is zero. The curve is spherical iff the centers of the osculating spheres at s are fixed. Proof We assume I S 3 b, R. According to Theorem 3. Conversely, according to Theorem 3. The curve is spherical iff rK k. Proof Let the curve be spherical. Derivating equation 3. Hence d s is fixed point. References  A. C oken A. Tuna, On the quaternionic inclined curves in the semi-Euclidean space E24 , Applied Mathematics and Computation, , Sabuncuoglu, Diferensiyel Geometri, Nobel Press, Soyt urk, K.
Ilarslan, D. Saglam, Osculating spheres and osculating circles of a curve in semi-Riemannian space, Commun. Series, A1, 54 2 , Gok, H. Hacsalihoglu, On the quaternionic B2 slant helices in the  F. Kahraman, I. Applied Mathematics and Computation, , Gok, O. Okuyucu, F. Kahraman, H. Hacsalihoglu, On the quaternionic B2 slant  I. Clifford Algebras, 21 , Bharathi, M. Sivridag, Characterisations for the quaternionic inclined curves, Erc.
Karadag, A. Fen Bil. Clifford, Preliminary sketch of biquaternions, Proc. Lourdusamy and T. Mathivanan Department of Mathematics, St. Abstract: Given a graph G and a configuration C of pebbles on the vertices of G, a pebbling step move removes two pebbles from one vertex and places one pebble on an adjacent vertex.
The cover pebbling number G is the minimum number so that every configuration of G pebbles has the property that after some sequence of pebbling steps moves , every vertex has a pebble on it. In this paper we determine the cover pebbling number for square of a path. Key Words: Cover pebbling, square of a path, Smarandachely cover H-pebbling. AMS : 05C78 1. Introduction The game of pebbling was first suggested by Lagarias and Saks as a tool for solving a numbertheoretical conjecture of Erdos.
Chung successfully used this tool to prove the conjecture and established other results concerning pebbling numbers. In doing so she introduced pebbling to the literature . Begin with a graph G and a certain number of pebbles placed on its vertices. A pebbling step consists of removing two pebbles from one vertex and placing one on an adjacent vertex.
In pebbling, the target is selected, and the goal is to move a pebble to the target vertex. The minimum number of pebbles such that regardless of their initial placement and regardless of the target vertex, we can pebble that target is called the pebbling number of G.
In cover pebbling, the goal is to cover all the vertices with pebbles, that is, to move a pebble to every vertex simultaneously. The minimum number of pebbles required such that, regardless of their initial placement on G, there is a sequence of pebbling steps at the end of which every vertex has at least one pebble on it, is called the cover pebbling number of G. In , Crull et al. Hulbert and Munyan  have also announced a proof for the cover pebbling of the n-dimensional cube. In , Maggy Tomova and Cindy Wyles determine the cover pebbling number for cycles and certain graph products.
In the next section, we determine the cover pebbling number for square of a path. Notation 2. Let p vi denote the number of pebbles on the vertex vi and p PA denote the number of pebbles on the path PA. Proof Consider the distribution of eight pebbles on v1. Clearly, we cannot cover at least one of the vertices of P Thus, P42 9. Now, consider the distribution of nine pebbles on the vertices of P If v4 has zero pebbles on it, then using at most four pebbles from P32 : v1 v2 v3 we can move a pebble to v4.
After moving a pebble to v4 , P32 contains at least five pebbles and we are done. Next assume that v4 has at least one pebble. If p v4 4, then p P32 5 and we are done. If p v4 8, then move as many as possible to the vertices of P32 using at most four moves while retaining one or two pebbles on v4 , we cover all the vertices of P42 in these distributions also. Proof Consider the distribution of twelve pebbles on v1.
Thus, P52 Now, consider the distribution of thirteen pebbles on the vertices of P If v5 has zero pebbles on it, then using at most four pebbles from P42 : v1 v2 v3 v4 we can move a pebble to v5. After moving a pebble to v5 , P42 contains at least nine pebbles and we are done. Next assume that v5 has at least one pebble. If p v5 4, then p P42 9 and we are done. If p v5 8, then move as many as possible to the vertices of P42 using at most four moves while retaining one or two pebbles on v5 , we cover all the vertices of P52 in these distributions also.
Proof Consider the following distribution. Next, we are going to prove the upper bound by induction on n. So, assume the result is true for m n If vn has zero pebbles on it, then using at most 2k pebbles from the vertices of 2 2 Pn1 : v1 v2 vn2 vn1 we can cover the vertex vn.
Then Pn1 contains at least. Next, assume that vn has a pebble on it. So, we are done easily if p vn 2 2k 1. Discrete Math. Pachter, H. Snevily and B. Voxman, On pebbling graphs, Congr. Siva Kota Reddy, M. Geetha and K.
Resources :: Algorithmic Combinatorics on Words REU
Abstract: An n-tuple a1 , a2 , In this paper, we introduced a new notion S-antipodal symmetric n-sigraph of a symmetric n-sigraph and its properties are obtained. Also we give the relation between antipodal symmetric n-sigraphs and S-antipodal symmetric n-sigraphs. Further, we discuss structural characterization of S-antipodal symmetric n-sigraphs. Key Words: Symmetric n-sigraphs, Smarandachely symmetric n-marked graph, symmetric n-marked graphs, balance, switching, antipodal symmetric n-sigraphs, S-antipodal symmetric n-sigraphs, complementation.
AMS : 05C22 1. Introduction Unless mentioned or defined otherwise, for all terminology and notion in graph theory the reader is refer to . We consider only finite, simple graphs free from self-loops. Let n 1 be an integer. An ntuple a1 , a2 , Particularly, a Smarandachely 1-marked graph Smarandachely 1-signed graph is called a marked graph signed graph.
Rangarajan and P. Reddy  : Definition 1. Then, i Sn is identity balanced or i-balanced , if product of n-tuples on each cycle of Sn is the identity n-tuple, and ii Sn is balanced, if every cycle in Sn contains an even number of non-identity edges. Note 1. The following characterization of i-balanced n-sigraphs is obtained in . Proposition 1. Sampathkumar et al. Consider the n-marking on vertices of Sn defined as follows: each vertex v V , v is the n-tuple which is the product of the n-tuples on the edges incident with v.
Clearly, Sn as defined here is an i-balanced n-sigraph due to Proposition 1. Then Sn and Sn are said to be isomorphic, if there exists an isomorphism : G G such that if uv is an edge in Sn with label a1 , a2 , , an then u v is an edge in Sn with label a1 , a2 , , an. The n-sigraph obtained in this way is denoted by S Sn and is called the -switched n-sigraph or just switched n-sigraph.
We make use of the following known result see . Consider the n-marking on vertices of S defined as follows: each vertex v V , v is the product of the n-tuples on the edges incident at v. S-Antipodal n-Sigraphs Radhakrishnan Nair and Vijayakumar  has introduced the concept of S-antipodal graph of a graph G as the graph A G has the vertices in G with maximum eccentricity and two vertices of A G are adjacent if they are at a distance of diam G in G.
The following result indicates the limitations of the notion. A Sn as introduced above, since the entire class of i-unbalanced n-sigraphs is forbidden to be S-antipodal n-sigraphs. Proof Since the n-tuple of any edge uv in A Sn is u v , where is the canonical n-marking of Sn , by Proposition 1. In , the authors characterized those graphs that are isomorphic to their S-antipodal graphs. A G if, and only if, G is a regular self-complementary graph. We now characterize the n-sigraphs that are switching equivalent to their S-antipodal n-sigraphs.
Proof Suppose Sn A Sn. Now, if Sn is any n-sigraph with underlying graph as regular selfcomplementary graph, Proposition 2. Therefore, Sn must be i-balanced. Conversely, suppose that Sn is an i-balanced n-sigraph and G is regular self-complementary. Then, since A Sn is i-balanced as per Proposition 2. Remark 2. The above result is holds good for Sn A Sn. In , P. Reddy et al. We now characterize n-sigraphs whose S-antipodal n-sigraphs and antipodal n-sigraphs are switching equivalent.
In case of graphs the following result is due to Radhakrishnan Nair and Vijayakumar . Conversely, suppose that G is self centred. Now, if Sn is an n-sigraph with underlying graph as self centred, by Propositions 2. We now characterize n-sigraphs whose A Sn and A Sn are switching equivalent. Since Sn is i-balanced, by Proposition 1. Hence Sn is a S-antipodal n-sigraph. Complementation In this section, we investigate the notion of complementation of a graph whose edges have signs a sigraph in the more general context of graphs with multiple signs on their edges. We look at two kinds of complementation: complementing some or all of the signs, and reversing the order of the signs on each edge.
We now examine, the condition under which m-complement of A Sn is i-balanced, where for any m Hn. Proof Since, by Proposition 2. This implies that the same thing is true in any m-complement, where for any m, Hn. Hence A Sn t is i-balanced. Lokesha, P. Reddy and S. Vijay, The triangular line n-sigraph of a symmetric nsigraph, Advn. Radhakrishnan Nair and A. Vijaykumar, S-Antipodal graphs, Indian J. Reddy, Notions of balance in symmetric n-sigraphs, Proceedings of the Jangjeon Math.
Rangarajan, P. Reddy and M. Reddy and N. Soner, Switching equivalence in symmetric n-sigraphsII, J. Orissa Math.
Sampathkumar, P. Reddy, and M. Subramanya, Jump symmetric n-sigraph, Proceedings of the Jangjeon Math. Singleton, There is no irregular moore graph, Amer. Monthly, 75 , Reddy and B. Prashanth, Switching equivalence in symmetric n-sigraphs-I, Advances and Applications in Discrete Mathematics, 4 1 , Reddy, S. Vijay and B. Prashanth, The edge C4 n-sigraph of a symmetric n-sigraph, Int.
Journal of Math. Reddy, V. Open Problems in Computer Science and Mathematics, 3 5 , Reddy, B. Prashanth and Kavita. Reddy, M. Abstract: We prove that closed helm CHn , web graph W bn , flower graph F ln , double triangular snake DTn and gear graph Gn admit product cordial labeling. Key Words: Graph labeling, cordial labeling, Smarandachely p-product cordial labeling, product cordial labeling. For any undefined notations and terminology we rely upon Clark and Holton . In order to maintain compactness we provide a brief summery of definitions and existing results. Definition 1. If the domain of the mapping is the set of vertices or edges then the labeling is called a vertex labeling or an edge labeling.
According to Beineke and Hegde  labeling of discrete structure serves as a frontier between graph theory and theory of numbers. A dynamic survey of graph labeling is carried out and frequently updated by Gallian . Let us denote vf 0 , vf 1 be the number of vertices of G having labels 0 and 1 respectively under f and let ef 0 , ef 1 be the number of edges of G having labels 0 and 1 respectively under f.
A graph G is called cordial if it admits cordial labeling. The concept of cordial labeling was introduced by Cahit  in which he investigated several results on this newly defined concept. After this some labelings like prime cordial labeling, A cordial labeling, H-cordial labeling and product cordial labeling are also introduced as variants of cordial labeling. This paper is aimed to report some new families of product cordial graphs. A graph with product cordial labeling is called a product cordial graph.
The product cordial labeling was introduced by Sundaram et al. The graphs obtained by joining apex vertices of k copies of stars, shells and wheels to a new vertex are proved to be product cordial by Vaidya and Dani  while some results on product cordial labeling for cycle related graphs are reported in Vaidya and Kanani .
Vaidya and Barasara  have proved that the cycle with one chord, the cycle with twin chords, the friendship graph and the middle graph of path admit product cordial labeling. The same authors in  have proved that the graphs obtained by duplication of one edge, mutual vertex duplication and mutual edge duplication in cycle are product cordial graphs. Vaidya and Vyas  have discussed product cordial labeling in the context of tensor product of some graphs while Vaidya and Barasara  have investigated some results on product cordial labeling in the context of some graph operations.
The vertex corresponding to K1 is known as apex vertex and vertices corresponding to cycle are known as rim vertices while the edges corresponding to cycle are known as rim edges. We continue to recognize apex of respective graphs obtained from wheel in Definitions 1. Main Results Theorem 2. Proof Let v be the apex vertex, v1 , v2 ,. Hence CHn is a product cordial graph. Hence W bn 2 admits product cordial labeling. Let F ln be the flower graph obtained from helm Hn.
Hence F ln admits product cordial labeling. Subcase 1. Hence DT2 is not a product cordial graph. Subcase 2. The vertices with label 0 will give rise at least 2 5n 5n 1 edges with label 0 and at most 4 edge with label 1 out of total 5n 5 edges. Thus the edge condition for product cordial graph is violated. Therefore DTn is not a product cordial graph for even n. Hence Double triangular snake DTn is a product cordial graph for odd n and not a product cordial graph for even n. Illustration 2. Proof Let Wn be the wheel with apex vertex v and rim vertices v1 , v2 , , vn.
To obtain the gear graph Gn subdivide each rim edge of wheel by the vertices u1 , u2 , , un. So Gn is not a product cordial graph for even n. Hence gear graph is a product cordial graph for odd n and not product cordial graph for even n. Concluding Remarks Some new families of product cordial graphs are investigated. To investigate some characterization s or sufficient condition s for the graph to be product cordial is an open area of research.
Acknowledgement The authors are deeply indebted to the referee for critical comments and suggestions. References  L. Beineke and S. Hegde, Strongly Multiplicative graphs, Discuss. Graph Theory, 21 , Clark and D. Sundaram, R. Ponraj and S. Somasundaram, Product cordial labeling of graphs, Bull. Vaidya and N. Dani, Some new product cordial graphs, Journal of App. Vaidya and K. Kanani, Some cycle related product cordial graphs, Int. Vaidya and C. Barasara, Product cordial labeling for some new graphs, Journal of Mathematics Research, 3 2 , Barasara, Some product cordial graphs, Elixir Discrete Mathematics, 41 , Vyas, Product cordial labeling in the context of tensor product of graphs, Journal of Mathematics Research, 3 3 , Barasara, Product cordial graphs in the context of some graph operations, International Journal of Mathematics and Scientific Computing, 1 2 , The Berge conjecture states that a graph H is perfect if and only if H is berge.
The Berge conjecture see  or  or  or  or  or  or  or  or  was proved by Chudnovsky, Robertson, Seymour and Thomas in a paper of at least pages see  , and an elementary proof of the Berge conjecture was given by Ikorong Nemron in a detailled paper of 37 pages long see . The Hadwiger conjecture see  or  or  or  or  or  or  or  or  or  was proved by Ikorong Nemron in a detailled paper of 28 pages long see  , by using arithmetic calculus, arithmetic congruences, elementary complex analysis, induction and reasoning by reduction to absurd.
That being so, in this paper, via two simple Theorems, we rigorously show that the difficult part of the Berge conjecture solved and the Hadwiger conjecture also solved , are exactly the same conjecture. The previous immediately implies that, the Hadwiger conjecture is only a non obvious special case of the Berge conjecture. Key Words: True pal, parent, berge, the berge problem, the berge index, representative, the hadwiger index, son. The Berge conjecture states that a graph H is perfect if 1 Received.
Briefly, the difficult part of the Berge conjecture will be called the Berge problem. In this topic, we rigorously show that the Berge problem and the Hadwiger conjecture are exactly the same problem [the Hadwiger conjecture states that every graph G is G colorable i.
G is the hadwiger number of G and is the maximum of p such that G is contractible to the complete graph Kp ]. That being so, this paper is divided into six simple Sections. In Section 1, we present briefly some standard definitions known in Graph Theory. In Section 2 , we introduce definitions that are not standard, and some elementary properties. In Section 3 we define a graph parameter denoted by is called the berge index and we give some obvious properties of this parameter. In Section 4 we introduce another graph parameter denoted by is called the hadwiger index and we present elementary properties of this parameter.
In Section 5 , using the couple , , we show two simple Theorems which are equivalent to the Hadwiger conjecture and the Berge problem. In Section 6, using the two simple Theorems stated and proved in Section 5, we immediately deduce that the Berge problem and the Hadwiger conjecture are exactly the same problem, and therefore, the Hadwiger conjecture is only a non obvious special case of the Berge conjecture.
In this paper, all results are simple, and every graph is finite, is simple and is undirected. We start. A clique of G is a subgraph of G that is complete; such a subgraph is necessarily an induced subgraph recall that a graph K is complete if every pair of vertices of K is an edge of K ; G is the size of a largest clique of G, and G is called the clique number of G. A stable set of a graph G is a set of vertices of G that induces a subgraph with no edges; G is the size of a largest stable set, and G is called the stability number of G.
The chromatic number of G denoted by G is the smallest number of colors needed to color all vertices of G such that two adjacent vertices do not receive the same color. It is easy to see: Assertion 1. The hadwiger number of a graph G denoted by G , is the maximum of p such that G is contractible to the complete graph Kp. Recall that, if e is an edge of G incident to x and y, we can obtain a new graph from G by removing the edge e and identifying x and y so that the resulting vertex is incident to all those edges other than e originally incident to x or to y. If a graph F can be obtained from G by a succession of such edge-contractions, then, G is contractible to F.
The maximum of p such that G is contractible to the complete graph Kp is the hadwiger number of G, and is denoted by G. The Hadwiger conjecture states that G G for every graph G. Clearly we have: Assertion 1. Non-Standard Definitions and Some Elementary Properties In this section, we introduce definitions that are not standard. These definitions are crucial for the two theorems which we will use in Section 6 to show that the Berge problem and the Hadwiger conjecture are exactly the same problem.
We say that a graph B is berge, if every does not contain an induced cycle of odd length 5. The Berge conjecture states that a graph G is perfect if and only if G is berge. Indeed, the Berge problem i. We will see in Section6 that the Berge problem and the Hadwiger conjecture are exactly the same problem. So, G means G is a complete G -partite graph. Using the definition of , then the following Assertion becomes immediate.
Assertion 2. Then we have the following two properties. Proof Property 2. Property 2. Using the definition of a parent, then the following Assertion is immediate. We have the folowing two properties. The Berge Index of a Graph In this section, we define a graph parameter called the berge index and we define a representative of a graph; we also give some elementary properties concerning the berge index.
We recall that does not contain an induced cycle of odd length 5. Using the definition of a berge graph and the definition of the following assertion becomes immediate. Assertion 3. Then, G is berge. Now, we define the berge index of a graph G. Let G be a graph. Then the berge index of G denoted by G is defined in the following two cases namely case where G and case where G 6.
First, we define the berge index of G in the case where G. We prove that such a clearly exists via the following remark. Remark i Suppose that G. Then, the berge index G exists. Recall G , so G is berge use Assertion 3. Suppose that G 6 and let parent G be the set of all parents of G. Then, min P. We prove that such a clearly exists, via the following remark. Remark ii Suppose that G 6. Indeed, let P such that P is a true pal of G [such a P exists use property 2. So min P P parent G.
Remark iii Let G be a graph. Then the berge index G exists. In fact, applying Remark i if G , and Remark ii if G 6 , we get the conclusion. To conclude, note that the berge index of a graph G is G , where G is defined as follows. Then, we have the following three properties. Proof Property 3. We prove property 3. Property 3. Now we prove property 3.
Then, P B. Now, we define a representative of a graph. Let G be a graph and let G be the berge index of G [observe G exists, by using Remark iii]; we say that a graph S is a representative of G if S is defined in the following two cases namely case where G and case where G 6. First, we define a representative of G in the case where G. Case i Suppose that G. Via Remarks i and i. Then, there exists a graph S such that S is a representative of. Remark i. Now let S be a representative of G such a S exists, by using Remark i. Now, we define a representative of G, in the case where G 6.
Case ii Suppose that G 6. Via Remarks ii and Remark ii. Then, there exists a graph S such that S is a representative of G. Now, let F B P. It is easy to see that B is a representative of G. Remark ii. Now let S be a representative of G such a S exists by using Remark ii. Applying Remark i if G and applying Remark ii if G 6 , we get the conclusion. Applying Remark i.
To conclude, note that a graph S is a representative of a graph G if S is defined in the following two cases. Suppose that G. Suppose that G 6. We will see in Section 5 that the berge index and a representative help to obtain an original reformulation of the Berge problem, and this original reformulation of the Berge problem is crucial for the result of Section 6 which clearly implies that the Hadwiger conjecture is only a non obvious special case of the Berge conjecture.
The Hadwiger Index of a Graph Here, we define the hadwiger index of a graph and a son of a graph, and we also give some elementary properties related to the hadwiger index. Using the definition of a true pal, the following assertion is immediate. Assertion 4. Then, there exists a graph S such that G is a true pal of S and S is minimum for this property.
Now we define the hadwiger index and a son. In other terms again, a graph S is a son of G, if G is a true pal of S and S is minimum for this property. Observe that such a son exists, via Assertion 4. We recall that G is the berge index of G, and we clearly have. We have the following three properties. Proof Properties 4. Now we show property 4. So K A G and clearly. Using the definition of , the following proposition becomes immediate.
Then G F. Then P F. Proof Observe that P trpl F and apply Proposition 4. We will see in Section 5 that the hadwiger index and a son help to obtain an original reformulation of the Hadwiger conjecture, and this original reformulation of the Hadwiger conjecture is also crucial for the result of Section 6 which clearly implies that the Hadwiger conjecture is only a non obvious special case of the Berge conjecture. An Original Reformulation of the Berge Problem and the Hadwiger Conjecture In this section, we prove two simple Theorems which are equivalent to the Berge problem and the Hadwiger conjecture.
Mathematical Combinatorics, international book series, Vol. 3, 2012
These original reformulations will help in Section 6 to show that the Berge problem and the Hadwiger conjecture are exactly the same problem. That being so, using the berge index , then the following first simple Theorem is an original reformulation of the Berge problem. So 1 2 ], and Theorem 5. Using the hadwiger index , then the following is a corresponding original reformulation of the Hadwiger conjecture.
So H H , and clearly 3 1. So 1 2 ] and Theorem 5. Conclusion Indeed, the following two theorems follow immediately from Theorems 5. Proof Indeed, it is an immediate consequence of Theorem 5. Using Theorems 6. Proof Indeed observing that the Berge conjecture is true see  or see  , then in particular the Berge problem is true. Now using Theorem 6. That being so, noticing that the Hadwiger conjecture is true see  and using Theorem 6. Proof It is immediate to see that the Berge conjecture implies the Berge problem. Now by Theorem 6. That being so, using 6.
Berge, Graphs Chap. M11 , Saaty and Paul C. Graphs and Cellular Foldings of 2-Manifolds E. Abstract: In this paper we considered the set of regular CW-complexes or simply complexes. We obtained the necessary and sufficient condition for the composition of cellular maps to be a cellular folding. Also the necessary and sufficient condition for the composition of a cellular folding with a cellular map to be a cellular folding is declared. Then we proved that the Cartesian product of two cellular maps is a cellular folding iff each map is a cellular folding.
By using these results we proved some other results. Once again we generalized the first three results and in each case we obtained the folding graph of the new map in terms of the original ones. Key Words: Graph, cellular folding, 2-manifold, Cartesian product. AMS : 57M10, 57M20 1. Introduction A cellular folding is a folding defined on regular CW-complexes first defined by E.
El-Kholy and H.
MATHEMATICAL COMBINATORICS (INTERNATIONAL BOOK SERIES), Volume 3 / 2012
Al-Khursani , and various properties of this type of folding are also studied by them. By a cellular folding of regular CW-complexes, it is meant a cellular map f : K L which maps i-cells of K to i- cells of L and such that f ei for each i-cells e is a homeomorphism onto its image. The set of all singularities of f is denoted by f.
This set corresponds P to the folds of map. It is noticed that for a cellular f , the set f of singularities of f is a proper subset of the union of cells of dimension n 1. Thus, when we consider any f C K, L , P where K and L are connected regular CW-complexes of dimension 2, the set f will consists P of 0- cells, 1-cells, and each 0-cell vertex has an even valency .
Of course, f need not be P connected. Thus in this case f has the structure of a locally finite graph f embedded in K, for which every vertex has an even valency. Note that if K is compact, then f is finite, also any 1 Received. Let K and L be complexes of the same dimension n. A neat cellular folding f : K L is a cellular folding such that Ln Ln1 consists of a single n-cell, IntL that is f satisfies the following: i f maps i-cells to i-cells; ii for each e which contains n vertices, f e is mapped on the single n- cell, IntL, . This category is a subcategory of cellular foldings C K, L.
From now we mean by a complex a regular CW-complex in this paper. Then g f is a S cellular folding iff f and g are cellular foldings. Then f form a graph f embedded in M. Thus g f is a cellular folding. Now, let M i be an i-cell in M. Then since f is a cellular map, then j i. But g f is a cellular folding, thus g f is an i- cell in L and so is g. Note that the above theorem is true if we consider f and g are neat cellular foldings instead of cellular folding.
The folding graph f is shown Fig. See Fig. Again g is a cellular folding and the folding graphs g and f 1 g are shown in Fig. In this case the folding graphs satisfy the condition. Then a cellular map g : N L is a cellular folding iff g f : M L is a cellular folding. Conversely, suppose g : N L is a cellular folding. Since f : M N is a cellular folding, by Theorem 2. Notice that this conclusion is also true if we consider g and g f neat cellular foldings instead of cellular foldings. Now, let L be a 2-cell with boundary consists of three 0-cells and three 1-cells , see Fig.
The folding graph h is shown in Fig. The cellular folding h is the composition of f with a cellular folding g : N L which folds N onto L. The graph g is given is given in Fig. Then a cellular map fn : Mn1 Mn is a cellular folding iff the composition fn fn1 f1 :. M Mn is a cellular folding. Let f : K X and g : L Y be cellular maps. Then f g. Suppose now f g is a cellular folding, then f g maps p-cells to p-cells, i.
The all cellular maps must map i-cells to j-cells such that j i. In this case g will map p i -cells to p j -cells and hence it is not a cellular map. The second condition of cellular folding certainly satisfied in this case. Now f g : K L K L is a cellular folding but not neat. In this case, f g has the form shown in Fig. In this case, f1 f2 fn. Also, since f : A A1 , g : B B1 are cellular foldings, then so is. The above theorem can be generalized for a finite number of cellular foldings. The cellular foldings f g, h k and the folding graphs f g , hk , hk f g are shown in Fig.
Also the cellular folding h f , k g and the folding graphs hf , kg , hf kg are shown in Fig. This is due to the fact that fei with ei an i-cell of X, is a homeomorphism onto its image and in the case of neat cellular folding of surfaces the image, Y must has only one 2-cell, IntY , and thus the restriction of f to any subcomplex of X will maps each 2-cells of A onto the 2-cell of Y and it does so for the 0 and 1-cells of A since f in fact is cellular. Consequently f A is a neat cellular folding of A to Y.
Now let A X shown in Fig. References  El-Kholy E. A1, Vol. Mahadevan , Selvam Avadayappan, J. Paulraj Joseph and T. Abstract: The concept of triple connected graphs with real life application was introduced in  by considering the existence of a path containing any three vertices of a graph G.
In this paper, we introduce a new domination parameter, called Smarandachely triple connected domination number of a graph. A subset S of V of a nontrivial graph G is said to be Smarandachely triple connected dominating set, if S is a dominating set and the induced sub graph hSi is triple connected. The minimum cardinality taken over all Smarandachely triple connected dominating sets is called the Smarandachely triple connected domination number and is denoted by tc. We determine this number for some standard graphs and obtain bounds for general graphs. Its relationship with other graph theoretical parameters are also investigated.
Key Words: Domination number, triple connected graph, Smarandachely triple connected domination number. AMS : 05C69 1. Introduction By a graph we mean a finite, simple, connected and undirected graph G V, E , where V denotes its vertex set and E its edge set. Unless otherwise stated, the graph G has p vertices and q edges.
Degree of a vertex v is denoted by d v , the maximum degree of a graph G is denoted by G. We denote a cycle on p vertices by Cp , a path on p vertices by Pp , and a complete graph on p vertices by Kp. A graph G is connected if any two vertices of G are connected by a path. A maximal connected subgraph of a graph G is called a component of G.
The number of components of G is denoted by G. The complement G of G is the graph with vertex set V in which two vertices are adjacent if and only if they are not adjacent in G. A tree is a connected acyclic graph. A bipartite graph or bigraph is a graph whose vertex set can be divided into two disjoint sets V1 and V2 such that every edge has one end in V1 and another end in V2.
A complete bipartite graph is a bipartite graph where every vertex of V1 is adjacent to every 1 Received. A star, denoted by K1,p1 is a tree with one root vertex and p 1 pendant vertices. A bistar, denoted by B m, n is the graph obtained by joining the root vertices of the stars K1,m and K1,n. A wheel graph, denoted by Wp is a graph with p vertices, formed by joining a single vertex to all vertices of Cp1. A helm graph, denoted by Hn is a graph obtained from the wheel Wn by attaching a pendant vertex to each vertex in the outer cycle of Wn.
Corona of two graphs G1 and G2 , denoted by G1 G2 is the graph obtained by taking one copy of G1 and V G1 copies of G2 in which ith vertex of G1 is joined to every vertex in the ith copy of G2. The diameter of a connected graph is the maximum distance between two vertices in G and is denoted by diam G. A cut-vertex cut edge of a graph G is a vertex edge whose removal increases the number of components. A vertex cut, or separating set of a connected graph G is a set of vertices whose removal results in a disconnected graph. The connectivity or vertex connectivity of a graph G, denoted by G where G is not complete is the size of a smallest vertex cut.
The chromatic number of a graph G, denoted by G is the smallest number of colors needed to colour all the vertices of a graph G in which adjacent vertices receive different colours. For any real number x, x denotes the largest integer less than or equal to x. A Nordhaus-Gaddum-type result is a tight lower or upper bound on the sum or product of a parameter of a graph and its complement. Terms not defined here are used in the sense of . The domination number G of G is the minimum cardinality taken over all dominating sets in G.
A dominating set S of a connected graph G is said to be a connected dominating set of G if the induced sub graph hSi is connected. The minimum cardinality taken over all connected dominating sets is the connected domination number and is denoted by c. Many authors have introduced different types of domination parameters by imposing conditions on the dominating set . Recently, the concept of triple connected graphs has been introduced by Paulraj Joseph et. They have studied the properties of triple connected graphs and established many results on them.
A graph G is said to be triple connected if any three vertices lie on a path in G. All paths, cycles, complete graphs and wheels are some standard examples of triple connected graphs. In this paper, we use this idea to develop the concept of Smarandachely triple connected dominating set and Smarandachely triple connected domination number of a graph. Notation 1. The graph obtained from G by attaching n1 times a pendant vertex of Pl1 on the vertex v1 , n2 times a pendant vertex of Pl2 on the vertex v2 and so on, is denoted by G n1 Pl1 , n2 Pl2 , n3 Pl3 ,. Example 1. The graph K4 2P2 , P3 , P4 , P3 is obtained from K4 by attaching 2 times a pendant vertex of P2 on v1 , 1 time a pendant vertex of P3 on v2 , 1 time a pendant vertex of P4 on v3 and 1 time a pendant vertex of P3 on v4 and is shown in Figure 1.
Triple Connected Domination Number Definition 2. The minimum cardinality taken over all Smarandachely triple connected dominating sets is called the Smarandachely triple connected domination number of G and is denoted by tc G. Any Smarandachely triple connected dominating set with tc vertices is called a tc -set of G. Observation 2. For the graph G5 in Figure 2. Proof The proof follows from Theorem 1. Some exact value for some standard graphs are listed in the following: 1.
Let P be the petersen graph. Here we notice that the induced subgraph of S has three pendant vertices and hence G does not contain a triple connected dominating set. If H has a triple connected dominating set, then tc G tc H and the bound is sharp. Since S is a dominating set, there exists a vertex vi in S such that vi is adjacent to x. If p 5, by taking the vertex vi , we can construct a triple connected dominating set S with fewer elements than p 1, which is a contradiction.
Hence p 4. Now by adding. Proof The lower bound follows from Definition 2. Consider the dodecahedron graph G10 in Figure 2. For P5 , the lower bound is attained and for C9 the upper bound is attained. Since G is connected, there exists a vertex say y in P3 is adjacent to u or v in K2. In all the other cases, no new graph exists. Since G is connected, there exists a vertex say y in P3 which is adjacent to u and v in K 2. Since G is connected, there exists a vertex say x in P3 which is adjacent to u in K 2 and y in P3 is adjacent to v in K 2. Since G is connected, there exists a vertex say x in P3 which is adjacent to u in K 2 and z in P3 which is adjacent to v in K 2.
Since G is connected, there exists a vertex say x or y, z in C3 is adjacent to u in K 2 and y or z in C3 is adjacent to v in K 2. In all other cases, no new graph exists. Suppose hSi is not a tree. Then hSi contains a cycle. Since G is connected and S is a tc -set of G, vp1 or vp is adjacent to a vertex vk in hSi.
Suppose vp1 or vp is adjacent to a vertex vi in hSi C, then we can construct a tc -set which contains vp1 , vi with fewer elements than p 2, which is a contradiction. Hence hSi is a tree. Deza, M. Petitjean, K. Markov Eds. Colbourn, J. Dinitz Eds. Dinitz, D. Lamb and D. Colbourn, S. Magliveras, R. Mathon, Transitive Steiner and Kirkman triple systems of order 27, Math. Colbourn, R. Mathon, On cyclic Steiner 2-designs. Topics on Steiner systems, Ann. Discret Math. Genma, M. Mishima, M. Jimbo, Cyclic resolvability of cyclic Steiner 2-designs, J.
Gruner, M. Huber, New combinatorial construction techniques for low-density parity-check codes and systematic repeat-accumulate codes, IEEE Trans.
Edited By Linfan MAO
Huber, Combinatorial designs for authentication and secrecy codes, Found. Trends Commun. Theory 5 6 — Johnson, S. Kageyama, A survey of resolvable solutions of balanced incomplete block designs, Int. Lam, Y. Miao, On cyclically resolvable cyclic steiner 2-designs, J. Theory Ser. A 85 2 —