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ę "line graph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 19
Tytuł:
The structure and existence of 2-factors in iterated line graphs
Autorzy:
Ferrara, Michael
Gould, Ronald
Hartke, Stephen
Powiązania:
https://bibliotekanauki.pl/articles/743426.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
line graph
2-factor
iterated line graph
cycle
Opis:
We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where $L^k(G)$ contains a 2-factor.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 507-526
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterizations of the Family of All Generalized Line Graphs—Finite and Infinite—and Classification of the Family of All Graphs Whose Least Eigenvalues ≥ −2
Autorzy:
Vijayakumar, Gurusamy Rengasamy
Powiązania:
https://bibliotekanauki.pl/articles/29551714.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
generalized line graph
enhanced line graph
representation of a graph
extended line graph
least eigenvalue of a graph
Opis:
The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented by the root system E8. In [A. Torgašev, A note on infinite generalized line graphs, in: Proceedings of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983 (Univ. Novi Sad, 1984) 291- 297], it has been found that (2) any countably infinite connected graph with least eigenvalue ≥ −2 is a generalized line graph. In this article, the family of all generalized line graphs-countable and uncountable-is described algebraically and characterized structurally and an extension of (1) which subsumes (2) is derived.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 637-648
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterization of Line-Consistent Signed Graphs
Autorzy:
Slilaty, Daniel C.
Zaslavsky, Thomas
Powiązania:
https://bibliotekanauki.pl/articles/31339317.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
line-consistent signed graph
line graph
consistent vertex-signed graph
consistent marked graph
Opis:
The line graph of a graph with signed edges carries vertex signs. A vertex-signed graph is consistent if every circle (cycle, circuit) has positive vertex-sign product. Acharya, Acharya, and Sinha recently characterized line-consistent signed graphs, i.e., edge-signed graphs whose line graphs, with the naturally induced vertex signature, are consistent. Their proof applies Hoede’s relatively difficult characterization of consistent vertex-signed graphs. We give a simple proof that does not depend on Hoede’s theorem as well as a structural description of line-consistent signed graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 589-594
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Distance-Local Rainbow Connection Number
Autorzy:
Septyanto, Fendy
Sugeng, Kiki A.
Powiązania:
https://bibliotekanauki.pl/articles/32222664.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow connection
chromatic number
line graph
Opis:
Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any two vertices with distance at most d can be connected by a rainbow path (respectively, rainbow geodesic). This generalizes rainbow connection numbers, which are the special case d = diam(G). We discuss some bounds and exact values. Moreover, we also characterize all triples of positive integers d, a, b such that there is a connected graph G with lrcd(G) = a and lsrcd(G) = b.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1027-1039
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterizations of planar plick graphs
Autorzy:
Kulli, V.
Basavanagoud, B.
Powiązania:
https://bibliotekanauki.pl/articles/744402.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
inner vertex number
planar graph
line graph
plick graph
Opis:
In this paper we present characterizations of graphs whose plick graphs are planar, outerplanar and minimally nonouterplanar.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 41-45
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decompositions of multigraphs into parts with two edges
Autorzy:
Ivančo, Jaroslav
Meszka, Mariusz
Skupień, Zdzisław
Powiązania:
https://bibliotekanauki.pl/articles/743551.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge decomposition
multigraph
line graph
1-factor
Opis:
Given a family of multigraphs without isolated vertices, a multigraph M is called -decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of . We present necessary and sufficient conditions for the existence of such decompositions if comprises two multigraphs from the set consisting of a 2-cycle, a 2-matching and a path with two edges.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 113-121
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Arithmetically maximal independent sets in infinite graphs
Autorzy:
Bylka, Stanisław
Powiązania:
https://bibliotekanauki.pl/articles/744334.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
infinite graph
independent set
arithmetical maximal set
line graph
Opis:
Families of all sets of independent vertices in graphs are investigated. The problem how to characterize those infinite graphs which have arithmetically maximal independent sets is posed. A positive answer is given to the following classes of infinite graphs: bipartite graphs, line graphs and graphs having locally infinite clique-cover of vertices. Some counter examples are presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 167-182
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge homogeneous colorings
Autorzy:
Madaras, Tomáš
Onderko, Alfréd
Schweser, Thomas
Powiązania:
https://bibliotekanauki.pl/articles/2048718.pdf
Data publikacji:
2022
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
homogeneous coloring
Mq-coloring
line graph
role coloring
Opis:
We explore four kinds of edge colorings defined by the requirement of equal number of colors appearing, in particular ways, around each vertex or each edge. We obtain the characterization of graphs colorable in such a way that the ends of each edge see (not regarding the edge color itself) q colors (resp. one end sees q colors and the color sets for both ends are the same), and a sufficient condition for 2-coloring a graph in a way that the ends of each edge see (with the omission of that edge color) altogether q colors. The relations of these colorings to Mq-colorings and role colorings are also discussed; we prove an interpolation theorem for the numbers of colors in edge coloring where all edges around each vertex have q colors.
Źródło:
Opuscula Mathematica; 2022, 42, 1; 65-73
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Perfect Set of Euler Tours of Kp,p,p
Autorzy:
Govindan, T.
Muthusamy, A.
Powiązania:
https://bibliotekanauki.pl/articles/31340779.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
compatible Euler tour
line graph
Hamilton cycle decomposition
Opis:
Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 783-796
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Wiener index of generalized stars and their quadratic line graphs
Autorzy:
Dobrynin, Andrey
Mel'nikov, Leonid
Powiązania:
https://bibliotekanauki.pl/articles/743914.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance in a graph
Wiener index
star
iterated line graph
Opis:
The Wiener index, W, is the sum of distances between all pairs of vertices in a graph G. The quadratic line graph is defined as L(L(G)), where L(G) is the line graph of G. A generalized star S is a tree consisting of Δ ≥ 3 paths with the unique common endvertex. A relation between the Wiener index of S and of its quadratic graph is presented. It is shown that generalized stars having the property W(S) = W(L(L(S)) exist only for 4 ≤ Δ ≤ 6. Infinite families of generalized stars with this property are constructed.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 161-175
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Regular Signed Graphs with Three Eigenvalues
Autorzy:
Anđelić, Milica
Koledin, Tamara
Stanić, Zoran
Powiązania:
https://bibliotekanauki.pl/articles/31534886.pdf
Data publikacji:
2020-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
adjacency matrix
eigenvalue
regular signed graph
signed line graph
block design
Opis:
In this paper our focus is on regular signed graphs with exactly 3 (distinct) eigenvalues. We establish certain basic results; for example, we show that they are walk-regular. We also give some constructions and determine all the signed graphs with 3 eigenvalues, under the constraint that they are either signed line graphs or have vertex degree 3. We also report our result of computer search on those with at most 10 vertices.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 2; 405-416
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On •-Line Signed Graphs L•(S)
Autorzy:
Sinha, Deepa
Dhama, Ayushi
Powiązania:
https://bibliotekanauki.pl/articles/31339494.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
sigraph
line graph
•-line sigraph
balance
sign-compatibility
C-sign-compatibility
Opis:
A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the edges incident with the vertex in e ∩ e′. In this paper we establish a structural characterization of •-line sigraphs, extending a well known characterization of line graphs due to Harary. Further we study several standard properties of •-line sigraphs, such as the balanced •-line sigraphs, sign-compatible •-line sigraphs and C-sign-compatible •-line sigraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 215-227
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Vertex-Rainbow Connection Number of Some Graph Operations
Autorzy:
Li, Hengzhe
Ma, Yingbin
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/32083892.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow connection number
vertex-rainbow connection number
Cartesian product
lexicographic product
line graph
Opis:
A path in an edge-colored (respectively vertex-colored) graph G is rainbow (respectively vertex-rainbow) if no two edges (respectively internal vertices) of the path are colored the same. An edge-colored (respectively vertex-colored) graph G is rainbow connected (respectively vertex-rainbow connected) if every two distinct vertices are connected by a rainbow (respectively vertex-rainbow) path. The rainbow connection number rc(G) (respectively vertex-rainbow connection number rvc(G)) of G is the smallest number of colors that are needed in order to make G rainbow connected (respectively vertex-rainbow connected). In this paper, we show that for a connected graph G and any edge e = xy ∈ E(G), rvc(G) ≤ rvc(G − e) ≤ rvc(G) + dG−e(x, y) − 1 if G − e is connected. For any two connected, non-trivial graphs G and H, rad(G□H)−1 ≤ rvc(G□H) ≤ 2rad(G□H), where G□H is the Cartesian product of G and H. For any two non-trivial graphs G and H such that G is connected, rvc(G ◦ H) = 1 if diam(G ◦ H) ≤ 2, rad(G) − 1 ≤ rvc(G ◦ H) ≤ 2rad(G) if diam(G) > 2, where G ◦ H is the lexicographic product of G and H. For the line graph L(G) of a graph G we show that rvc(L(G)) ≤ rc(G), which is the first known nontrivial inequality between the rainbow connection number and vertex-rainbow connection number. Moreover, the bounds reported are tight or tight up to additive constants.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 513-530
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ł
Tytuł:
Sum List Edge Colorings of Graphs
Autorzy:
Kemnitz, Arnfried
Marangio, Massimiliano
Voigt, Margit
Powiązania:
https://bibliotekanauki.pl/articles/31340809.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
sum list edge coloring
sum choice index
sum list coloring
sum choice number
choice function
line graph
Opis:
Let $ G = (V,E) $ be a simple graph and for every edge $ \mathcal{e} \in E $ let $ L(e) $ be a set (list) of available colors. The graph $ G $ is called $L$-edge colorable if there is a proper edge coloring $ c $ of $ G $ with $ c(\mathcal{e} ) \in L( \mathcal{e} ) $ for all $ \mathcal{e} \in E $. A function $ f : E \rightarrow \mathbb{N} $ is called an edge choice function of $G$ and $G$ is said to be $f$-edge choosable if $G$ is $L$-edge colorable for every list assignment $L$ with $ |L( \mathcal{e} )| = f( \mathcal{e} ) $ for all $ \mathcal{e} \in E $. Set $ \text{size}(f) = \Sigma_{ \mathcal{e} \in E } f(e) $ and define the sum choice index $ \chi_{sc}^' (G) $ as the minimum of $ \text{size} (f) $ over all edge choice functions $f$ of $G$. There exists a greedy coloring of the edges of $G$ which leads to the upper bound $ \chi_{sc}^′ (G) \le 1/2 \Sigma_{ v \in V } d(v)^2 $. A graph is called sec-greedy if its sum choice index equals this upper bound. We present some general results on the sum choice index of graphs including a lower bound and we determine this index for several classes of graphs. Moreover, we present classes of sec-greedy graphs as well as all such graphs of order at most 5.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 709-722
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 19

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