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 44

Showing per page

Valency seven symmetric graphs of order 2 p q

Xiao-Hui Hua, Li Chen (2018)

Czechoslovak Mathematical Journal

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, all connected valency seven symmetric graphs of order 2 p q are classified, where p , q are distinct primes. It follows from the classification that there is a unique connected valency seven symmetric graph of order 4 p , and that for odd primes p and q , there is an infinite family of connected valency seven one-regular graphs of order 2 p q with solvable automorphism groups, and there are four sporadic ones...

Value sets of graphs edge-weighted with elements of a finite abelian group

Edgar G. DuCasse, Michael L. Gargano, Louis V. Quintas (2010)

Discussiones Mathematicae Graph Theory

Given a graph G = (V,E) of order n and a finite abelian group H = (H,+) of order n, a bijection f of V onto H is called a vertex H-labeling of G. Let g(e) ≡ (f(u)+f(v)) mod H for each edge e = u,v in E induce an edge H-labeling of G. Then, the sum H v a l f ( G ) ≡ ∑ e ∈ E g ( e ) m o d H is called the H-value of G relative to f and the set HvalS(G) of all H-values of G over all possible vertex H-labelings is called the H-value set of G. Theorems determining HvalS(G) for given H and G are obtained.

Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index

Mustapha Aouchiche, Pierre Hansen, Dragan Stevanović (2009)

Discussiones Mathematicae Graph Theory

The AutoGraphiX 2 system is used to compare the index of a connected graph G with a number of other graph theoretical invariants, i.e., chromatic number, maximum, minimum and average degree, diameter, radius, average distance, independence and domination numbers. In each case, best possible lower and upper bounds, in terms of the order of G, are sought for sums, differences, ratios and products of the index and another invariant. There are 72 cases altogether: in 7 cases known results were reproduced,...

Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche, Serge Lapiquonne (2007)

Discussiones Mathematicae Graph Theory

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition N G ( x ) ⊆ N G [ u ] ∪ N G [ v ] , where N G [ x ] = N G ( x ) ∪ x . In particular, this condition is satisfied if x does not center a claw (an induced K 1 , 3 ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian if...

Various Bounds for Liar’s Domination Number

Abdollah Alimadadi, Doost Ali Mojdeh, Nader Jafari Rad (2016)

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly...

Vertex coloring the square of outerplanar graphs of low degree

Geir Agnarsson, Magnús M. Halldórsson (2010)

Discussiones Mathematicae Graph Theory

Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.

Vertex Colorings without Rainbow Subgraphs

Wayne Goddard, Honghai 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...

Currently displaying 1 – 20 of 44

Page 1 Next