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 24

Showing per page

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...

Sharp bounds for the number of matchings in generalized-theta-graphs

Ardeshir Dolati, Somayyeh Golalizadeh (2012)

Discussiones Mathematicae Graph Theory

A generalized-theta-graph is a graph consisting of a pair of end vertices joined by k (k ≥ 3) internally disjoint paths. We denote the family of all the n-vertex generalized-theta-graphs with k paths between end vertices by Θⁿₖ. In this paper, we determine the sharp lower bound and the sharp upper bound for the total number of matchings of generalized-theta-graphs in Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.

Solution to the problem of Kubesa

Mariusz Meszka (2008)

Discussiones Mathematicae Graph Theory

An infinite family of T-factorizations of complete graphs K 2 n , where 2n = 56k and k is a positive integer, in which the set of vertices of T can be split into two subsets of the same cardinality such that degree sums of vertices in both subsets are not equal, is presented. The existence of such T-factorizations provides a negative answer to the problem posed by Kubesa.

Some recent results on domination in graphs

Michael D. Plummer (2006)

Discussiones Mathematicae Graph Theory

In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; (3) upper bounds...

Splitting Cubic Circle Graphs

Lorenzo Traldi (2016)

Discussiones Mathematicae Graph Theory

We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.

Star number and star arboricity of a complete multigraph

Chiang Lin, Tay-Woei Shyu (2006)

Czechoslovak Mathematical Journal

Let G be a multigraph. The star number s ( G ) of G is the minimum number of stars needed to decompose the edges of G . The star arboricity s a ( G ) of G is the minimum number of star forests needed to decompose the edges of G . As usual λ K n denote the λ -fold complete graph on n vertices (i.e., the multigraph on n vertices such that there are λ edges between every pair of vertices). In this paper, we prove that for n ≥ 2 ...

Star-Cycle Factors of Graphs

Yoshimi Egawa, Mikio Kano, Zheng Yan (2014)

Discussiones Mathematicae Graph Theory

A spanning subgraph F of a graph G is called a star-cycle factor of G if each component of F is a star or cycle. Let G be a graph and f : V (G) → {1, 2, 3, . . .} be a function. Let W = {v ∈ V (G) : f(v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor F with the property that (i) if a component D of F is a star with center v, then degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S f(x) for all...

Currently displaying 1 – 20 of 24

Page 1 Next