由轮图导出的某些平面图类的星色数

图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.     

The Star Chromatic Numbers of Some Planar Graphs Derived from Wheels

The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper, we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions, their star chromatic numbers being 2+2/(2n + 1), 2+3/(3n + 1), and 2+3(3n−1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n, which is a generalization of one result of Gao et al. Received September 21, 1998, Accepted April 9, 2001.     

Cycle embedding in star graphs with conditional edge faults

Among the various interconnection networks, the star graph has been an attractive one. In this paper, we consider the cycle embedding problem in star graphs with conditional edge faults. We show that there exist cycles of all even lengths from 6 to n! in an n-dimensional star graph with ?2n-7 edge faults in which each vertex is incident with at least two healthy edges for n?4.     

Global defensive alliances in star graphs

A defensive alliance in a graph G=(V,E) is a set of vertices S⊆V satisfying the condition that, for each v∈S, at least one half of its closed neighbors are in S. A defensive alliance S is called a critical defensive alliance if any vertex is removed from S, then the resulting vertex set is not a defensive alliance any more. An alliance S is called global if every vertex in V(G)?S is adjacent to at least one member of the alliance S. In this paper, we shall propose a way for finding a critical global defensive alliance of star graphs. After counting the number of vertices in the critical global defensive alliance, we can derive an upper bound to the size of the minimum global defensive alliances in star graphs.     

Star partitions on graphs

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.     

Classes of graphs without star forests and related graphs

This work provides a structural characterisation of hereditary graph classes that do not contain a star forest, several graphs obtained from star forests by subset complementation, a union of cliques, and the complement of a union of cliques as induced subgraphs. This provides, for instance, structural results for graph classes not containing a matching and several complements of a matching. In terms of the speed of hereditary graph classes, our results imply that all such classes have at most factorial speed of growth.     

Circulant graphs and tessellations on flat tori

Circulant graphs are characterized here as quotient lattices, which are realized as vertices connected by a knot on a k-dimensional flat torus tessellated by hypercubes or hyperparallelotopes. Via this approach we present geometric interpretations for a bound on the diameter of a circulant graph, derive new bounds for the genus of a class of circulant graphs and establish connections with spherical codes and perfect codes in Lee spaces.     

Circulant graphs and tessellations on flat tori

Circulant graphs are characterized here as quotient lattices, which are realized as vertices connected by a knot on a k-dimensional flat torus tessellated by hypercubes or hyperparallelotopes. Via this approach we present geometric interpretations for a bound on the diameter of a circulant graph, derive new bounds for the genus of a class of circulant graphs and establish connections with spherical codes and perfect codes in Lee spaces.     

Strong structural properties of unidirectional star graphs

Day and Tripathi [K. Day, A. Tripathi, Unidirectional star graphs, Inform. Process. Lett. 45 (1993) 123-129] proposed an assignment of directions on the star graphs and derived attractive properties for the resulting directed graphs: an important one is that they are strongly connected. In [E. Cheng, M.J. Lipman, On the Day-Tripathi orientation of the star graphs: Connectivity, Inform. Process. Lett. 73 (2000) 5-10] it is shown that the Day-Tripathi orientations are in fact maximally arc-connected when n is odd; when n is even, they can be augmented to maximally arc-connected digraphs by adding a minimum set of arcs. This gives strong evidence that the Day-Tripathi orientations are good orientations. In [E. Cheng, M.J. Lipman, Connectivity properties of unidirectional star graphs, Congr. Numer. 150 (2001) 33-42] it is shown that vertex-connectivity is maximal, and that if we delete as many vertices as the connectivity, we can create at most two strong connected components, at most one of which is not a singleton. In this paper we prove an asymptotically sharp upper bound for the number of vertices we can delete without creating two nonsingleton strong components, and we also give sharp upper bounds on the number of singletons that we might create.     

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x∈V(G) the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O(mlogn) time whether G is a median graph with geodetic number 2.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.     

Some topological properties of star graphs: The surface area and volume

The star graph, as an interesting network topology, has been extensively studied in the past. In this paper, we address some of the combinatorial properties of the star graph. In particular, we consider the problem of calculating the surface area and volume of the star graph, and thus answering an open problem previously posed in the literature. The surface area of a sphere with radius i in a graph is the number of nodes in the graph whose distance from a given node is exactly i. The volume of a sphere with radius i in a graph is the number of nodes within distance i from the given node. In this paper, we derive explicit expressions to calculate the surface area and volume in the star graph.     

临界图的星色数

1988年,Vince定义了图的色数的一个推广——图的星色数,本文研究了有围长限制或有最大度限制的临界图的星色数,得到了三个新结果。     

Isometric embeddings of subdivided connected graphs into hypercubes

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollack [R.L. Graham, H. Pollack, On the addressing problem for loop switching, Bell System Technol. J. 50 (1971) 2495-2519; and D. Djokovi?, Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263-267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specifically, we deal with the case where this configuration is a connected graph of order 4, a complete graph of order 5 and the case of a k-fan F_k(k≥3).     

Cube intersection concepts in median graphs

In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Q_k(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices H_x and H_y in Q_k(G) are adjacent whenever the intersection H_x∩H_y contains a subgraph isomorphic to Q_k. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations.     

Graph pegging numbers

In graph pegging, we view each vertex of a graph as a hole into which a peg can be placed, with checker-like “pegging moves” allowed. Motivated by well-studied questions in graph pebbling, we introduce two pegging quantities. The pegging number (respectively, the optimal pegging number) of a graph is the minimum number of pegs such that for every (respectively, some) distribution of that many pegs on the graph, any vertex can be reached by a sequence of pegging moves. We prove several basic properties of pegging and analyze the pegging number and optimal pegging number of several classes of graphs, including paths, cycles, products with complete graphs, hypercubes, and graphs of small diameter.     

Distance-preserving subgraphs of hypercubes

We give a characterization of connected subgraphs G of hypercubes H such that the distance in G between any two vertices a, b?G is the same as their distance in H. The hypercubes are graphs which generalize the ordinary cube graph.     

Uniquely pairable graphs

The concept of a k-pairable graph was introduced by Z. Chen [On k-pairable graphs, Discrete Mathematics 287 (2004), 11-15] as an extension of hypercubes and graphs with an antipodal isomorphism. In the present paper we generalize further this concept of a k-pairable graph to the concept of a semi-pairable graph. We prove that a graph is semi-pairable if and only if its prime factor decomposition contains a semi-pairable prime factor or some repeated prime factors. We also introduce a special class of k-pairable graphs which are called uniquely k-pairable graphs. We show that a graph is uniquely pairable if and only if its prime factor decomposition has at least one pairable prime factor, each prime factor is either uniquely pairable or not semi-pairable, and all prime factors which are not semi-pairable are pairwise non-isomorphic. As a corollary we give a characterization of uniquely pairable Cartesian product graphs.     

On the spanning tree packing number of a graph: a survey

The spanning tree packing number or STP number of a graph G is the maximum number of edge-disjoint spanning trees contained in G. We use an observation of Paul Catlin to investigate the STP numbers of several families of graphs including quasi-random graphs, regular graphs, complete bipartite graphs, cartesian products and the hypercubes.     

Mapping Planar Graphs into Projective Cubes

Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well‐known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle‐free graph on 16 vertices, is the smallest triangle‐free graph to which every triangle‐free planar graph admits a homomorphism.