共查询到20条相似文献,搜索用时 31 毫秒
1.
图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论. 相似文献
2.
De Ming Li 《数学学报(英文版)》2002,18(1):173-180
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. 相似文献
3.
Cycle embedding in star graphs with conditional edge faults 总被引:1,自引:0,他引:1
Ming-Chien Yang 《Applied mathematics and computation》2010,215(10):3541-3867
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. 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
《Discrete Mathematics》2022,345(12):113089
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. 相似文献
7.
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. 相似文献
8.
S.I.R. Costa J.E. Strapasson M.M.S. Alves 《Linear algebra and its applications》2011,434(8):1811-1823
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. 相似文献
9.
Eddie Cheng 《Discrete Applied Mathematics》2008,156(15):2939-2949
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. 相似文献
10.
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. 相似文献
11.
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 Sn (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. 相似文献
12.
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. 相似文献
13.
1988年,Vince定义了图的色数的一个推广——图的星色数,本文研究了有围长限制或有最大度限制的临界图的星色数,得到了三个新结果。 相似文献
14.
Méziane Aïder 《Discrete Mathematics》2009,309(22):6402-6407
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 Fk(k≥3). 相似文献
15.
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 Qk(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices Hx and Hy in Qk(G) are adjacent whenever the intersection Hx∩Hy contains a subgraph isomorphic to Qk. 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. 相似文献
16.
Geir Helleloid 《Discrete Mathematics》2009,309(8):1971-1985
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. 相似文献
17.
D.Ž Djoković 《Journal of Combinatorial Theory, Series B》1973,14(3):263-267
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. 相似文献
18.
Zhongyuan Che 《Discrete Mathematics》2008,308(24):6104-6110
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. 相似文献
19.
E. M. Palmer 《Discrete Mathematics》2001,230(1-3):13-21
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. 相似文献
20.
Reza Naserasr 《Journal of Graph Theory》2013,74(3):249-259
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. 相似文献