All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 102

Showing per page

2-Tone Colorings in Graph Products

Jennifer Loe, Danielle Middelbrooks, Ashley Morris, Kirsti Wash (2015)

Discussiones Mathematicae Graph Theory

A variation of graph coloring known as a t-tone k-coloring assigns a set of t colors to each vertex of a graph from the set {1, . . . , k}, where the sets of colors assigned to any two vertices distance d apart share fewer than d colors in common. The minimum integer k such that a graph G has a t- tone k-coloring is known as the t-tone chromatic number. We study the 2-tone chromatic number in three different graph products. In particular, given graphs G and H, we bound the 2-tone chromatic number...

A lower bound for the packing chromatic number of the Cartesian product of cycles

Yolandé Jacobs, Elizabeth Jonck, Ernst Joubert (2013)

Open Mathematics

Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9...

A Note on Total Graphs

S.F. Forouhandeh, N. Jafari Rad, B.H. Vaqari Motlagh, H.P. Patil, R. Pandiya Raj (2015)

Discussiones Mathematicae Graph Theory

Erratum Identification and corrections of the existing mistakes in the paper On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361-371.

Adjacent vertex distinguishing edge colorings of the direct product of a regular graph by a path or a cycle

Laura Frigerio, Federico Lastaria, Norma Zagaglia Salvi (2011)

Discussiones Mathematicae Graph Theory

In this paper we investigate the minimum number of colors required for a proper edge coloring of a finite, undirected, regular graph G in which no two adjacent vertices are incident to edges colored with the same set of colors. In particular, we study this parameter in relation to the direct product of G by a path or a cycle.

Asymptotic spectral distributions of distance-k graphs of Cartesian product graphs

Yuji Hibino, Hun Hee Lee, Nobuaki Obata (2013)

Colloquium Mathematicae

Let G be a finite connected graph on two or more vertices, and G [ N , k ] the distance-k graph of the N-fold Cartesian power of G. For a fixed k ≥ 1, we obtain explicitly the large N limit of the spectral distribution (the eigenvalue distribution of the adjacency matrix) of G [ N , k ] . The limit distribution is described in terms of the Hermite polynomials. The proof is based on asymptotic combinatorics along with quantum probability theory.

Boolean differential operators

Jorge Catumba, Rafael Díaz (2014)

Commentationes Mathematicae Universitatis Carolinae

We consider four combinatorial interpretations for the algebra of Boolean differential operators and construct, for each interpretation, a matrix representation for the algebra of Boolean differential operators.

Cancellation of direct products of digraphs

Richard H. Hammack, Katherine E. Toman (2010)

Discussiones Mathematicae Graph Theory

We investigate expressions of form A×C ≅ B×C involving direct products of digraphs. Lovász gave exact conditions on C for which it necessarily follows that A ≅ B. We are here concerned with a different aspect of cancellation. We describe exact conditions on A for which it necessarily follows that A ≅ B. In the process, we do the following: Given an arbitrary digraph A and a digraph C that admits a homomorphism onto an arc, we classify all digraphs B for which A×C ≅ B×C.

Characterization of Line-Consistent Signed Graphs

Daniel C. Slilaty, Thomas Zaslavsky (2015)

Discussiones Mathematicae Graph Theory

The line graph of a graph with signed edges carries vertex signs. A vertex-signed graph is consistent if every circle (cycle, circuit) has positive vertex-sign product. Acharya, Acharya, and Sinha recently characterized line-consistent signed graphs, i.e., edge-signed graphs whose line graphs, with the naturally induced vertex signature, are consistent. Their proof applies Hoede’s relatively difficult characterization of consistent vertex-signed graphs. We give a simple proof that does not depend...

Characterizations of the Family of All Generalized Line Graphs-Finite and Infinite-and Classification of the Family of All Graphs Whose Least Eigenvalues ≥ −2

Gurusamy Rengasamy Vijayakumar (2013)

Discussiones Mathematicae Graph Theory

The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented by the...

Characterizing Cartesian fixers and multipliers

Stephen Benecke, Christina M. Mynhardt (2012)

Discussiones Mathematicae Graph Theory

Let G ☐ H denote the Cartesian product of the graphs G and H. In 2004, Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24(3) (2004), 389-402] characterized prism fixers, i.e., graphs G for which γ(G ☐ K₂) = γ(G), and noted that γ(G ☐ Kₙ) ≥ min{|V(G)|, γ(G)+n-2}. We call a graph G a consistent fixer if γ(G ☐ Kₙ) = γ(G)+n-2 for each n such that 2 ≤ n < |V(G)|- γ(G)+2, and characterize this class of graphs. Also in 2004, Burger,...

Closed Formulae for the Strong Metric Dimension of Lexicographi

Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez (2016)

Discussiones Mathematicae Graph Theory

Given a connected graph G, a vertex w ∈ V (G) strongly resolves two vertices u, v ∈ V (G) if there exists some shortest u − w path containing v or some shortest v − w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several relationships between the strong metric dimension...

Codes and designs from triangular graphs and their line graphs

Washiela Fish, Khumbo Kumwenda, Eric Mwambene (2011)

Open Mathematics

For any prime p, we consider p-ary linear codes obtained from the span over 𝔽 p p of rows of incidence matrices of triangular graphs, differences of the rows and adjacency matrices of line graphs of triangular graphs. We determine parameters of the codes, minimum words and automorphism groups. We also show that the codes can be used for full permutation decoding.

Computing the Metric Dimension of a Graph from Primary Subgraphs

Dorota Kuziak, Juan A. Rodríguez-Velázquez, Ismael G. Yero (2017)

Discussiones Mathematicae Graph Theory

Let G be a connected graph. Given an ordered set W = {w1, . . . , wk} ⊆ V (G) and a vertex u ∈ V (G), the representation of u with respect to W is the ordered k-tuple (d(u, w1), d(u, w2), . . . , d(u, wk)), where d(u, wi) denotes the distance between u and wi. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum cardinality metric generator is called a metric basis of G and its cardinality is called the metric dimension of G. It is well...

Containers and wide diameters of P 3 ( G )

Daniela Ferrero, Manju K. Menon, A. Vijayakumar (2012)

Mathematica Bohemica

The P 3 intersection graph of a graph G has for vertices all the induced paths of order 3 in G . Two vertices in P 3 ( G ) are adjacent if the corresponding paths in G are not disjoint. A w -container between two different vertices u and v in a graph G is a set of w internally vertex disjoint paths between u and v . The length of a container is the length of the longest path in it. The w -wide diameter of G is the minimum number l such that there is a w -container of length at most l between any pair of different...

Currently displaying 1 – 20 of 102

Page 1 Next