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 48

Showing per page

Saturation numbers for trees.

Faudree, Jill, Faudree, Ralph J., Gould, Ronald J., Jacobson, Michael S. (2009)

The Electronic Journal of Combinatorics [electronic only]

Sequences of Maximal Degree Vertices in Graphs

Khadzhiivanov, Nickolay, Nenov, Nedyalko (2004)

Serdica Mathematical Journal

2000 Mathematics Subject Classification: 05C35.Let Γ(M ) where M ⊂ V (G) be the set of all vertices of the graph G adjacent to any vertex of M. If v1, . . . , vr is a vertex sequence in G such that Γ(v1, . . . , vr ) = ∅ and vi is a maximal degree vertex in Γ(v1, . . . , vi−1), we prove that e(G) ≤ e(K(p1, . . . , pr)) where K(p1, . . . , pr ) is the complete r-partite graph with pi = |Γ(v1, . . . , vi−1) Γ(vi )|.

Set colorings in perfect graphs

Ralucca Gera, Futaba Okamoto, Craig Rasmussen, Ping Zhang (2011)

Mathematica Bohemica

For a nontrivial connected graph G , let c : V ( G ) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v ∈ V ( G ) , the neighborhood color set NC ( v ) is the set of colors of the neighbors of v . The coloring c is called a set coloring if NC ( u ) ≠ NC ( v ) for every pair u , v of adjacent vertices of G . The minimum number of colors required of such a coloring is called the set chromatic number χ s ( G ) . We show that the decision variant of determining χ s ( G ) is NP-complete in the general case, and show that χ s ( G ) can be...

Signed total domination number of a graph

Bohdan Zelinka (2001)

Czechoslovak Mathematical Journal

The signed total domination number of a graph is a certain variant of the domination number. If v is a vertex of a graph G , then N ( v ) is its oper neighbourhood, i.e. the set of all vertices adjacent to v in G . A mapping f : V ( G ) → { - 1 , 1 } , where V ( G ) is the vertex set of G , is called a signed total dominating function (STDF) on G , if ∑ x ∈ N ( v ) f ( x ) ≥ 1 for each v ∈ V ( G ) . The minimum of values ∑ x ∈ V ( G ) f ( x ) , taken over all STDF’s of G , is called the signed total domination number of G and denoted by γ s t ( G ) . A theorem stating lower bounds for γ s t ( G ) is stated for the...

Some applications of pq-groups in graph theory

Geoffrey Exoo (2004)

Discussiones Mathematicae Graph Theory

We describe some new applications of nonabelian pq-groups to construction problems in Graph Theory. The constructions include the smallest known trivalent graph of girth 17, the smallest known regular graphs of girth five for several degrees, along with four edge colorings of complete graphs that improve lower bounds on classical Ramsey numbers.

Some maximum multigraphs and edge/vertex distance colourings

Zdzisław Skupień (1995)

Discussiones Mathematicae Graph Theory

Shannon-Vizing-type problems concerning the upper bound for a distance chromatic index of multigraphs G in terms of the maximum degree Δ(G) are studied. Conjectures generalizing those related to the strong chromatic index are presented. The chromatic d-index and chromatic d-number of paths, cycles, trees and some hypercubes are determined. Among hypercubes, however, the exact order of their growth is found.

Some news about the independence number of a graph

Jochen Harant (2000)

Discussiones Mathematicae Graph Theory

For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.

Currently displaying 1 – 20 of 48

Page 1 Next