On upper embeddability of complementary graphs
For a connected graph of order and a linear ordering of vertices of , , where is the distance between and . The upper traceable number of is , where the maximum is taken over all linear orderings of vertices of . It is known that if is a tree of order , then and if . All pairs for which there exists a tree of order and are determined and a characterization of all those trees of order with upper traceable number is established. For a connected graph of order...
Recent model of lifetime after a heart attack involves some integer coefficients. Our goal is to get these coefficients in simple way and transparent form. To this aim we construct a schema according to a rule which combines the ideas used in the Pascal triangle and the generalized Fibonacci and Lucas numbers
In this paper, we introduce the notion of a variety of graphs closed under isomorphic images, subgraph identifications and induced subgraphs (induced connected subgraphs) firstly and next closed under isomorphic images, subgraph identifications, circuits and cliques. The structure of the corresponding lattices is investigated.
In this paper we investigate varieties of orgraphs (that is, oriented graphs) as classes of orgraphs closed under isomorphic images, suborgraph identifications and induced suborgraphs, and we study the lattice of varieties of tournament-free orgraphs.
A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of -vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, and as well as are the only -vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.
A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.
A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.
A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the...
Let be an oriented graph of order and size . A -labeling of is a one-to-one function that induces a labeling of the arcs of defined by for each arc of . The value of a -labeling is A -labeling of is balanced if the value of is 0. An oriented graph is balanced if has a balanced labeling. A graph is orientably balanced if has a balanced orientation. It is shown that a connected graph of order is orientably balanced unless is a tree, , and every vertex of...
Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is . The maximum value of a γ-labeling of G is defined as ; while the minimum value of a γ-labeling of G is ; The values and are determined for double stars . We present characterizations of connected graphs G of order n for which or .