Informacja

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

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "Graph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 960
Tytuł:
Pₘ-saturated bipartite graphs with minimum size
Autorzy:
Dudek, Aneta
Wojda, A.
Powiązania:
https://bibliotekanauki.pl/articles/744479.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
saturated graph
extremal graph
bipartite graph
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 2; 197-211
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Pm-saturated graphs with minimum size
Autorzy:
Dudek, A.
Wojda, A.P.
Powiązania:
https://bibliotekanauki.pl/articles/2050147.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
graph
saturated graph
extremal graph
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}$
Źródło:
Opuscula Mathematica; 2004, 24, 1; 43-55
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Total Graphs
Autorzy:
Forouhandeh, S.F.
Jafari Rad, N.
Vaqari Motlagh, B.H.
Patil, H.P.
Pandiya Raj, R.
Powiązania:
https://bibliotekanauki.pl/articles/31339326.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total graph
central graph
middle graph
Mycielski graph
Opis:
Erratum Identification and corrections of the existing mistakes in the paper On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361-371.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 585-587
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The edge C₄ graph of some graph classes
Autorzy:
Menon, Manju
Vijayakumar, A.
Powiązania:
https://bibliotekanauki.pl/articles/744285.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge C₄ graph
threshold graph
block graph
geodetic graph
weakly geodetic graph
Opis:
The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices, there exists a super graph H such that C(H) = G and C(E₄(H)) = E₄(G). Also we give forbidden subgraph characterizations for E₄(G) being a threshold graph, block graph, geodetic graph and weakly geodetic graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 365-375
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
(H,k) stable graphs with minimum size
Autorzy:
Dudek, Aneta
Szymański, Artur
Zwonek, Małgorzata
Powiązania:
https://bibliotekanauki.pl/articles/743537.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
stable graph
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).
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 137-149
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs
Autorzy:
Bašić, Nino
Fowler, Patrick W.
Pisanski, Tomaž
Sciriha, Irene
Powiązania:
https://bibliotekanauki.pl/articles/32222533.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
signed graph
nut graph
singular graph
graph spectrum
Fowler construction
sign-balanced graph
sign-unbalanced graph
cocktail-party graph
Opis:
A signed graph has edge weights drawn from the set {+1, −1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller ‘seed’ graph, giving infinite series of both sign-balanced and sign-unbalanced ρ -regular nut graphs. Orders for which a regular nut graph with ρ = n − 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n − 2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1351-1382
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The i-chords of cycles and paths
Autorzy:
McKee, Terry
Powiązania:
https://bibliotekanauki.pl/articles/743264.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chord
chordal graph
strongly chordal graph
ptolemaic graph
trivially perfect graph
threshold graph
Opis:
An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)| ≥ i has an (i -2)-chord.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 607-615
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
4-chromatic Koester graphs
Autorzy:
Dobrynin, Andrey
Mel'nikov, Leonid
Powiązania:
https://bibliotekanauki.pl/articles/743274.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
4-critical graph
Grötzsch-Sachs graph
Koester graph
Opis:
Let G be a simple 4-regular plane graph and let S be a decomposition of G into edge-disjoint cycles. Suppose that every two adjacent edges on a face belong to different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Studies of coloring of graphs of this kind were originated by Grötzsch. Two 4-chromatic graphs generated by circles in the plane were constructed by Koester in 1984 [10,11,12]. Until now, no other examples of such graphs were known. We present fourteen new 4-chromatic graphs generated by circles in the plane.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 617-627
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Clique graph representations of ptolemaic graphs
Autorzy:
McKee, Terry
Powiązania:
https://bibliotekanauki.pl/articles/744102.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Ptolemaic graph
clique graph
chordal graph
clique tree
graph representation
Opis:
A graph is ptolemaic if and only if it is both chordal and distance-hereditary. Thus, a ptolemaic graph G has two kinds of intersection graph representations: one from being chordal, and the other from being distance-hereditary. The first of these, called a clique tree representation, is easily generated from the clique graph of G (the intersection graph of the maximal complete subgraphs of G). The second intersection graph representation can also be generated from the clique graph, as a very special case of the main result: The maximal Pₙ-free connected induced subgraphs of the p-clique graph of a ptolemaic graph G correspond in a natural way to the maximal $P_{n+1}$-free induced subgraphs of G in which every two nonadjacent vertices are connected by at least p internally disjoint paths.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 651-661
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Digraphs with isomorphic underlying and domination graphs: connected $UG^c(d)$
Autorzy:
Factor, Kim
Langley, Larry
Powiązania:
https://bibliotekanauki.pl/articles/743665.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination graph
domination
graph isomorphism
underlying graph
Opis:
The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 51-67
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
Autorzy:
Czap, Július
Przybyło, Jakub
Škrabuľáková, Erika
Powiązania:
https://bibliotekanauki.pl/articles/31341143.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
1-planar graph
bipartite graph
graph size
Opis:
A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 141-151
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Existence of Regular Nut Graphs for Degree at Most 11
Autorzy:
Fowler, Patrick W.
Gauci, John Baptist
Goedgebeur, Jan
Pisanski, Tomaž
Sciriha, Irene
Powiązania:
https://bibliotekanauki.pl/articles/31550028.pdf
Data publikacji:
2020-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
nut graph
core graph
regular graph
nullity
Opis:
A nut graph is a singular graph with one-dimensional kernel and corresponding eigenvector with no zero elements. The problem of determining the orders n for which d-regular nut graphs exist was recently posed by Gauci, Pisanski and Sciriha. These orders are known for d ≤ 4. Here we solve the problem for all remaining cases d ≤ 11 and determine the complete lists of all d-regular nut graphs of order n for small values of d and n. The existence or non-existence of small regular nut graphs is determined by a computer search. The main tool is a construction that produces, for any d-regular nut graph of order n, another d-regular nut graph of order n+2d. If we are given a sufficient number of d-regular nut graphs of consecutive orders, called seed graphs, this construction may be applied in such a way that the existence of all d-regular nut graphs of higher orders is established. For even d the orders n are indeed consecutive, while for odd d the orders n are consecutive even numbers. Furthermore, necessary conditions for combinations of order and degree for vertex-transitive nut graphs are derived.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 2; 533-557
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dualizing Distance-Hereditary Graphs
Autorzy:
McKee, Terry A.
Powiązania:
https://bibliotekanauki.pl/articles/32083836.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance-hereditary graph
dual graph
graph duality
Opis:
Distance-hereditary graphs can be characterized by every cycle of length at least 5 having crossing chords. This makes distance-hereditary graphs susceptible to dualizing, using the common extension of geometric face/vertex planar graph duality to cycle/cutset duality as in abstract matroidal duality. The resulting “DH* graphs” are characterized and then analyzed in terms of connectivity. These results are used in a special case of plane-embedded graphs to justify viewing DH* graphs as the duals of distance-hereditary graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 285-296
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge cycle extendable graphs
Autorzy:
McKee, Terry
Powiązania:
https://bibliotekanauki.pl/articles/743340.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cycle extendable graph
chordal graph
chordless graph
minimally 2-connected graph
Opis:
A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C⁺ is also formed from edges and one chord of a cycle C' of length one greater than C with V(C') ⊆ V(C⁺). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 2; 373-378
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the 12-Representability of Induced Subgraphs of a Grid Graph
Autorzy:
Chen, Joanna N.
Kitaev, Sergey
Powiązania:
https://bibliotekanauki.pl/articles/32361728.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph representation
12-representable graph
grid graph
forbidden subgraph
square grid graph
line grid graph
Opis:
The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53]. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12- representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question of Jones et al. is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al. by providing a complete characterization of 12-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 383-403
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 960

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