The error constant of 3. Now following cases arise: Case 1. Pn From 2. From 2. The method 3. To solve this method, we have at least 2 data points and the order of 3. To solve this method, we have at least 3 data points. Case 4. Following previous case we get the same as 3. The order of 3. Note 3. The error of trapezoidal rule is, from 3. The error Simpson rd rule of is, from 3. The weights of the integration method of 3. Problems Problem 6. Problem 6. Solution Let P2n be the quadratic equation by fit n equal space data points in [0, 1]. Using the exact solution, find the absolute errors.
In this method Ln2 weights are increasing from a to midpoint i. We have given the MATLAB code also, give any continuous function f x on [a, b] that will be give an approximation integration value of f x from a to b. Also, we are developing this concept to high degree polynomials and high dimension. References  M. Chichester, England. Smith, , Numerical Integration, Encyclopedia of Biostatistics. Sucharitha, Open-type quadrature methods with equispaced nodes and maximal polynomial degree of exactness, International Journal of Mathematics And Applications, Vol.
Sucharitha, Numerical integration by using straight line inter- polation formula, Global Journal of Pure and Applied Mathematics, 13, No. K Jain, S. Iyengar, R. In this way, we determine time dependent linear and angular differential properties of motion such as velocity and acceleration which play important roles in robot trajectory planning.
Moreover, motion of a robot end-effector which can be represented by a right conoid and an additional parameter called spin angle is investigated as a practical example. Key Words: Blaschke frame, curvature theory, robot end-effector, robot trajectory plan- ning, ruled surface. Introduction In robotics, a robot end-effector is a device at the end of a robotic arm. Robot end-effectors are widely used in transportation, welding industry, medical science, military and many other areas.
Recently, they can be used in the research areas which have critical importance of accurate motion such as surgical operations and bomb disposal. So accurate trajectory planning of a robot end-effector becomes an important research area of robotics. In this area, one of the most interesting problems is determining time dependent differential properties of motion of a robot end-effector which are linear and angular velocities and accelerations.
These differential properties play important roles in robot trajectory planning. As a robot end-effector moves on a specified trajectory in space, a line fixed in the end- effector generates a ruled surface . There is an important relationship between time depen- dent properties of motion of the robot end-effector and differential geometry of the ruled surface.
By using this relationship, Ryuh and Pennock proposed a method based on the curvature theory of a ruled surface generated by a line fixed in the end-effector to determine linear and angular properties of motion [12, 13, 14]. After that, this research area was also studied in Lorentzian space. Ekici et al. Blaschke Approach to the Motion of a Robot End-Effector 43 determined differential properties of motion of a robot end-effector whose trajectory is a null curve .
Other Mathematical Olympiads
On the other hand, there is also an efficient relationship between directed lines and dual unit vectors. By the aid of this correspondence, W. Blaschke defined a frame called Blaschke frame on a ruled surface by taking directed lines pass through striction curve of the ruled surface instead of real unit vectors used in Frenet frame of ruled surface. He also gave some invariants which characterize the shape of a ruled surface.
Several authors used Blaschke frame in their researches concerning with kinematics, spatial mechanisms and many other areas [1, 2, 18]. In this paper, we use the relationships between kinematic, ruled surfaces and dual vector algebra. First, we represent motion of a robot end-effector on a specified trajectory in space as a ruled surface generated by a line fixed in the end-effector and an additional parameter called spin angle.
We define a dual frame called dual tool frame on robot end-effector in order to obtain a relationship between Blaschke frame of the ruled surface, which is used to study the differential geometry of a ruled surface by means of dual quantities, and time dependent differential properties of robot end-effector. By using this relation, we determine time dependent differential properties of motion of a robot end-effector which are linear translational and angular rotational velocities and accelerations.
These differential properties have important roles in robot trajectory planning. In this method, we use just a dual vector called dual instantaneous rotation vector of dual tool frame to determine the differential properties. So, this method has more advantages than traditional methods which based on matrix representations in terms of being simple and systematic. Preliminaries In this section, we give a brief summary of basic concepts for the reader who is not familiar with dual numbers, dual vectors and dual space.
As introduced by W. The set of all dual numbers can be denoted by D. The set D is a commutative ring, not a field. The set of all dual vectors is a module over the ring D and is called dual space or D-module, denoted by D3 , . A Robot End-Effector and its Dual Tool Frame In this section, we introduce tool frame of a robot end-effector which consists of three mutually perpendicular unit vectors described by Ryuh and Pennock  in detail.
Then, we represent motion of a robot end-effector by using a ruled surface generated by a line fixed in the end- effector and an additional parameter called spin angle. By taking three lines instead of three unit vectors, we define a dual frame called dual tool frame on robot end-effector which will be used to study the motion. The tool frame consists of three orthogonal unit vectors strictly attached to robot end- effector.
These are; orientation vector O which is a unit vector in the direction of the gripper motion as it opens and closes, approach vector A which is a unit vector in the direction normal to the palm of robot end-effector, and normal vector N which is a unit vector in the direction perpendicular to the plane of the gripper see Figure 1 , . The origin of the tool frame is called tool center point and denoted by TCP. By using tool frame and tool center point, location and orientation of a robot end-effector can be described completely.
Blaschke Approach to the Motion of a Robot End-Effector 45 As a robot end-effector moves on a specified trajectory in space, a line called tool line fixed in the end-effector which passes through TCP and whose direction vector is parallel to the orientation vector O generates a ruled surface . During motion, the approach vector A may not be always perpendicular to the ruled surface. As seen in Figure 1, there may be an angle between the approach vector A and the surface normal vector on the directrix which is denoted by Sn.
Thus, a robot end-effector motion which has six degrees of freedom in space can be completely described by a ruled surface generated by a line in robot end-effector which provides five independent parameters and a spin angle. These lines pass through the TCP and their direction vectors are the orientation vector O, the approach vector A and the normal vector N , respectively. From Theorem 2. Blaschke Approach to the Motion In this section, we give Blaschke frame of a ruled surface generated by a line fixed in the robot end-effector.
By relating Blaschke frame and dual tool frame, we determine linear and angular differential properties of motion. Furthermore, we give corollaries for some special cases of motion. The dual Pfaff vector is considered as dual velocity vector in dual spherical motion see ref. This dual motion contains both rotational and translational motion in real space. Thus, linear and angular velocities and accelerations which are important dif- ferential properties of motion of a robot end-effector are found in terms of the parameter s which is the arc-length parameter of striction curve of the generating ruled surface.
In order to determine time dependent differential properties, the vectors given in equations 4 , 5 , 7 and 8 should be related to the parameter of time. Now, we give time dependent linear and angular differential properties of motion of a robot end-effector as corollaries. Now, we consider some special cases of motion of a robot end-effector and give some corollaries about these cases. Case 1. Then, the derivative of the spin angle is equal to zero. For this case, by substituting the value of spin angle into equations 4 , 5 , 7 , and 8 , and by rearranging these equations, we can give time dependent linear and angular differential properties of the motion of a robot end-effector as in the following corollaries.
Corollary 4. A specified trajectory which robot end-effector follows may be striction curve of ruled surface generated by a line fixed in the robot end-effector. Namely, directrix and striction curve of generating ruled surface may be the same curve. For this case, by rearranging equations 4 , 5 , 7 , and 8 , we can give time dependent linear and angular differential properties of the motion of a robot end-effector as in the following corollaries. Ruled surface generated by a line fixed in a robot end-effector may be a developable ruled surface except a cylinder and a cone.
For this case, by making the necessary arrangement in equations 4 , 5 , 7 , and 8 , we can give time dependent linear and angular differential properties of the motion of a robot end-effector as in the following corollaries. Since directrix is also striction curve, the distance between these curves equals to zero, i. Conclusions In this paper, time dependent differential properties which are linear and angular velocities and accelerations of the motion of a robot end-effector are determined by using Blaschke approach of a ruled surface generated by a line fixed in the end-effector.
These differential properties are important information in robot trajectory planning. By the aid of Blaschke approach which uses dual numbers and dual vectors as basic tool, both linear and angular differential properties can be determined. This is achieved only by using a dual vector which is dual instantaneous rotation vector of dual tool frame.
Thus, Blaschke approach presents a simple and systematic method to study motion of a robot end-effector without redundant parameter. This paper does not contain a computer program which compares Blaschke approach and conventional method of scalar curvature theory of ruled surfaces in real space. This is the subject of ongoing research works. However, it is believed that the presented method based on Blaschke approach will reduce computation time in computer programming for determining differential properties of motion and contribute to research area of robot trajectory planning. References  Abdel-Baky, R.
We discuss nonzero real domination roots of these graphs. We also investigate whether all the domination roots of some graphs lying left half plane or not. Key Words: Dominating set, Smarandachely k-dominating set, domination number, dom- ination polynomial, domination root, d-number, stable. AMS : 05C Introduction Let G V, E be a simple finite graph.
The order of G is the number of vertices of G. Generally, a dominating set S is said to be a Smarandachely k-dominating set if each vertex of G is dominated by at least k vertices of S. For more information on this polynomial the reader may refer to . A root of D G, x is called a domination root of G.
It is easy to see that the domination polynomial is monic with no constant term. Consequently, 0 is a root of every domination polynomial in fact, 0 is a root whose multiplicity is the domination number of the graph. So we introduce a new definition as follows. The number of distinct real domination roots of the graph G is called d-number of G and is denoted by d G. Proof It follows from the fact that 0 is a domination root of any graph. Proof It follows from the fact that 0 is a domination root and complex roots occurs in conjugate pairs.
Therefore by the intermediate value theorem, h y has at least one real root in 0, 1. Therefore we can conclude that h y has exactly one real root for odd n and two real roots for even n. It remains to show that all the real roots of f x are distinct. Proof Let v be the center vertex of Gn3. Proof By Theorem 2.
Therefore by the intermediate value theorem, we have the result. Proof It follows from the fact that the n-barbell graph Bn,1 and the generalized barbell graph Bn,n,1 are isomorphic. A bi-star graph B m,n is a tree obtained from the graph K2 with two vertices u and v by attaching m pendant edges in u and n pendant edges in v. Clearly there is no one element dominating set. The remaining proof is similar to the proof of Theorem 2. Proof The proof similar to the proof of Theorem 2.
The graph Q m, n is obtained by identifying each vertex of Km with a vertex of a unique Kn. Domination Stable Graph In this section we introduce d-stable and d-unstable graphs. We obtained some examples of d-stable and d-unstable graphs. Definition 3. The graph G is said to be a domination stable graph or simply d-stable graph if all the nonzero domination roots of G lie in the left open half-plane, that is, if real part of the nonzero domination roots is negative.
If G is not d-stable graph, then G is said to be a domination unstable graph or simply d-unstable graph. Proof Suppose G is d-stable. This implies that Kn is d-stable for all n. Proof It follows from the fact that the graph Kn has no nonzero domination roots. These definitions and theorems are taken from . The number k is the order of the recurrence. The details are available in . Beraha, Kahane and Weiss  proved the following results on recursive families of polynomials and their roots.
Then the limits of roots of fn x are exactly those z satisfying 1 or 2 of Theorem 3. Proof We have known by Theorem 2. This implies that the generalized barbell graph Bm,n,1 is d-stable for all m, n. If D G, x has exactly two distinct domination roots, then G is d-stable for all n. Proof It follows from the fact that the two distinct roots are real. If D G, x has exactly three distinct roots, then G is d-stable. Therefore the initial conditions of Theorem. This implies that the domination roots of Gn3 have unbounded positive real part.
Therefore the Dutch windmill graph Gn3 is not d-stable for all but finite values of n. Remark 3. Therefore the initial conditions of Theorem 3. Therefore we think that that there is no complex number z with positive real part is a root of D Sn , x. We conjectured that the star graph Sn is d-stable graph for all n. Now, applying part i of Theorem 3. Domination Stable Graphs 71 Case 1. So we conjectured that the complete bipartite graph Km,n is d-stable for all m, n. But from the Remark 3. So we conjectured that the bi-star graph B m,n is d-stable for all m, n.
Vijayan and S. Alikhani and Y. Peng, Characterization of graphs using Domination Polynomial, European Journal of Combinatorics, 31 7 ,, Studies in Foundations and Combinatorics, — Academic Press, New York A, On chromatic roots of large subdivisions of graphs, Discrete Math.
Hedetniemi and P. Thesis, Uni- versity Putra Malaysia, Beraha, J. Kahane, and N. Joshi Department of Mathematics D. Introduction Prime graph of a ring first introduced by Satyanarayana et al. This graph is denoted by P G R. The concept of energy and Wiener index of zero divisor graph was introduced by Mohammad Reza and Reza Jahani in . Motivated from the article in  in Section 2 of this paper we discuss energy of prime graph of a ring and give general MATLAB code for our calculation.
Here, we also discuss complement of line graph of prime graph of a ring over a ring Zn , denote it by L P G Zn c. For more preliminary definitions and Notations the reader is referred to -. Energy of Prime Graph of a Ring In this section we give some examples and calculate the Energy of prime graph of a ring.
INTERNATIONAL JOURNAL OF MATHEMATICAL COMBINATORICS, vol. 1 / by Florentin Smarandache - Issuu
Example 2. Joshi and Kishor F. From the above Discussion we conclude the following theorem. Line Graph of Prime Graph of a Ring In this section we define line graph of prime graph of a ring, presented some examples and give some results. Definition 4. Consider Zn , the ring of integers modulo n.
Example 4. L P G Z4 is a complete graph k3. L P G Z5 is a complete graph k4. L P G Z6 contains a complete subgraph k5. L P G Z7 is a complete graph k6. Observations 4. Therefore, centre is L P G Zn. So, there is a common vertex which is adjacent to all other vertices and that vertex is called center of the graph.
Then a1 appears in every vertex of the line graph. In other words, we can say that single vertex cover all other vertices of line graph of P G Zn. Thus, the point cover is one and from that vertex an independence number is also one. Bhavanari, S. Kuncham, Nagaraju Dasari, Prime graph of a ring, J. Ltd, Dummit, Richard M. The set W is called Steiner dominating set if W is both a Steiner set and a dominating set. We investigate Steiner domination number of some splitting and degree splitting graphs. Key Words: Steiner distance, Steiner set, Steiner number, domination number, Steiner domination number.
AMS : 05C69, 05C Introduction We consider simple, finite, connected and undirected graph G with vertex set V and edge set E. For the standard graph theoretic terminology and notation we follow Chatrand and Lesniak  while the terms related to the theory of domination are used in the sense of Haynes et al. Definition 1. If H is a subgraph of minimum size that contains a set W , then H is necessarily a tree, called a Steiner tree for W or a Steiner W -tree. Vaidya and Sejal H. Karkar Chartrand et al. The sharp upper and lower bounds for the Steiner k-diameter of G and G are given by Mao  while the same author have identified some graph classes attaining these bounds.
A Steiner set of minimum cardinality is a minimum Steiner set and this cardinality is the Steiner number s G. The concept of Steiner number was introduced by Chartrand and Zhang . In the same paper authors have proved many results on this newly defined concept. This concept was further studied by Santhakumaran and John . Figure 1 The graph G and its Steiner trees Definition 1. A set of vertices W in G is called a Steiner dominating set if W is both a Steiner set and a dominating set.
The concept of Steiner domination number was introduced by John et al. It is very in- teresting to investigate Steiner domination number of graph or graph families as it is known only for handful number of graphs. Main Results Observation 2. Therefore, they must be in Steiner dominating set W.
Karkar corresponding vertices which are added in order to obtain DS Bm,n. Proof From the Theorem 2. Therefore, these two vertices must be in Steiner dominating set W. Here W dominates all the vertices of the graph. Therefore, it is also a dominating set. Thus, W is a Steiner dominating set.
We claim that W is a Steiner dominating set with minimum cardinality. Therefore, U is not Steiner set. Thus, U is not a Steiner set. In order to construct DS Km,n we add w1 and w2. Hence by Proposition 2. Proof Let v0 , v1 , v2 ,.
Edited By Linfan MAO
Therefore, we must include some more vertices to obtain a Steiner dominating set. Concluding Remarks The Steiner domination in graphs is one of the interesting domination models. It is always challenging to investigate Steiner domination number of a graph. We have obtained Steiner domination number of larger graphs which are obtained by means of various graph operations. Acknowledgment The authors are highly thankful to the anonymous referees for their critical comments and constructive suggestions for the improvement in the first draft of this paper. References  P. Ali, P.
Dankelmann and S. Mukwembi, Upper bounds on the Steiner diameter of a graph, Discrete Appl. Chartrand and L. Chartrand, O. Oellermann, S. Tian and H. Chartrand and P. Zhang, The Steiner number of a graph, Discrete Mathematics, , Gross and J. Haynes, S. John, G. Edwin and P. Santhakumaran and J. Mao, The Steiner diameter of a graph, arXiv : CO], Vaidya and S. Karkar, Steiner domination number of some graphs, International Journal of Mathematics and Scientific Computing, 5 , Vaidya and R. Mehta, Steiner domination number of some wheel related graphs, International Journal of Mathematics and Soft Computing, 5 , Sudev, K.
In this paper, we extend the concepts of mean and variance, two important statistical measures, to the theory of graph coloring and determine the values of these parameters for a number of standard graphs. AMS : 05C15, 62A Introduction Investigations on graph coloring problems have attracted wide interest among researchers since its introduction in the second half of the nineteenth century. The vertex coloring or simply a coloring of a graph is an assignment of colors or labels to the vertices of a graph subject to certain conditions.
In a proper coloring of a graph, its vertices are colored in such a way that no two adjacent vertices in that graph have the same color. Different types of graph colorings have been introduced during several subsequent studies. Many practical and real life situations paved paths to different graph coloring problems. Several researchers have also introduced various parameters related to different types of graph coloring and studied their properties extensively.
The first and the most important parameter in the theory of graph coloring is the chromatic number of graphs which is defined as the minimum number of colors required in a proper coloring of the given graph. The concept of chromatic number has been extended to almost all types of graph colorings. The notion of chromatic sums of graphs related to various graph colorings have been 1 Received February 27, , Accepted August 16, Chithra, S.
Satheesh and Johan Kok introduced and studied extensively. Some of these studies can be found in [9, 10, 11]. For all terms and definitions, not defined specifically in this paper, we refer to [2, 3, 4, 6, 15, 16] and for the terminology of graph coloring, we refer to [5, 7, 8].
For the concepts in Statistics, please see [12, 13]. Unless mentioned otherwise, all graphs considered in this paper are simple, finite, connected and non-trivial. Coloring Mean and Variance of Graphs We can identify the coloring of the vertices of a given graph G with a random experiment. If the context is clear, we can also say that f i is the p. Hence, analogous to the definitions of the mean and variance of random variables, the mean and variance of a graph G, with respect to a general coloring of G can be defined as follows.
Proof Note that all vertices of a complete graph Kn must have different colors as they are all adjacent to each other. Proof Let X be the r. Satheesh and Johan Kok complete graph Kn. Hence, the corresponding p. Proposition 2. Being a bipartite graph, the vertices of Pn can be colored using two colors, say c1 and c2. Then, we have the following cases.
Then, the p. Then, exactly n2 vertices of Cn also have color c1 and c2 each. Satheesh and Johan Kok Proposition 2. Hence the corresponding p. Hence, the p. Hence the p. Invoking the definitions of two types of chromatic means and variances mentioned above, we can infer the following. Satheesh and Johan Kok Remark 2. Proof As in Proposition 2. Then the p. Then, we have to consider the following cases. Therefore, the corresponding p. By Theorem 2. Hence, we have Theorem 2. An n-partite graph is a graph whose set of vertices can be partitioned in to n subsets such that no two vertices in the same partitions are adjacent.
Then, we have the following result. Then, any minimal proper coloring of G follows uniform distribution in each partition. Let G be an r-regular k-partite graph. Proof The proof follows immediately from the fact that the minimal proper coloring of a k-partite graph follows uniform distribution. Scope for Further Studies In this paper, we have extended the notions of mean and variance to the theory of graph coloring and determined their values for certain graphs and graph classes. More problems in this area are still open.
Determining the sum, mean and variance corresponding to the coloring of certain generalized graphs like generalized Petersen graphs, fullerence graphs etc. Studies on the sum, mean and variance corresponding to different types of edge colorings, map colorings, total colorings etc. We can associate many other parameters to graph coloring and other notions like covering, matching etc. All these facts highlight a wide scope for future studies in this area. Acknowledgement The first author of this article dedicates this paper to the memory Prof.
Batsyn and V. Kalyagin, An analytical expression for the distribution of the sum of random variables with a mixed uniform density and mass function, In Models, Algorithms, and Technologies for Network Analysis Editors: B. Goldengorin, P. Prdalos and V. Kalyagin , , Springer, Bondy and U. Le and J. Harary, Graph theory, Addison-Wesley Pub. Jensen and B. Kok, N. Sudev and K. Chithra, General coloring sums of graphs, Cogent Math. Kubicka and A. Schwenk, An introduction to chromatic sums, Proc. Kubicka, The chromatic sum of a graph: History and recent developments, Int.
Rohatgi, A. Chithra and J. Kok, Certain chromatic sums of some cycle related graph classes, Discrete Math. Algorithms Appl. Here we construct new graphs of fixed diameter and compute the status indices as well as harmonic status indices of those graphs. Key Words: Status of vertex, first status connectivity index, second status connectivity index, harmonic status index.
Introduction There are several molecular structural graph descriptors such as Weiner Index, Zagreb Index, Hosoya Index etc which strongly correlate studies in graph theory with chemistry. Most of these indices are based on the distance between vertices in a graph. Motivated by harmonic mean we have harmonic index of a graph defined by Fajtlowicz . For more work one can refer . Further motivated by the same, Ramane and Yalnaik introduced the harmonic status index of graphs . Jog and Shrinath L. Status Connectivity Indices and Coindices of First Level Thorn Graphs Now we discuss the harmonic status index and coindex of first level thorn graphs.
Proof The proof follows by direct counting. Patil Theorem 3. Conclusion We considered general l level thorn graphs and obtained in particular, status connectivity indices and coindices as well as Harmonic status indices and coindices of 0 level and first level thorn graphs for some class of graphs. References  Harary F. Ramane and A.
Yalnaik, Status connectivity indices of graphs and its applications to the boiling point of benzenoid hydrocarbons, Journal of Applied Mathematics and Com- puting, Ramane, B. Basavangoud and A. Yalnaik, Harmonic status index of graphs, Bulletin of Mathematical Sciences and applications, 17 , Number, 60 , Liu, On the harmonic Index of triangle free graphs, Appl.
Sampath Kumar. In this paper we study the set S being dominating set and corresponding domination energy of some class of graphs. Key Words: Adjacency matrix, Smarandachely k-dominating set, eigenvalues, energy of graph, distance energy, Laplacian energy. The molecular graph is a representation of the molecular structure of a hydrocarbon whose vertices are the position of carbon atoms and two vertices are adjacent if there is a bond connecting them. Eigen values and eigenvectors provide insight into the geometry of the associated linear transformation.
The energy of a graph is the sum of the absolute values of the Eigen values of its adjacency matrix. The importance of Eigen values is not only used in theoretical chemistry but also in ana- lyzing structures. Car designers analyze Eigen values in order to damp out the noise to reduce 1 Received February 18, , Accepted August 19, Various Domination Energies in Graphs the vibration of the car due to music.
Eigen values can be used to test for cracks or deformities in a solid. Oil companies frequently use Eigen value analysis to explore land for oil. Eigen values are also used to discover new and better designs for the future. Definitions and Notations Representation of a subset of vertices of a graph by means of a matrix was first introduced by E. Sampath Kumar . The matrix thus obtained from the adjacency matrix can be taken as the matrix of the set S denoted by AS G.
Recall that in the last few years, the graph energy E G and domination energy [9,10] or covering energy  has been extensively studied in the mathematics [6,7] and mathematic-chemical literature [8,12]. Kamal Kumar nation energy and Laplacian distance domination energy can also be defined as follows. The matrix thus obtained from the distance matrix can be considered as the distance matrix of the set S denoted by DS G. Various Domination Energies Definition 3. Some book graphs are shown in Figure 1.
This completes the proof. The edges of a wheel which include the hub are called spokes. Some wheel graphs are shown in Figure 3. On the calculation of the energy in unsaturated hydrocarbon molecules. Cambridge Phil. The energy of a graph. Forschungszenturm Graz, 1— Gutman and O. Graphs and Matrices. The Minimum covering energy of a graph. Kragujevac J. The energy of a graph: Bounds, Graph theory Lecture notes. Ramane, D. Acharya and H. Estimating the distance energy of graphs. Kamal Kumar, Domination energy of some well-known graphs, International Journal of Applied Mathematics, 3 1 — Kamal Kumar, Characteristic polynomial and domination energy of some special class of graphs, International Journal of Mathematical Combinatorics, Vol.
The energy of graphs and matrices. Graphs and matrices with maximal energy. A graph that admits a C-geometric mean labeling is called a C-geometric mean graph. In this paper, we have discussed the C-geometric meanness of some ladder graphs. Introduction Throughout this paper, by a graph we mean a finite, undirected and simple graph. Let G V, E be a graph with p vertices and q edges.
For notations and terminology, we follow . For a detailed survey on graph labeling we refer to . Path on n vertices is denoted by Pn. Let G1 and G2 be any two graphs with p1 and p2 vertices respectively. The ladder graph Ln is a graph obtained from the cartesian product of P2 and Pn. The graph thus obtained is called a one sided step graph and it is denoted by STn. Durai Baskar and S. The graph thus obtained is called a double sided step graph and it is denoted by 2ST2n. The study of graceful graphs and graceful labeling methods was first introduced by Rosa .
The concept of mean labeling was first introduced by S. Somasundaram and R. Ponraj  and it was developed in  and . In , R. Vasuki et al. In [1, 3], some graph labelings of step graphs were analyzed. In a study of traffic, the labeling problems in graph theory can be used by considering the crowd at every junctions as the weights of a vertex and expected average traffic in each street as the weight of the corresponding edge. If we assume the expected traffic at each street as the arithmetic mean of the weight of the end vertices, that eases mean labeling of the graph.
When we consider a geometric mean instead of arithmetic mean in a large population of a city, the rate of growth of traffic in each street will be more accurated. Motivated by this, we establish the geometric mean labeling on graphs. Motivated by the works of so many authors in the area of graph labeling, we introduced a new type of labeling called C-geometric mean labeling.
In , S. Somasundaram et al. In the above definition, the readers will get some confusion in finding the edge labels which edge is assigned by flooring function and which edge is assigned by ceiling function. Clearly, a Smarandache 2-mean graph is nothing else but a geometric mean labeling graph.
MATHEMATICAL COMBINATORICS (INTERNATIONAL BOOK SERIES), Vol. 3 / 2018
To avoid the confusion lp of assigning m the edge labels in their definition, we just consider the ceiling function f u f v for our discussion. Main Results Theorem 2. Hence f is a C-geometric mean labeling of T Ln. Hence f is a C-geometric mean labeling of SLn. In ui,j , i denotes the row counted from bottom to top and j denotes the column counted from left to right in which the vertex occurs. Hence, f is a C-geometric mean labeling of STn. Arockiaraj In ui,j , i denotes the row counted from bottom to top and j denotes the column counted from left to right in which the vertex occurs.
Hence, f is a C-geometric mean labeling of 2ST2n. Thesis, Madurai Kamaraj University, Madurai, Arockiaraj, P. Mahalakshmi and P. Namasivayam, Odd sum labeling of some subdivision graphs, Kragujevac Journal of Mathematics, volume 38 1 , Durai Baskar, S. Arockiaraj and B. Rajendran, Geometric meanness of graphs obtained from paths, Util.
- Related titles.
- Bring Me One of Everything!
- Related titles.
- MATHEMATICAL COMBINATORICS (INTERNATIONAL BOOK SERIES), Volume 3 / 2008.
- Edited By Linfan MAO?
Ponraj and S. Somasundaram, Further results on mean graphs, Proceedings of Sacoef- erence, , Somasundaram, P. Vidhyarani and S. Vasuki and A. Nagarajan, Further results on mean graphs, Scientia Magna, 6 3 , In this paper, we determine the edge hubtic number of some standard graphs. Beijing NO. China 2. Email: caijunliang bnu. The least such integers k is called the Smarandache exponent or exponent of A and denoted by S A and A , respectively. The symmetric primitive matrices with exponent n 2 has been described in articles -. In this paper the complete characterization of symmetric primitive matrices with exponent n 3 is obtained.
Key words: Smarandachely primitive matrix, Primitive matrix, Smarandache exponent, exponent, primitive graph. AMS : 05C The least such integer k is called the Smarandache exponent or exponent of A and denoted by S A and A , respectively. The least such k is called the exponent of G, denoted by G. Clearly,a symmetric matrix A is primitive if and only if its associated graph G A is primitive. By this reason as above, we shall employ graph theory as a major tool and consider G A to prove our results.
Let SEn be the exponent set of n n symmetric primitive matrices. In ,Wang gave the characterization of the matrix with exponent 2n 4. In , Li obtained the characterization with exponent 1 Supported 2 Received. July 16, Accepted September 6, In , Cai and Zhang derived the complete characterization of symmetric primitive matrices with exponent 2n 2r n. In , Cai and Wang got the characterization with exponent n 1. In ,Cai characterized the matrix with exponent n 2.
The purpose of this paper is to go further into the problem and give the complete characterization of symmetric primitive matrices with exponent n 3. Some lemmas on G For convenience, We will narrate the lemmas with graph theory below. Lemma 2. The local exponent from vertex u to v, denoted by u, v , is the least integer k such that there exists a walk of length l from u to v for all l k. We denote u, u by u for short. We denote by P u, v the shortest walk from u to v in G.
The length of P u, v is called the distance between u and v, denoted by dG u, v.
Let G1 and G2 be two subgraphs of G. P G1 , G2 denotes the shortest walk between G1 and G2. Let u, v V G ,we name the walk from u to v with different parity length to dG u, v a dissimilar walk, denoted by W u, v. The shortest u, v -dissimilar walk is called the primitive walk between u and v, denoted by Wr u, v , its length is denoted by b u, v .
Apparently, any u, v -dissimilar walk is inevitably correlative with some odd cycle. And for any odd cycle C, there is a u, v -dissimilar walk correlative with C, we denote it by W u, v, C. We call C0 a u, v -primitive cycle or the primitive cycle of P u, v. If there exists a u, v -shortest path which intersects with its primitive cycle C0 , then we can choose some u, v -shortest path, denoted by P u, v might as well, such that their intersected vertexes can be arranged on a path.
Constructions of graphs Let G be a primitive graph with order n. Let the set of induced subgraphs with order n of K which contain K d be. We mark the graphs of N d with Nn3 which satisfy the following qualifications: 1 diam N d n 3;. Let ui V P x, Cd Pt i t be the vertex with the smallest subscript. Let Cd0 be the cycle with length d0 which has only one intersected vertex ut0 ,j with P0 , while Cd1 be the cycle with length d1 which has only one intersected vertex ut1 ,i with P1 and doesnt intersect with Cd0.
Therefore, we have. We choose the connected subgraph Tm,t0 of T [V m, t0 ] to 2 form the set of graphs Mn3 ,where Tm,t0 satisfies that: 1 diam Tm,t0 n 3;. We choose the connected subgraph Tm,t0 of T [V m, t0 ] to form the set 3 of graphs Mn3 , where Tm,t0 satisfies that: 1 diam Tm,t0 n 3;. Main results and proofs Theorem 4. Thus we get. Then P x, ui is a shortest path from C to Pt.
Note that x, u0 , C. So the third qualification meets. For the sufficiency, without loss of generality, we let G Nn3 with 1 d n 2 and d 1 mod 2. In what follows, it suffices to prove u, v n 3 for any two distinct vertexes u and v in V G. We then have u0. Therefore P u, C doesnt intersect with Pt. We shall discuss in the two following cases. Then C 3. If P u, C intersects with P v, C , then we have u, v.
Thus we can easily have u, v u, u0 , C 2t G. Otherwise, C doesnt intersect with P u, v. This suggests that d u, C d v, C. Hence we have u, v v, C G. If C 3,then C must intersects with C. Similarly, d u, C d v, C. Therefore, we get u, v u, u0 G. From those as above, we can easily get u, v u, u0 G. Theorem 4. In the following, we shall complete our arguments in four cases. Suppose that the odd cycles C1 and C2 satisfy the following qualifications respectively. It is easy to verify that G meets the first three construct qualifications 1 , 2 and 3 of Td0 ,d1. We shall prove that G meets the other qualifications: Suppose there exists a xa , yb -path with length p which connects P0 C0 to P1 C1 in G E Kd0 ,d1 , where 0 a t0 and 0 b t1.
The qualification 4 thus meets. The fifth qualification 5 meets. Hence, we assume that C1 doesnt intersect with C without loss of generality. This contradicts the choose of C. It is obvious that its order is n 2. It is easy to verify that G meets the first three construct qualifications 1 , 2 and 3 of Tm,t0. We shall prove that G meets the other qualifications: Suppose that there is a xa , yb -path with length p which divides up C0 in G E Km,t0 , where 0 a, b t0.
Clearly,p 3. Note that any odd cycle in G has only one intersected vertex with the u, v -shortest path, and C0 is the smallest odd cycle which has only one intersected vertex with P u, v :. Hence, a b p, and the fourth qualification 4 comes into existence. The fifth qualification 5 comes into existence. Note that n 3 m mod 2. It is obvious that its order is n 1. We shall prove that G meets the other qualifications:.
Suppose that there exists a xa , yb -path with length p which divides up C0 in GE Km,t0 , where 0 a, b t0. Clearly,p 2. Note that any odd cycle has at most two intersected vertexes with any u, v -shortest path in G, and C0 is the smallest odd cycle which has just two intersected vertexes with P u, v. Suppose that there exists a z, xa -path or z, yb -path with length p in G E Km,t0 which divides up C0 , where 0 a, b t0.
Clearly, p 2. Using analogous argument, we can get the corresponding restrained qualifications for b. Hence the fourth construct qualification 4 comes into existence. The fifth qualification 5 thus comes into existence. We shall prove that G meets the other qualifications: Suppose that there exists an edge xa yb in G E Km,t0 which divides C0 , where 0 a, b t0.
We thus get a b 3. Suppose that there exists an edge vk xa in G E Km,t0 which divides up C0 , where 1 a t0. Thus, we have a 2t0 1. Suppose that there is an edge vk yb in G E Km,t0 which divides C0 , where 1 b t0. Hence, the fourth qualification 4 comes into existence. Hence, the fifth qualification 5 comes into existence.
References  J. Bondy and U. Brualdi and H. Wang, The character of symmetric primitive matrices with certain exponents, J. Taiyuan Machinery College. Li, The characterization of symmetric primitive matrices with exponent 2n6, J. Nanjing Univ. Graph Theory , Vol. Cai and K. Zhang, The characterization of symmetric primitive matrices with exponent 2n 2r n , Linear Multilin.
Cai and B. Wang, The characterization of symmetric primitive matrices with exponent n 1, Linear Alg. Liu, B. McKay, N. Wormald and K. Zhang, The exponent set of symmetric primitive 0,1 matrices with zero trace, Linear Alg. China E-mail: wangjing hotmail. Key Words: Graph, Smarandache drawing, crossing number, circulant graph. AMS : 05C, 05C A Smarandache drawing of a graph G is a drawing of G on the plane with minimal intersections for its each component.
Certainly, we only need to consider Smarandache drawing of connected graphs. The crossing number cr G of a graph G is the minimum number of pairwise intersections of edges in a drawing of G in the plane. It is well known that the crossing number of a graph is attained only in good drawings of the graph, which are those drawings where no edge crosses itself, no adjacent edges cross each other, no two edges intersect more than once, and no three edges have a common point.
Let D be a good drawing of the graph G, we denote the number of crossings in D by cr D. Calculating the crossing number of a given graph is NP-complete . Only the crossing number of very few families of graphs are known exactly, some of which are the crossing number of circulant graph.
Yang and Lin, etc. Accepted September 20, In , Ma, et al. Some lemmas and the main result Let A and B be two disjoint subsets of E. By counting the number of crossings in D, we have Lemma 2. In a drawing D, if an edge is not crossed by any other edge, we say that it is clean in D; if it is crossed by at least one edge, we say that it is crossed in D. The following lemma is a trivial observation. Proof We will prove it by induction on k. So, it suffices to verify that 1 is true. Furthermore, there are only two possible drawings of Ei , which are shown in Figure 2.
Suppose that Ei is drawn as in the right hand side of Figure 2. Denote the regions by a, b and c as in Fig. From all the above cases, we have shown that 1 is true. This together with Lemma 2. References  Garey, M. Algebraic Discrete Methods, 4 , Santhakumaran and S. Ullas Chandran Department of Mathematics of St. E-mail: apskumar yahoo. A u v path of length d u, v is called a u v geodesic. For an integer k 1, a geodesic of length k in G is called a k-geodesic. The minimum cardinality of a k-edge geodetic set of G is the k-edge geodetic number egk G and the minimum cardinality of an edge geodetic set is the edge geodetic number eg G.
In this paper we investigate how the edge geodetic number and the k-edge geodetic number of a graph G are affected by adding a pendant edge to G. Key Words: Smarandache edge-geodetic set, geodetic number, edge geodetic number, k-geodetic number, k-edge geodetic number, k-extreme edge. The order and size of G are denoted by n and m respectively. For basic graph theoretic terminology, we refer to Harary .
For vertices u and v in a connected graph G, the distance d u, v is the length of a shortest u-v path in G. It is known that the distance is a metric on the vertex set of G. A u-v path of length d u, v is called a u-v geodesic. A vertex x is said to lie on a u-v geodesic P if x is a vertex of P including the vertices u and v.
For any path P in a graph and two vertices x, y on P, we use P [x, y] to denote the portion of P between x and y, inclusive of x and y. The neighborhood of a vertex v is the set N v consisting of all vertices u which are adjacent with v. A vertex v is an extreme vertex of G if the subgraph induced by its neighbors is complete. The closed interval I[u, v] consists of all vertices lying on 1 Supported 2 Received. A geodetic set of cardinality g G is called a g-set of G. The geodetic number of a graph was introduced in ,  and further studied in , .
It was shown in  that determining the geodetic number of a graph is an NP-hard problem. A set S of vertices is an edge geodetic set of a graph G if each edge of G lies on a geodesic of vertices in S, and Smarandache edge-geodetic set of G if each edge of G lies on at least two geodesics of S. The minimum cardinality of an edge geodetic set is the edge geodetic number eg G. An edge geodetic set of cardinality eg G is called eg-set of G.
Edge geodetic sets and the edge geodetic number of a graph with several interesting applications are investigated in . For an integer k 1, a geodesic in G of length k is called k-geodesic. A vertex v is called kextreme vertex if v is not the internal vertex of a k-geodesic joining any pair of distinct vertices of G.
Obviously, each extreme vertex of a connected graph G is k-extreme vertex of G. In particular, each end vertex of G is a k-extreme vertex of G. The minimum cardinality of a k-geodetic set of G is its k-geodetic number gk G. A k-geodetic set of cardinality gk G is called gk -set. The k-geodetic number of a graph was refereed to as k-geodeomination number and studied in . The minimum cardinality of a k-edge geodetic set of G is its k-edge geodetic number egk G.
A k-edge geodetic set of cardinality egk G is called egk -set of G. For k 2, an edge of G is called k-extreme edge if it does not lie on any k-geodesic of vertices of G. For the graph G given in Fig. Since the edge v3 v4 does not lie on any 2-geodesic of vertices of S, S is not a 2-edge geodetic set of G. The k-edge geodetic number of a graph was introduced and studied in . It is proved in  that each triple a, b, k of integers with 2 a b and k 2 is realizable as the kgeodetic number and k-edge geodetic number of a graph respectively. Also it is shown in  that for given integers a, b, c and k 2 with 3 a b c, there is a connected graph G with.
These concepts have many applications in location theory and convexity theory. There are interesting applications of these concepts to the problem of designing the route for a shuttle and communication network design. A fundamental question in graph theory concerns how the value of a parameter is affected by making a small change in the graph.
The geodetic number and the k-geodetic number, affected by adding a pendant edge, was discussed in  and  respectively. In this paper we study how the edge geodetic number and the k-edge geodetic number of a graph are affected by adding a pendant edge to the graph. Throughout the following G denotes a connected graph with at least two vertices. The following theorems will be used in the sequel.
In particular, if the set of all extreme vertices W is an edge geodetic set of G, then W is the unique eg-set of G. How the edge geodetic number of a connected graph is affected by adding a pendant edge In this section we discuss how the edge geodetic number of a connected graph G is affected by adding a pendant edge to G. Let G be a graph obtained from a connected graph G by adding a pendant edge uv, where u is not vertex of G and v is a vertex of G. We claim that S is an edge geodetic set of G.
Let e be an edge of G. If e E G , then e lies on a geodesic of vertices in S. Then, it is clear that the portion P [x, v] of the x v path on P together with the edge uv is a x u geodesic of G , which contains the edge e with. Let S be an eg-set of G. By Theorems 1. Hence the result. If the graph G is the path Pn n 3 on n vertices, then, by Theorem 1. Let G be the path obtained from Pn by adding a pendant edge at one of its end vertices.
Then, by Theorem 1. If G is the tree obtained from Pn by adding a pendant edge at a cut vertex of Pn , then by Theorem 1. Proof First, assume that there is an eg-set S of G such that v S. We show that S is an eg-set of G. Let e be any edge of G. Since S is an eg-set of G, e lies on a x y geodesic in G with x, y S. Now, the result follows from Theorem 2. Suppose that v does not belong to any eg-set of G.
Since u is an end vertex of G and v is a cut vertex of G , by Theorems 1. Then S V G and. Then e is also an edge of G and so e lies on a geodesic P in G joining a pair of vertices x, y S. Then it follows that e lies on a geodesic in G joining x and v in S. Since v S, this is contradiction to our assumption. This completes the proof. For example, for the complete bipartite graph Km,n we have, by Theorem 1.
Hence a new vertex may be added to a graph along with a large number of edges such that it does not affect the edge geodetic number. Now, it follows from Theorem 1. If we add a vertex v and join it to all the end vertices of K1,n then we obtain the graph K2,n. By Theorem 1.
How the k-edge geodetic number of a connected graph is affected by adding a pendant edge We now consider how the k-edge geodetic number of a connected graph G is affected by the addition of a pendant edge. Proposition 3. Proof Let S be an egk -set of G. Let G be a graph obtained from G by adding a pendant edge uv at a vertex v of G.
Now, by Theorem 1. Hence the result follows. Proof Let G be the graph obtained from G by adding a pendant edge uv at a vertex v of G. Let S be an eg2 -set of G. We claim that S is a 2-edge geodetic set of G. If e E G , then e lies on a 2-geodesic of vertices in S. Let vw be an edge of G. Then, by Observation 3.
Now, it is clear that the edge uv lies on the 2-geodesic P : w, v, u of G with w, u S. Now, let T be any eg2 -set of G. Then by Theorem 1. Then T T. We show that T is a 2-edge geodetic set of G. By Observation 3. Assume that the geodesic P is P : x, y, z with x, z T. Proof Let T be an eg2 -set of G such that v T. Problem 3.
Books by Linfan Mao
In view of Proposition 3. Proof We prove the theorem by considering five cases. Let G be the graph obtained from the path P : v0 , v1 ,. The graph G is shown in Fig. It is clear that the edges ui v2 1 i b 3 are the only k-extreme edges of G. Since S is a k-edge geodetic set of G, it follows from Theorem 1.
Now, let G be the graph obtained from G by adding a pendant edge vk x. It is clear that G has no k-extreme edges. Since the edges v0 v1 and v1 v2 do not lie on any k-geodesic joining a pair of vertices in S , we have S is not a k-edge geodetic set of G. Then S is the set of all k-extreme vertices of G. It is clear that G has no k-extreme edges and S is a k-edge geodetic set of G and so by Theorem 1. Now, let G be the graph obtained from G by adding a new vertex x and joining it to v1. Let G be the graph constructed in Case 2. Now, let G be the graph obtained from G by adding a new vertex x and joining it to v2.
Then the edge xv2 is the only k-extreme edge in G. Let G1 be the graph obtained from the path P : v0 , v1 ,. Let G2 be the graph obtained from G1 and Q by identifying the vertices v2 and x0. Let G be the graph obtained from G2 by adding b 5 new vertices z1 , z2 ,. The graph is G shown in Fig. It is clear that the edge v2 w is the only k-extreme edge of G. Let G2 be the graph obtained from G1 by adding b a 1 new vertices u1 , u2 ,. Let G3 be the graph obtained from G2 by adding a 4 new vertices z1 , z2 ,. Let G be the graph obtained from G3 and Q by identifying the vertices v3 and x0.
It is clear that the edges ui v3 and ui w 1 i b a 1 are the only k-extreme edges of G and so by Theorem 1. Then S is the set of all k-extreme vertices and the ends of all k-extreme edges of G. Now, let G be the graph obtained from G by adding a new vertex x and joining it to w. Then the graph G has no k-extreme edges. Next, suppose that k 5. Then T is the set of all k-extreme vertices and the ends of all k-extreme edges of G. It is clear that T is a k-edge geodetic set of G and so by Theorem 1. Let G be the graph obtained from G by adding a new vertex x and joining it to w.
Since T is a k-edge geodetic set of G , it follows from Theorem 1. Thus the proof is complete. Buckley and F. Chartrand, F. Harary and P. Harary, Graph Theory, Addison-Wesley, Harary, E. Loukakis, C. Souros, The geodetic number of a graph, Mathl. Modeling,17 11 , Muntean, P. Zhang, On Geodomination in Graphs, Congr. Santhakumaran and J.
Ullas Chandran, The k-edge geodetic number of a graph, communicated. Simple Path Covers in Graphs S. Arumugam and I. E-mail: s arumugam akce yahoo. Abstract: A simple path cover of a graph G is a collection of paths in G such that every edge of G is in exactly one path in and any two paths in have at most one vertex in common. More generally, for any integer k 1, a Smarandache path k-cover of a graph G is a collection of paths in G such that each edge of G is in at least one path of and two paths of have at most k vertices in common.
The minimum cardinality of a simple path cover of G is called the simple path covering number of G and is denoted by s G. In this paper we initiate a study of this parameter. Key Words: Smarandache path k-cover, simple path cover, simple path covering number. AMS : 05C35, 05C The order and size of G are denoted by p and q respectively. For graph theoretic terminology we refer to Harary . All graphs in this paper are assumed to be connected and non-trivial. Let Ti , 1 i k 2, be the maximal subtree of G such that Ti contains the edge ei and w is a pendant vertex of Ti.
Then T1 , T2 ,. The concept of path cover and path covering number of a graph was introduced by Harary . Preliminary results on this parameter were obtained by Harary and Schwenk , Peroche  and Stanton et al. May 16, Accepted September 16, The minimum cardinality of a path cover of G is called the path covering number of G and is denoted by G or simply.
Let m denote the number of vertices of degree greater than 2 on C. Let k denote the number of vertices of odd degree. The concepts of graphoidal cover and acyclic graphoidal cover were introduced by Acharya et al. If further no member of is a cycle in G, then is called an acyclic graphoidal cover of G. The minimum cardinality of a graphoidal cover of G is called the graphoidal covering number of G and is denoted by G. Similarly we define the acyclic graphoidal covering number a G. An elaborate review of results in graphoidal covers with several interesting applications and a large collection of unsolved problems is given in Arumugam et al.
Motivated by this observation we introduced the concept of simple acyclic graphoidal covers in graphs . The minimum cardinality of a simple acyclic graphoidal cover of G is called the simple acyclic graphoidal covering number of G and is denoted by as G or simply as. A vertex of G is said to be an interior vertex of if it is an internal vertex of some path in , otherwise it is said to.
Let C be the unique cycle in G and let m denote the number of vertices of degree greater than 2 on C. In this paper we introduce the concept of simple path cover and simple path covering number s of a graph G and initiate a study of this parameter. We observe that the concept of simple path cover is a special case of Smarandache path k-cover .
- The Army of Many Tribes.
- International Mathematical Olympiad.
- MATHEMATICAL COMBINATORICS (INTERNATIONAL BOOK SERIES), vol. 4, by Ioan Degău - Issuu;
- The Art of Rama!
- MATHEMATICAL COMBINATORICS (INTERNATIONAL BOOK SERIES), Volume 3 / 2008.
For any integer k 1, a Smarandache path k-cover of a graph G is a collection of paths in G such that each edge of G is in at least one path of and two paths of have at most k vertices in common. Main results Definition 2. Example 2. Remark 2. Proof Let be any simple path cover of G. Corollary 2. Further, equality holds if and only if G is complete. Hence it follows from Theorem 1.
We now proceed to determine the value of s for unicyclic graphs and wheels. Let k be the number of vertices of odd degree. Let v1 be the unique vertex of degree greater than 2 on C. Let G1 be the tree rooted at v1. Let 1 be a minimum simple path cover of G1. If deg v1 is odd, then degG1 v1 is odd. Let P be the path in 1 having v1 as a terminal vertex. If deg v1 is even, then degG1 v1 is even. Further, for any simple path cover of G, all the k vertices of odd degree and at least two vertices on C are terminal vertices of paths in.
Let v1 and vi , where 2 i r, be the vertices of degree greater than 2 on C. Let P and Q denote respectively the v1 , vi -section and vi , v1 -section of C. Let vj be an internal vertex of P say. Let R1 and R2 be the v1 , vj -section of P and vj , vi -section P respectively.
Let G1 be the graph obtained by deleting all the internal vertices of P. Subcase 3. Then both degG1 v1 and degG1 vi are even. Then degG1 v1 and degG1 vi are odd. Suppose v1 and vi are terminal vertices of two different paths in 1 , say P1 and P2 respectively. Suppose there exists a path P1 in 1 having both v1 and vi as its end vertices. Let P2 be an u1 -w1 path in 1 having v1 as an internal vertex and P3 be an u2 -w2 path in 1 having vi as an internal vertex.
Let S1 and S2 be the u1 , v1 -section of P2 and w1 , v1 section of P2 respectively. Let S3 and S4 be the u2 , vi -section of P3 and w2 , vi -section of P3 respectively. Then degG1 v1 is even and degG1 vi is odd. Let P1 be the path in 1 having vi as a terminal vertex. Since degG1 vi 3, there exists an u1 -w1 path in 1 , say P2 , having vi as an internal vertex. Let S1 and S2 be the w1 , vi -section of P2 and u1 , vi -section of P2 respectively. Also, for any simple path cover of G all the k vertices of odd degree and at least one vertex on C are terminal vertices of paths in.
Let vi1 , vi2 ,. Let ij , 1 j s, be a minimum simple path cover of the tree rooted at vij. Consider the vertices vi1 , vi2 and vi3. For each j, where 1 j 3, let Pj be the path in ij in which vij is a terminal vertex if deg vij is odd, otherwise let Pj be an uj -wj path in ij in which vij is an internal vertex and Rj and Sj be the uj , vij and wj , vij sections of Pj respectively.
Proof The proof follows from Theorem 2. Problem 2. These parameters may be either equal or all distinct as shown below. We now proceed to obtain some bounds for s. Further, the following are equivalent. Proof Since s , the inequality follows from Theorem 1. Then v lies on each Pi and v is an internal vertex of all the paths in except possibly for at most one path.
Thus i and iii are equivalent. Similarly the equivalence of ii and iii can be proved. Since any path in covers at most one edge of H, it follows that s G 2. Then it follows from Corollary 2. However, the converse is not true. We now prove that the converse is true for trees and unicyclic graphs. Suppose 4. Let v be a vertex of G with deg v 4. Let be a minimum simple acyclic graphoidal cover of G. Let P1 and P2 be two paths in having v as a terminal vertex.
Hence 3. Let k denote the number of vertices of odd degree and n be the number of pendant vertices of G. It follows from Theorem 1. The above results lead to the following problem. In the following theorem we establish a relation connecting the parameters as and s. Proof Let be a minimum simple path cover of G. Let i v denote the number of paths in having v V as an internal vertex. If i v 2, let Pi , where 1 i i v , be the ui -wi path in having v as an internal vertex and let Qi and Ri , where 2 i i v , respectively denote the v, wi -section and v, ui -section of Pi.
Let 1 be the collection of paths obtained from by replacing P2 , P3 ,. Hence it follows from Corollary 2. By Theorem 2. Acharya and E. Sampathkumar, Graphoidal covers and graphoidal covering number of a graph, Indian J. Arumugam, B. Sampathkumar, Tata McGraw Hill, , 1 - Arumugam and J. Suresh Suseela, Acyclic graphoidal covers and path partitions in a graph, Discrete Math. Harary, Covering and packing in graphs I, Ann. Harary and A. Road, Academic Press, New York, , 39 - Peroche, The path number of some multipartite graphs, Annals of Discrete Math. Stanton, D. Cowan and L. James, Some results on path numbers, Proc.
Louisiana Conf. Read, Academic Press, New York, , - China 3. China E-mail: zhang zhong fu yahoo. AMS : 05C15, 94C Introduction Graph coloring is a very important part of graph theory. Recently, the central part is to get the chromatic number of the relate coloring. While it is a NP-problem to get the relate chromatic number for most graphs.
Now these vertex distinguishing edge coloring, adjacent-strongly edge coloring, D -vertex distinguishing edge coloring, adjacent-vertex-distinguishing total coloring, D -vertex distinguishing total coloring, vertex-distinguishing total coloring, adjacent-vertex-strongly-distinguishing total coloring, and a Smarandachely total coloring etc. For terminologies and notations not defined here, we refer to the reference .
Main results Lemma 2. We can find classes C by the construction f following. References  Bondy J. Marty U. R, Graph Theory with applications, Springer Verlag, Graph Theory 20 2 , China, Ser. A, 35 3 , A,,51 3 , Abstract: Classifying objects needs permutation groups in mathematics. Similarly, consideration should be also done for actions of multi-groups, i. In this paper, we consider the action of multi-groups on a finite multi-set, its orbits, multitransitive, primitive, etc.
By choosing an element p in or not in a permutation group , define a new operation p enables us to finding permutation multi-groups. Considering such permutation multi-groups, some interesting results in finite permutation groups are generalized to permutation multi-groups. Key Words: Action of multi-group, permutation multi-group, representation, transitive.
Introduction A bijection f : X X is called a permutation of X. For example, let. It is well-known that all permutations form a group X under the composition operation. Then we have Theorem 1. Proof We check these conditions for a group hold in X ; p. By definition, we know that X ; p is a group.
Furthermore, Theorem 1. Similar to the proof of Theorem 1. Multi-permutation Representations The construction for permutation multi-groups shown in Theorems 1. Choose m permutations p1 , p2 , , pm on X. Denoted by s X all such s-vectors p m. Let be an operation on X. Hence, is a 1 1 and onto mapping. As shown in Theorem 1. If we choose all i , 1 i s to be just the composition of permutation, then all bullet operations in s1 is the same, denoted by.
We find an interesting result following which also implies the Cayleys result on groups, i. Therefore, s H ; is a group. Calculation shows that the order of s H is. Whence, we only need to consider the action of permutation multi-groups on multi-sets. Then we know the result following. Then P.
Proof By definition, we know that P. Whence, we get that hgk1 x , namely, h gk x. Therefore, we find that P. This is the assertion i. Applying Theorem 1. Counting these elements in E, we find that X. Now let xi , 1 i Orb X be representations of different orbits in Orb X. Therefore, GX y g GX xi g. This enables us to obtain that X. In this case, we know formulae following by Theorems 3. It is well-known that Sym X is X -transitive on a finite set X. Proof If is k-transitive on X, it is obvious that is k 1 -transitive on X itself. Therefore, g hg We know that is k-transitive on X. This is the assertion of i.
By definition, GXP is k-transitive on X if and only if is k-transitive, i. For a given set X and permutation multi-group GXP , it can be shown easily by definition that. The next result shows the existence of primitive multi-groups. By assumption, GXP is k-transitive on X, k 2. This fact implies that x, z R for z X by definition. Notice that R is an equivalence relation on X. Then R is a GXP -admissible equivalent relation. In fact, it is GXP -admissible, reflexive and symmetric by definition. For its transitiveness, let s, t R, t, u R. Therefore, s, u R. This concludes that R is an equivalent relation.
Combining these discussions, we conclude that GXP is primitive. Corollary 4. We have shown in Theorem 1. Then what can we say if not all p P are in? This multi-group has good behavior like GXP , also a kind way of extending a group to a multi-group. For convenience, a group generated by a set S with the operation in is denoted by hSi.
According to Theorem 1. Applying Theorem 5. Construct a permutation X y1 y2 yk. Therefore, P is X y1 y2 yk. Applying the induction principle, we get the conclusion. Notice that any k-transitive multi-group is primitive if k 2 by Theorem 4. We have a corollary following by Theorem 5. References  N. Biggs and A. Mao, Extending homomorphism theorem to multi-systems, International J. If you would not forgotten as soon as you are dead, either write things worth reading or do things worth write. By Benjamin Franklin, an American Scientist. Author Information Submission: Papers only in electronic form are considered for possible publication.
Papers prepared in formats, viz. An effort is made to publish a paper duly recommended by a referee within a period of 3 months. In case of clear recommendation for publication, the paper is accommodated in an issue to appear next. Each submitted paper is not returned, hence we advise the authors to keep a copy of their submitted papers for further processing.
Abstract: Authors are requested to provide an abstract of not more than words, latest Mathematics Subject Classification of the American Mathematical Society, Keywords and phrases. Statements of Lemmas, Propositions and Theorems should be set in italics and references should be arranged in alphabetical order by the surname of the first author in the following style: Books K.
Research papers K. Azad and Gunjan Agrawal, On the projective cover of an orbit space, J. In addition, all figures and tables should be numbered and the appropriate space reserved in the text, with the insertion point clearly indicated. Copyright: It is assumed that the submitted manuscript has not been published and will not be simultaneously submitted or published elsewhere. By submitting a manuscript, the authors agree that the copyright for their articles is transferred to the publisher, if and when, the paper is accepted for publication.
The publisher cannot take the responsibility of any loss of manuscript. Therefore, authors are requested to maintain a copy at their end. Proofs: One set of galley proofs of a paper will be sent to the author submitting the paper, unless requested otherwise, without the original manuscript, for corrections after the paper is accepted for publication on the basis of the recommendation of referees.