Search

Start Over Subject graphs

2. A note on the domination number of a graph and its complement

Creator:
Marcu, Dănuţ
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
graphs, domination number, and graph’s complement
Language:
English
Description:
If G is a simple graph of size n without isolated vertices and G is its complement, we show that the domination numbers of G and G satisfy γ(G) + γ(G) ≤ { n − δ + 2 if γ(G) > 3, δ + 3 if γ(G) > 3, where δ is the minimum degree of vertices in G.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

4. All graphs in which each pair of distinct vertices has exactly two common neighbors

Creator:
Stevanović, Dragan
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
graphs, adjacency matrix, eigenvalues of a graph, and common neighbours
Language:
English
Description:
We find all connected graphs in which any two distinct vertices have exactly two common neighbors, thus solving a problem by B. Zelinka.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

6. An identity between the determinant and the permanent of Hessenberg-type matrices

Creator:
Da Fonseca, Carlos Martins
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
determinant, permanent, Hessenberg matrices;, graphs, and trees
Language:
English
Description:
In this short note we provide an extension of the notion of Hessenberg matrix and observe an identity between the determinant and the permanent of such matrices. The celebrated identity due to Gibson involving Hessenberg matrices is consequently generalized.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

7. Bounds on the subdominant eigenvalue involving group inverses with applications to graphs

Creator:
Kirkland, Stephen J., Neumann, Michael, and Shader, Bryan L.
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
math, eigenvalues, and graphs
Language:
English
Description:
Let $A$ be an $n\times n$ symmetric, irreducible, and nonnegative matrix whose eigenvalues are $\lambda _1 > \lambda _2 \ge \ldots \ge \lambda _n$. In this paper we derive several lower and upper bounds, in particular on $\lambda _2$ and $\lambda _n$, but also, indirectly, on $\mu = \max _{2\le i \le n} |\lambda _i|$. The bounds are in terms of the diagonal entries of the group generalized inverse, $Q^{\#}$, of the singular and irreducible M-matrix $Q=\lambda _1 I-A$. Our starting point is a spectral resolution for $Q^{\#}$. We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected graphs, where now $Q$ becomes $L$, the Laplacian of the graph. In case the graph is a tree we find a graph-theoretic interpretation for the entries of $L^{\#}$ and we also sharpen an upper bound on the algebraic connectivity of a tree, which is due to Fiedler and which involves only the diagonal entries of $L$, by exploiting the diagonal entries of $L^{\#}$.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

8. Classifying trees with edge-deleted central appendage number 2

Creator:
Stalder, Shubhangi, Eroh, Linda, Koker, John, Moghadam, Hosien S., and Winters, Steven J.
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
graphs, trees, and central appendage number
Language:
English
Description:
The eccentricity of a vertex v of a connected graph G is the distance from v to a vertex farthest from v in G. The center of G is the subgraph of G induced by the vertices having minimum eccentricity. For a vertex v in a 2-edge-connected graph G, the edge-deleted eccentricity of v is defined to be the maximum eccentricity of v in G − e over all edges e of G. The edge-deleted center of G is the subgraph induced by those vertices of G having minimum edge-deleted eccentricity. The edge-deleted central appendage number of a graph G is the minimum difference |V (H)| − |V (G)| over all graphs H where the edgedeleted center of H is isomorphic to G. In this paper, we determine the edge-deleted central appendage number of all trees.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

9. Distance in stratified graphs

Creator:
Chartrand, Gary, Hansen, Lisa, Rashidi, Reza, and Sherwani, Naveed
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
math, graphs, and strata in a stratified graph
Language:
English
Description:
A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$, the $X$-eccentricity $e_X(v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$-colored vertex furthest from $v$. The minimum $X$-eccentricity among the vertices of $G$ is the $X$-radius $\mathop {\mathrm rad}\nolimits _XG$ of $G$ and the maximum $X$-eccentricity is the $X$-diameter $\mathop {\mathrm diam}\nolimits _XG$. It is shown that for every three positive integers $a, b$ and $k$ with $a \le b$, there exist a $k$-stratified graph $G$ with $\mathop {\mathrm rad}\nolimits _XG=a$ and $\mathop {\mathrm diam}\nolimits _XG=b$. The number $s_X$ denotes the minimum $X$-eccetricity among the $X$-colored vertices of $G$. It is shown that for every integer $t$ with $\mathop {\mathrm rad}\nolimits _XG \le t \le \mathop {\mathrm diam}\nolimits _XG$, there exist at least one vertex $v$ with $e_X(v)=t$; while if $\mathop {\mathrm rad}\nolimits _XG \le t \le s_X$, then there are at least two such vertices. The $X$-center $C_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(v)=\mathop {\mathrm rad}\nolimits _XG$ and the $X$-periphery $P_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(G)=\mathop {\mathrm diam}\nolimits _XG$. It is shown that for $k$-stratified graphs $H_1, H_2, \dots , H_k$ with colors $X_1, X_2, \dots , X_k$ and a positive integer $n$, there exists a $k$-stratified graph $G$ such that $C_{X_i}(G) \cong H_i \ (1 \le i \le k)$ and $d(C_{X_i}(G), C_{X_j}(G)) \ge n \text{for} i \ne j$. Those $k$-stratified graphs that are peripheries of $k$-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

10. Light paths with an odd number of vertices in polyhedral maps

Creator:
Jendroĺ, Stanislav and Voss, Heinz-Jürgen
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
graphs, path, polyhedral map, and embeddings
Language:
English
Description:
Let $P_k$ be a path on $k$ vertices. In an earlier paper we have proved that each polyhedral map $G$ on any compact $2$-manifold $\mathbb{M}$ with Euler characteristic $\chi (\mathbb{M})\le 0$ contains a path $P_k$ such that each vertex of this path has, in $G$, degree $\le k\left\lfloor \frac{5+\sqrt{49-24 \chi (\mathbb{M})}}{2}\right\rfloor $. Moreover, this bound is attained for $k=1$ or $k\ge 2$, $k$ even. In this paper we prove that for each odd $k\ge \frac{4}{3} \left\lfloor \frac{5+\sqrt{49-24\chi (\mathbb{M})}}{2}\right\rfloor +1$, this bound is the best possible on infinitely many compact $2$-manifolds, but on infinitely many other compact $2$-manifolds the upper bound can be lowered to $\left\lfloor (k-\frac{1}{3})\frac{5+\sqrt{49-24\chi (\mathbb{M})}}{2}\right\rfloor $.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public