It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out...It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out that it would be interesting to compute the competition numbers of some triangulations of a sphere as he got the exact value of the competition numbers of regular polyhedra. In this paper, we study the competition numbers of several kinds of triangulations of a sphere, and get the exact values of the competition numbers of a 24-hedron obtained from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face, a class of dodecahedra constructed from a hexahedron by adding a diagonal in each face of the hexahedron, and a triangulation of a sphere with 3n (n≥2) vertices.展开更多
For any graph?G,?G?together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number?k(G)?of a graph?G?is defined to be the smallest number of such isolated ver...For any graph?G,?G?together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number?k(G)?of a graph?G?is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number?k(G)?for a graph?G?and chara-cterizing a graph by its competition number has been one of important research problems in the study of competition graphs. A 2-connected planar graph?G?with minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single face?f0?yields a tree. It is a Halin graph if the vertices of?f0?all have degree 3 in?G. In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.展开更多
文摘It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out that it would be interesting to compute the competition numbers of some triangulations of a sphere as he got the exact value of the competition numbers of regular polyhedra. In this paper, we study the competition numbers of several kinds of triangulations of a sphere, and get the exact values of the competition numbers of a 24-hedron obtained from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face, a class of dodecahedra constructed from a hexahedron by adding a diagonal in each face of the hexahedron, and a triangulation of a sphere with 3n (n≥2) vertices.
文摘For any graph?G,?G?together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number?k(G)?of a graph?G?is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number?k(G)?for a graph?G?and chara-cterizing a graph by its competition number has been one of important research problems in the study of competition graphs. A 2-connected planar graph?G?with minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single face?f0?yields a tree. It is a Halin graph if the vertices of?f0?all have degree 3 in?G. In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.
