Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "neighborhood graph" wg kryterium: Temat


Wyświetlanie 1-15 z 15
Tytuł:
Iterated neighborhood graphs
Autorzy:
Sonntag, Martin
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/743216.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
neighborhood graph
2-step graph
neighborhood completeness number
Opis:
The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V,E_N)$ where $E_N$ = {{a,b} | a ≠ b, {x,a} ∈ E and {x,b} ∈ E for some x ∈ V}. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite.
We present some results concerning the k-iterated neighborhood graph $N^k(G) : = N(N(...N(G)))$ of G. In particular we investigate conditions for G and k such that $N^k(G)$ becomes a complete graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 403-417
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Path-Neighborhood Graphs
Autorzy:
Laskar, R.C.
Mulder, Henry Martyn
Powiązania:
https://bibliotekanauki.pl/articles/30098149.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
path-neighborhood graph
outerplanar graph
MOP
snake
3- sun
k-fun
Opis:
A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A $ P_k $-graph is a path-neighborhood graph in which every neighborhood is a $ P_k $, where $ P_k $ is the path on $ k $ vertices. The $ P_k $-graphs are characterized for $ k \leq 4 $.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 731-745
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graph Operations and Neighborhood Polynomials
Autorzy:
Alipour, Maryam
Tittmann, Peter
Powiązania:
https://bibliotekanauki.pl/articles/32083862.pdf
Data publikacji:
2021-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
neighborhood complex
neighborhood polynomial
domination polynomial
graph operations
graph degeneracy
Opis:
The neighborhood polynomial of graph G is the generating function for the number of vertex subsets of G of which the vertices have a common neighbor in G. In this paper, we investigate the behavior of this polynomial under several graph operations. Specifically, we provide an explicit formula for the neighborhood polynomial of the graph obtained from a given graph G by vertex attachment. We use this result to propose a recursive algorithm for the calculation of the neighborhood polynomial. Finally, we prove that the neighborhood polynomial can be found in polynomial-time in the class of k-degenerate graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 697-711
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graph Exponentiation and Neighborhood Reconstruction
Autorzy:
Hammack, Richard H.
Powiązania:
https://bibliotekanauki.pl/articles/32083841.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
neighborhood reconstructible graphs
graph exponentiation
Opis:
Any graph $G$ admits a neighborhood multiset \(\mathscr{N}(G) = \{N_G(x) | x ∈ V (G)\}\) whose elements are precisely the open neighborhoods of $G$. We say $G$ is neighborhood reconstructible if it can be reconstructed from \(\mathscr{N}(G)\), that is, if \(G ≅ H\) whenever \(\mathscr{N}(G) = \mathscr{N}(H)\) for some other graph $H$. This note characterizes neighborhood reconstructible graphs as those graphs $G$ that obey the exponential cancellation \(G^{K_2} ≅ H^{K_2} ⇒ G ≅ H\).
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 335-339
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the structure of compact graphs
Autorzy:
Nikandish, R.
Shaveisi, F.
Powiązania:
https://bibliotekanauki.pl/articles/255638.pdf
Data publikacji:
2017
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
compact graph
vertex degree
cycle
neighborhood
Opis:
A simple graph G is called a compact graph if G contains no isolated vertices and for each pair x, y of non-adjacent vertices of G, there is a vertex z with N(x) ∪ N(y) ⊆ N(z), where N(v) is the neighborhood of v, for every vertex v of G. In this paper, compact graphs with sufficient number of edges are studied. Also, it is proved that every regular compact graph is strongly regular. Some results about cycles in compact graphs are proved, too. Among other results, it is proved that if the ascending chain condition holds for the set of neighbors of a compact graph G, then the descending chain condition holds for the set of neighbors of G.
Źródło:
Opuscula Mathematica; 2017, 37, 6; 875-886
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Maxclique and unit disk characterizations of strongly chordal graphs
Autorzy:
Caria, Pablo De
McKee, Terry A.
Powiązania:
https://bibliotekanauki.pl/articles/30148683.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chordal graph
strongly chordal graph
clique
maxclique
closed neighborhood
Opis:
Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 593-602
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Extension of several sufficient conditions for Hamiltonian graphs
Autorzy:
Ainouche, Ahmed
Powiązania:
https://bibliotekanauki.pl/articles/744192.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hamiltonian graph
dual closure
neighborhood closure
Opis:
Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖{u})|+d(u) ≥ n-1. Using the concept of dual closure, we prove that
1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇
2. G is nonhamiltonian if and only if its 0-dual closure is either the graph $(K_r ∪ Kₛ ∪ Kₜ) ∨ K₂$, 1 ≤ r ≤ s ≤ t or the graph $((n+1)/2)K₁ ∨ K_{(n-1)/2}$.
It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph satisfying the above condition. From this main result we derive a large number of extensions of previous sufficient conditions for hamiltonian graphs. All these results are sharp.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 23-39
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11
Autorzy:
Borodin, Oleg V.
Ivanova, Anna O.
Kazak, Olesya N.
Powiązania:
https://bibliotekanauki.pl/articles/31342287.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
structure properties
3-polytope
neighborhood
Opis:
In 1940, Lebesgue proved that every 3-polytope contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13). In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6), where all parameters are tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 615-625
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on possible density and diameter of countere xamples to the Seymour’s second neighborhood conjecture
Autorzy:
Zelenskiy, Oleksiy
Darmosiuk, Valentyna
Nalivayko, Illia
Powiązania:
https://bibliotekanauki.pl/articles/2052069.pdf
Data publikacji:
2021
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
graph theory
Seymour’s second neighborhood conjecture
density of graph
diameter of graph
Opis:
Seymour’s second neighborhood conjecture states that every simple digraph without loops or 2-cycles contains a vertex whose second neighborhood is at least as large as its first. In this paper we show, that from falsity of Seymour’s second neighborhood conjecture it follows that there exist strongly-connected counterexamples with both low and high density (dense and sparse graph). Moreover, we show that if there is a counterexample to conjecture, then it is possible to construct counterexample with any diameter k ≥ 3
Źródło:
Opuscula Mathematica; 2021, 41, 4; 601-605
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the hat problem on a graph
Autorzy:
Krzywkowski, M.
Powiązania:
https://bibliotekanauki.pl/articles/256048.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
hat problem
graph
degree
neighborhood
neighborhood-dominated
unicyclic
universal vertex
Nordhaus-Gaddum
Opis:
The topic of this paper is the hat problem in which each of n players is uniformly and independently fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player can see everybody excluding himself. We consider such a problem on a graph, where vertices correspond to players, and a player can see each player to whom he is connected by an edge. The solution of the hat problem on a graph is known for trees and for cycles on four or at least nine vertices. In this paper first we give an upper bound on the maximum chance of success for graphs with neighborhood-dominated vertices. Next we solve the problem on unicyclic graphs containing a cycle on at least nine vertices. We prove that the maximum chance of success is one by two. Then we consider the hat problem on a graph with a universal vertex. We prove that there always exists an optimal strategy such that in every case some vertex guesses its color. Moreover, we prove that there exists a graph with a universal vertex for which there exists an optimal strategy such that in some case no vertex guesses its color. We also give some Nordhaus-Gaddum type inequalities.
Źródło:
Opuscula Mathematica; 2012, 32, 2; 285-296
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected
Autorzy:
Wang, Shiying
Wang, Meiyu
Zhang, Lei
Powiązania:
https://bibliotekanauki.pl/articles/31341790.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
neighborhood
k -restricted edge connectivity
super k -restricted edge connected graph
Opis:
For a subset $S$ of edges in a connected graph $G$, $S$ is a $k$-restricted edge cut if $G − S$ is disconnected and every component of $G − S$ has at least $k$ vertices. The $k$-restricted edge connectivity of $G$, denoted by $ \lambda_k (G) $, is defined as the cardinality of a minimum $k$-restricted edge cut. Let \( \xi_k(G) = \text{min} \{ | [ X , \overline{X} ] | : |X| = k, G[X] \) is connected $ \} $, where $ \overline{X} = V (G) \backslash X $. A graph $G$ is super $k$-restricted edge connected if every minimum $k$-restricted edge cut of $G$ isolates a component of order exactly $k$. Let $k$ be a positive integer and let $G$ be a graph of order $ \nu \ge 2k$. In this paper, we show that if $ | N( u ) \cup N( v ) | \ge k +1 $ for all pairs $u$, $v$ of nonadjacent vertices and $ \xi_k (G) \le \floor{ ν/2}+k $, then $G$ is super $k$-restricted edge connected.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 537-545
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
Autorzy:
Batueva, Ts.Ch-D.
Borodin, O.V.
Ivanova, A.O.
Nikiforov, D.V.
Powiązania:
https://bibliotekanauki.pl/articles/32361718.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
structural properties
3-polytope
5-star
neighborhood
Opis:
In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. (6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13) Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P5. In 2018, Borodin, Ivanova, Kazak proved that every forbidding vertices of degree from 7 to 11 results in a tight description (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6). Recently, Borodin, Ivanova, and Kazak proved every 3-polytope in P5 with no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences (5, 5, 5, 5, ∞) and (5, 5, 10, 5, 12), which is tight and improves a corresponding description (5, 5, 5, 5, ∞), (5, 5, 9, 5, 17), (5, 5, 10, 5, 14), (5, 5, 11, 5, 13) that follows from the Lebesgue Theorem. The purpose of this paper is to prove that every 3-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a 5-vertex whose neighborhood is majorized by one of the ordered sequences (5, 5, 5, 5, ∞), (5, 5, 8, 5, 14), or (5, 5, 10, 5, 12).
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 535-548
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertices with the second neighborhood property in Eulerian digraphs
Autorzy:
Cary, Michael
Powiązania:
https://bibliotekanauki.pl/articles/952854.pdf
Data publikacji:
2019
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
Eulerian digraph
second neighborhood conjecture
cycle decomposition
cycle intersection graph
Opis:
The Second Neighborhood Conjecture states that every simple digraph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood, i.e. a vertex with the Second Neighborhood Property. A cycle intersection graph of an even graph is a new graph whose vertices are the cycles in a cycle decomposition of the original graph and whose edges represent vertex intersections of the cycles. By using a digraph variant of this concept, we prove that Eulerian digraphs which admit a simple cycle intersection graph not only adhere to the Second Neighborhood Conjecture, but that local simplicity can, in some cases, also imply the existence of a Seymour vertex in the original digraph.
Źródło:
Opuscula Mathematica; 2019, 39, 6; 765-772
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Neighborhood Condition for Fractional ID-[A, B]-Factor-Critical Graphs
Autorzy:
Zhou, Sizhong
Yang, Fan
Sun, Zhiren
Powiązania:
https://bibliotekanauki.pl/articles/31340936.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
minimum degree
neighborhood
fractional [a
b]-factor
fractional ID-[a
b]-factor-critical graph
Opis:
Let $G$ be a graph of order $n$, and let $a$ and $b$ be two integers with $ 1 \le a \le b $. Let $ h : E(G) \rightarrow [0, 1] $ be a function. If \( a \le \Sigma_{ e \ni x } h(e) \le b \) holds for any $ x \in V (G) $, then we call $ G[F_h] $ a fractional $ [a, b] $-factor of $ G $ with indicator function $ h $, where $ F_h = \{ e \in E(G) : h(e) > 0 \} $. A graph $G$ is fractional independent-set-deletable $[a, b]$-factor-critical (in short, fractional ID-$[a, b]$-factor-critical) if $ G − I $ has a fractional $ [a, b] $-factor for every independent set $I$ of $G$. In this paper, it is proved that if $ n \ge \frac{(a+2b)(2a+2b-3)+1}{b} $, $ \delta (G) \ge \frac{bn}{a+2b} + a $ and $ | N_G(x) \cup N_G(y) | \ge \frac{(a+b)n}{a+2b} $ for any two nonadjacent vertices $ x, y \in V (G) $, then $ G $ is fractional ID-$[a, b]$-factor-critical. Furthermore, it is shown that this result is best possible in some sense.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 409-418
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Variations on a sufficient condition for Hamiltonian graphs
Autorzy:
Ainouche, Ahmed
Lapiquonne, Serge
Powiązania:
https://bibliotekanauki.pl/articles/743758.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cycles
partially square graph
degree sum
independent sets
neighborhood unions and intersections
dual closure
Opis:
Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition $N_G(x) ⊆ N_G[u] ∪ N_G[v]$, where $N_G[x] = N_G(x) ∪ {x}$. In particular, this condition is satisfied if x does not center a claw (an induced $K_{1,3}$). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = {x,y,z} we define
σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|.
Flandrin et al. proved that a 2-connected graph G is hamiltonian if [σ̅]₃(X) ≥ n holds for any independent triple X in G. Replacing X in G by X in the larger graph G*, Wu et al. improved recently this result. In this paper we characterize the nonhamiltonian 2-connected graphs G satisfying the condition [σ̅]₃(X) ≥ n-1 where X is independent in G*. Using the concept of dual closure we (i) give a short proof of the above results and (ii) we show that each graph G satisfying this condition is hamiltonian if and only if its dual closure does not belong to two well defined exceptional classes of graphs. This implies that it takes a polynomial time to check the nonhamiltonicity or the hamiltonicity of such G.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 229-240
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-15 z 15

    Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies