Temat: graph - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Pₘ-saturated bipartite graphs with minimum size
Autorzy:: Dudek, Aneta
Wojda, A.
Tematy:: graph
saturated graph
extremal graph
bipartite graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744479.pdf Link otwiera się w nowym oknie
Opis:: A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Pm-saturated graphs with minimum size
Autorzy:: Dudek, A.
Wojda, A.P.
Tematy:: graph
saturated graph
extremal graph; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/2050147.pdf Link otwiera się w nowym oknie
Opis:: By Pm we denote a path of order m. A graph G is saidto be P$\text{}_{m}$ - saturated if G has no subgraph isomorphic to P$\text{}_{m}$ and adding any new edge to G creates a Pm in G. In 1986 L. Kaszonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size $sat(n; P\text{}_{m}$) of P$\text{}_{m}$-saturated graph and characterize the graphs of $Sat(n; P\text{}_{m}$) - the set of P$\text{}_{m}$-saturated graphs of minimum size. They have solved this problem for $n \geq a_{m}$ where $$ a_{m} = \begin{cases} 3 \cdot 2^{k-1} - 2~~\text{if}~m = 2k,k~~~~~~~\\ 2^{k+1} - 2~~~~~~\text{if}~m = 2k + 1, k \geq 2 \end{cases} $$ We define $$ b_{m} = \begin{cases} 3 \cdot 2^{k-2}~~~~~~~\text{if}~m = 2k,k \geq 3 \\ 3 \cdot 2 ^{k-1} - 1~~\text{if}~m = 2k + 1,k \geq 3 \end{cases} $$ and give $sat(n; P\text{}_{m}$) and $Sat(n; P\text{}_{m})$ for $m \geq 6$ and $b_{m} \leq n < a_{m}$
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: (H,k) stable graphs with minimum size
Autorzy:: Dudek, Aneta
Szymański, Artur
Zwonek, Małgorzata
Tematy:: graph
stable graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743537.pdf Link otwiera się w nowym oknie
Opis:: Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(₃,k), Q(₄,k), $Q(K_{1,p},k)$ and Q(Kₛ,k).
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: (H,k) stable bipartite graphs with minimum size
Autorzy:: Dudek, Aneta
Zwonek, Małgorzata
Tematy:: graph
vertex stable graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744467.pdf Link otwiera się w nowym oknie
Opis:: Let us call a graph G(H;k) vertex stable if it contains a subgraph H after removing any of its k vertices. In this paper we are interested in finding the $(K_{n,n+1};1)$ (respectively $(K_{n,n};1)$) vertex stable graphs with minimum size.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Evolutionary approach to obtain graph covering by densely connected subgraphs
Autorzy:: Stańczak, J.
Potrzebowski, H.
Sęp, K.
Tematy:: graph
clique
graph clustering
evolutionary algorithms; Pokaż więcej
Wydawca:: Polska Akademia Nauk. Instytut Badań Systemowych PAN
Powiązania:: https://bibliotekanauki.pl/articles/206170.pdf Link otwiera się w nowym oknie
Opis:: This article describes two evolutionary methods for dividing a graph into densely connected structures. The first method deals with the clustering problem, where the element order plays an important role. This formulation is very useful for a wide range of Decision Support System (DSS) applications. The proposed clustering method consists of two stages. The first is the stage of data matrix reorganization, using a specialized evolutionary algorithm. The second stage is the final clustering step and is performed using a simple clustering method (SCM). The second described method deals with a completely new partitioning algorithm, based on the subgraph structure we call α-clique. The α-clique is a generalization of the clique concept with the introduction of parameter α, which imposes for all vertices of the subgraph the minimal percentage (α*100%) of vertices of this subgraph that must be connected with vertices of this α-clique. Traditional clique is an instance of α-clique with α = 1. Application of this parameter makes it possible to control the degree (or strength) of connections among vertices (nodes) of this subgraph structure. The evolutionary approach is proposed as a method that enables finding separate α-cliques that cover the set of graph vertices.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: Acyclic reducible bounds for outerplanar graphs
Autorzy:: Borowiecki, Mieczysław
Fiedorowicz, Anna
Hałuszczak, Mariusz
Tematy:: graph
acyclic colouring
additive hereditary class
outerplanar graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743164.pdf Link otwiera się w nowym oknie
Opis:: For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions:
1. $G[V_i] ∈ _i$ for i = 1,...,n,
2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that $u ∈ V_i$ and $v ∈ V_j$ is acyclic.
A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring. If ⊆ R, then we say that R is an acyclic reducible bound for . In this paper we present acyclic reducible bounds for the class of outerplanar graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Decomposition of complete graphs into factors of diameter two and three
Autorzy:: Vukicević, Damir
Tematy:: decomposition
graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743378.pdf Link otwiera się w nowym oknie
Opis:: We analyze a minimum number of vertices of a complete graph that can be decomposed into one factor of diameter 2 and k factors of diameter at most 3. We find exact values for k ≤ 4 and the asymptotic value of the ratio of this number and k when k tends to infinity. We also find the asymptotic value of the ratio of the number of vertices of the smallest complete graph that can be decomposed into p factors of diameter 2 and k factors of diameter 3 and number k when p is fixed.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Two graphs with a common edge
Autorzy:: Badura, Lidia
Tematy:: graph
adjacency matrix
determinant of graph
path
cycle; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30148254.pdf Link otwiera się w nowym oknie
Opis:: Let $G = G_1 ∪ G_2$ be the sum of two simple graphs $G_1,G_2$ having a common edge or $G = G_1 ∪ e_1 ∪ e_2 ∪ G_2$ be the sum of two simple disjoint graphs $G_1,G_2$ connected by two edges $e_1$ and $e_2$ which form a cycle $C_4$ inside $G$. We give a method of computing the determinant $det A(G)$ of the adjacency matrix of $G$ by reducing the calculation of the determinant to certain subgraphs of $G_1$ and $G_2$. To show the scope and effectiveness of our method we give some examples.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Some news about the independence number of a graph
Autorzy:: Harant, Jochen
Tematy:: graph
independence; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743691.pdf Link otwiera się w nowym oknie
Opis:: 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: On domination in graphs
Autorzy:: Göring, Frank
Harant, Jochen
Tematy:: graph
domination; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744282.pdf Link otwiera się w nowym oknie
Opis:: For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "graph" wg kryterium: Temat