Temat: matching polynomial - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Mean value for the matching and dominating polynomial
Autorzy:: Arocha, Jorge
Llano, Bernardo
Powiązania:: https://bibliotekanauki.pl/articles/743687.pdf
Data publikacji:: 2000
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: matching
matching polynomial
dominating set
Opis:: The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2000, 20, 1; 57-69
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Extremal Matching Energy of Complements of Trees
Autorzy:: Wu, Tingzeng
Yan, Weigen
Zhang, Heping
Powiązania:: https://bibliotekanauki.pl/articles/31340889.pdf
Data publikacji:: 2016-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: matching polynomial
matching energy
Hosoya index
energy
Opis:: Gutman and Wagner proposed the concept of the matching energy which is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph. And they pointed out that the chemical applications of matching energy go back to the 1970s. Let $T$ be a tree with n vertices. In this paper, we characterize the trees whose complements have the maximal, second-maximal and minimal matching energy. Furthermore, we determine the trees with edge-independence number p whose complements have the minimum matching energy for $ p = 1, 2, . . ., \floor{ n/2 } $. When we restrict our consideration to all trees with a perfect matching, we determine the trees whose complements have the second-maximal matching energy.
Źródło:: Discussiones Mathematicae Graph Theory; 2016, 36, 3; 505-521
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: The Graphs Whose Permanental Polynomials Are Symmetric
Autorzy:: Li, Wei
Powiązania:: https://bibliotekanauki.pl/articles/31342428.pdf
Data publikacji:: 2018-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: permanental polynomial
rooted product
matching
Opis:: The permanental polynomial $ \pi (G,x) = \Sigma_{i=0}^n b_i x^{n − i} $ of a graph G is symmetric if $ b_i = b_n−i $ for each $i$. In this paper, we characterize the graphs with symmetric permanental polynomials. Firstly, we introduce the rooted product $ H(K) $ of a graph $ H $ by a graph $ K $, and provide a way to compute the permanental polynomial of the rooted product $ H(K) $. Then we give a sufficient and necessary condition for the symmetric polynomial, and we prove that the permanental polynomial of a graph $ G $ is symmetric if and only if $ G $ is the rooted product of a graph by a path of length one.
Źródło:: Discussiones Mathematicae Graph Theory; 2018, 38, 1; 233-243
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: The signed matchings in graphs
Autorzy:: Wang, Changping
Powiązania:: https://bibliotekanauki.pl/articles/743079.pdf
Data publikacji:: 2008
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: signed matching
signed matching number
maximum signed matching
signed edge cover
signed edge cover number
strongly polynomial-time
Opis:: Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → {-1,1} satisfying $∑_{e ∈ E_G(v)} x(e) ≤ 1$ for every v ∈ V(G), where $E_G(v) = {uv ∈ E(G)| u ∈ V(G)}$. The maximum of the values of $∑_{e ∈ E(G)} x(e)$, taken over all signed matchings x, is called the signed matching number and is denoted by β'₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β'₁(G) for general graphs. We investigate the sum of maximum size of signed matchings and minimum size of signed 1-edge covers. We disprove the existence of an analogue of Gallai's theorem. Exact values of β'₁(G) of several classes of graphs are found.
Źródło:: Discussiones Mathematicae Graph Theory; 2008, 28, 3; 477-486
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: Finding Dominating Induced Matchings in P₉-Free Graphs in Polynomial Time
Autorzy:: Brandstädt, Andreas
Mosca, Raffaele
Powiązania:: https://bibliotekanauki.pl/articles/32222548.pdf
Data publikacji:: 2022-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: dominating induced matching
P 9 -free graphs
polynomial time algorithm
Opis:: Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is ℕℙ-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P₇-free graphs and in polynomial time for P₈-free graphs. In this paper, we solve it in polynomial time for P₉-free graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1139-1162
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja