In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define ℳH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join recursively and show that the maximum independent set problem, the maximum clique problem, the minimum coloring problem, and the minimum clique cover problem can be solved efficiently for ℳH.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ from V to the set {1, . . . , n} such that the weight w(x) = ∑y∈NG(x) ℓ(y) of every vertex x ∈ V is equal to the same element μ, called the magic constant. In this paper, we study unions of distance magic graphs as well as some properties of such graphs.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
A vertex v ∈ V (G) is said to distinguish two vertices x, y ∈ V (G) of a graph G if the distance from v to x is di erent from the distance from v to y. A set W ⊆ V (G) is a total resolving set for a graph G if for every pair of vertices x, y ∈ V (G), there exists some vertex w ∈ W − {x, y} which distinguishes x and y, while W is a weak total resolving set if for every x ∈ V (G)−W and y ∈ W, there exists some w ∈ W −{y} which distinguishes x and y. A weak total resolving set of minimum cardinality is called a weak total metric basis of G and its cardinality the weak total metric dimension of G. Our main contributions are the following ones: (a) Graphs with small and large weak total metric bases are characterised. (b) We explore the (tight) relation to independent 2-domination. (c) We introduce a new graph parameter, called weak total adjacency dimension and present results that are analogous to those presented for weak total dimension. (d) For trees, we derive a characterisation of the weak total (adjacency) metric dimension. Also, exact figures for our parameters are presented for (generalised) fans and wheels. (e) We show that for Cartesian product graphs, the weak total (adjacency) metric dimension is usually pretty small. (f) The weak total (adjacency) dimension is studied for lexicographic products of graphs.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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 known that the problem of finding the metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the metric dimension of graphs with cut vertices. The main results are applied to specific constructions including rooted product graphs, corona product graphs, block graphs and chains of graphs.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ {1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋} be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k $\delta _M (v) \ge {{\delta _G (v)} \over 2} + k$ , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this article we study the open k-monopoly number of strong product graphs. We present general lower and upper bounds for the open k-monopoly number of strong product graphs. Moreover, we study in addition the open 0-monopolies of several specific families of strong product graphs.
7
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G, t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
8
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The concept of generalized k-connectivity κk(G), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity τk(G) was also introduced by Hager in 1985, which is a specialization of generalized k-connectivity but a generalization of the classical connectivity. Another generalized connectivity of a graph G, named k-connectivity κ′k(G), introduced by Chartrand et al. in 1984, is a generalization of the cut-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of κ′k(G) and τk(G) by showing that for a connected graph G of order n, if κ′k(G) ≠ n − k + 1 where k ≥ 3, then 1 ≤ κ′k(G) − τk(G) ≤ n − k; otherwise, 1 ≤ κ′k(G) ‘− τk(G) ≤ n − k + 1. Moreover, all of these bounds are sharp. We get a sharp upper bound for the 3-connectivity of the Cartesian product of any two connected graphs with orders at least 5. Especially, the exact values for some special cases are determined. Among our results, we also study the pendant tree-connectivity of Cayley graphs on Abelian groups of small degrees and obtain the exact values for τk(G), where G is a cubic or 4-regular Cayley graph on Abelian groups, 3 ≤ k ≤ n.
9
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The purpose of this paper is to study W(2, 2) Lie conformal algebra, which has a free ℂ[∂]-basis {L, M} such that [...] [LλL]=(∂+2λ)L,[LλM]=(∂+2λ)M,[MλM]=0 $\begin{equation}[{L_\lambda }L] = (\partial + 2\lambda )L,[{L_\lambda }M] = (\partial + 2\lambda )M,[{M_\lambda }M] = 0]\end{equation}$ . In this paper, we study conformal derivations, central extensions and conformal modules for this Lie conformal algebra. Also, we compute the cohomology of this Lie conformal algebra with coefficients in its modules. In particular, we determine its cohomology with trivial coefficients both for the basic and reduced complexes.
10
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition, we establish upper and lower bounds for the Laplacian Estrada index of Г(G) based on the vertex degrees of G. These bounds are also connected with the number of spanning trees in Г(G).
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.