Generalized Power Domination: Propagation Radius and Sierpiński Graphs

The recently introduced concept of k-power domination generalizes domination and power domination, the latter concept being used for monitoring an electric power system. The k-power domination problem is to determine a minimum size vertex subset S of a graph G such that after setting X=N[S], and iteratively adding to X vertices x that have a neighbour v in X such that at most k neighbours of v are not yet in X, we get X=V(G). In this paper the k-power domination number of Sierpiński graphs is determined. The propagation radius is introduced as a measure of the efficiency of power dominating sets. The propagation radius of Sierpiński graphs is obtained in most of the cases.     

On the role of hypercubes in the resonance graphs of benzenoid graphs

The resonance graph R(B) of a benzenoid graph B has the perfect matchings of B as vertices, two perfect matchings being adjacent if their symmetric difference forms the edge set of a hexagon of B. A family P of pair-wise disjoint hexagons of a benzenoid graph B is resonant in B if B-P contains at least one perfect matching, or if B-P is empty. It is proven that there exists a surjective map f from the set of hypercubes of R(B) onto the resonant sets of B such that a k-dimensional hypercube is mapped into a resonant set of cardinality k.     

Structural characterization of Ga-doped Mg0.1Zn0.9O layers grown on ZnO/α-Al2O3 templates by P-MBE

In this study, structural properties of epitaxial Ga-doped Mg_0.1Zn_0.9O layers grown on ZnO/α-Al₂O₃ templates by plasma-assisted molecular beam epitaxy have been investigated by high-resolution transmission electron microscopy (HRTEM), and high resolution X-ray diffraction (HRXRD). From analysis of the diffraction pattern, the monocrystallinity of the Mg_0.1Zn_0.9O layer with hexagonal structure is confirmed. The orientation relationship between Mg_0.1Zn_0.9O and the template is determined as (0 0 0 1)_Mg0.1Zn0.9O(0 0 0 1)_ZnO(0 0 0 1)_Al2O3 and [ [ ]_ZnO[ . The density of dislocations near the top surface layers measured by plan-view TEM is about 3.610¹⁰ cm⁻², one order of magnitude higher than the value obtained for ZnO layers on α-Al₂O₃ with a MgO buffer. Cross-sectional observation revealed that the majority of threading dislocations are in the [0 0 0 1] line direction, i.e. they lie along the surface normal and consist of edge, screw, and mixed dislocations. Cross- sectional TEM and X-ray rocking curve experiments reveal that most of dislocations are edge dislocations. The interface of Mg_0.1Zn_0.9O and ZnO layers and the effect of excess Ga-doping in these layers have been also studied.     

On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced.     

Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles

Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006