Research On Domination In W_{3, N} And Universality Of Arc In Bipartite Graphs

Graph theory is the theory researching vertex set which is connected by lines. Graph theory is one of the most important branches of combinatorics and is also the most important part of discrete mathematics. With the development of computer science and mathematics, graph theory turns into an important tool to research technology and nature science, even for the social science.Domination in graphs is one of the hottest fields of graph theory. The research on domination in graphs has not only important theoretical, but also varied applications in such fields as optimization, design and analysis of communication networks, social sciences, computational complexity, and algorithm design.The dominating number has many applications in network design. For example, some launchers must be placed in a communication network, requiring each lancher must have a direct communication line with another. How to choose places, making the places with the least lanchers. This problem can be converted to a domination number problem.Calculating the domination of any graph is a NP-complete problem, so there are only a few domination problems of graphs have been solved. This paper researches the domination numberγ(W_3,n) and the Packing numberρ(W_3,n) of Kn(o|¨)del graphs W_3,n and proves thatA.Hubenko[On a cyclic connectivity property of directed graphs. Discrete Math, 2008, 308: 1018-1024] proved that each cycle-connected oriented complete bipartite graph has a universal arc and raised two problems. (1) Assume that G is a cycle-connected oriented complete bipartite graph and C is a maximal cycle of G. Are all arcs of C universal? (2) Assume that D is a cycle-connected simple oriented bipartite graph. Does D have a universal arc? The present paper also shows that: (1) There exists cycle-connected oriented complete bipartite graph such that at least one arc of its maximal cycle is not universal. (2) There exists cycle-connected simple oriented bipartite graph such that all arcs of its maximal cycle are universal. (3) There exists cycle-connected simple oriented bipartite graph such that at least one arc of its maximal cycle is not universal.