Currently displaying 1 – 10 of 10

Showing per page

Order by Relevance | Title | Year of publication

The s-packing chromatic number of a graph

Wayne GoddardHonghai Xu — 2012

Discussiones Mathematicae Graph Theory

Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to 1,2,...,k such that vertices with color i have pairwise distance greater than a i , and the S-packing chromatic number χ S ( G ) of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider bounds on...

Orientation distance graphs revisited

Wayne GoddardKiran Kanakadandi — 2007

Discussiones Mathematicae Graph Theory

The orientation distance graph 𝓓ₒ(G) of a graph G is defined as the graph whose vertex set is the pair-wise non-isomorphic orientations of G, and two orientations are adjacent iff the reversal of one edge in one orientation produces the other. Orientation distance graphs was introduced by Chartrand et al. in 2001. We provide new results about orientation distance graphs and simpler proofs to existing results, especially with regards to the bipartiteness of orientation distance graphs and the representation...

Coloring subgraphs with restricted amounts of hues

Wayne GoddardRobert Melville — 2017

Open Mathematics

We consider vertex colorings where the number of colors given to specified subgraphs is restricted. In particular, given some fixed graph F and some fixed set A of positive integers, we consider (not necessarily proper) colorings of the vertices of a graph G such that, for every copy of F in G, the number of colors it receives is in A. This generalizes proper colorings, defective coloring, and no-rainbow coloring, inter alia. In this paper we focus on the case that A is a singleton set. In particular,...

Vertex Colorings without Rainbow Subgraphs

Wayne GoddardHonghai Xu — 2016

Discussiones Mathematicae Graph Theory

Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal outerplanar...

Worm Colorings

Wayne GoddardKirsti WashHonghai Xu — 2015

Discussiones Mathematicae Graph Theory

Given a coloring of the vertices, we say subgraph H is monochromatic if every vertex of H is assigned the same color, and rainbow if no pair of vertices of H are assigned the same color. Given a graph G and a graph F, we define an F-WORM coloring of G as a coloring of the vertices of G without a rainbow or monochromatic subgraph H isomorphic to F. We present some results on this concept especially as regards to the existence, complexity, and optimization within certain graph classes. The focus is...

Hereditary domination and independence parameters

Wayne GoddardTeresa HaynesDebra Knisley — 2004

Discussiones Mathematicae Graph Theory

For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.

On distances between isomorphism classes of graphs

Gerhard BenadéWayne GoddardTerry A. McKeePaul A. Winter — 1991

Mathematica Bohemica

In 1986, Chartrand, Saba and Zou [3] defined a measure of the distance between (the isomorphism classes of) two graphs based on 'edge rotations'. Here, that measure and two related measures are explored. Various bounds, exact values for classes of graphs and relationships are proved, and the three measures are shown to be intimately linked to 'slowly-changing' parameters.

Minimal claw-free graphs

P. DankelmannHenda C. SwartP. van den BergWayne GoddardM. D. Plummer — 2008

Czechoslovak Mathematical Journal

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K 1 , 3 (claw) as an induced subgraph and if, for each edge e of G , G - e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.

Offensive alliances in graphs

A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number...

Page 1

Download Results (CSV)